This paper takes a game theoretic approach to the design and analysis of online algorithms and illustrates the approach on the finite-horizon ski-rental problem. This approach allows beyond worst-case analysis of online algorithms. First, we define "subgame optimality" which is stronger than worst case optimality in that it requires the algorithm to take advantage of an adversary not playing a worst case input. Algorithms only focusing on the worst case can be far from subgame optimal. Second, we consider prior-independent design and analysis of online algorithms, where rather than choosing a worst case input, the adversary chooses a worst case independent and identical distribution over inputs. Prior-independent online algorithms are generally analytically intractable; instead we give a fully polynomial time approximation scheme to compute them. Highlighting the potential improvement from these paradigms for the finite-horizon ski-rental problem, we empirically compare worst-case, subgame optimal, and prior-independent algorithms in the prior-independent framework.

The prior independent framework for algorithm design considers how well an algorithm that does not know the distribution of its inputs approximates the expected performance of the optimal algorithm for this distribution. This paper gives a method that is agnostic to problem setting for proving lower bounds on the prior independent approximation factor of any algorithm. The method constructs a correlated distribution over inputs that can be described both as a distribution over i.i.d. good-for-algorithms distributions and as a distribution over i.i.d. bad-for-algorithms distributions. We call these two descriptions equivocal blends. Prior independent algorithms are upper-bounded by the optimal algorithm for the latter distribution even when the true distribution is the former. Thus, the ratio of the expected performances of the Bayesian optimal algorithms for these two decompositions is a lower bound on the prior independent approximation ratio. We apply this framework to give new lower bounds on canonical prior independent mechanism design problems. For one of these problems, we also exhibit a near-tight upper bound. Towards solutions for general problems, we give distinct descriptions of two large classes of correlated-distribution "solutions" for the technique, depending respectively on an order-statistic separability property and a paired inverse-distribution property. We exhibit that equivocal blends do not generally have a Blackwell ordering, which puts this paper outside of standard information design.

Firms engaged in electronic commerce increasingly rely on predictive analytics via machine-learning algorithms to drive a wide array of managerial decisions. The tuning of many standard machine learning algorithms can be understood as trading off bias (i.e., accuracy) with variance (i.e., precision) in the algorithm's predictions. The goal of this paper is to understand how competition between firms affects their strategic choice of such algorithms. To this end, we model the interaction of two firms choosing learning algorithms as a game and analyze its equilibria. Absent competition, players care only about the magnitude of predictive error and not its source. In contrast, our main result is that with competition, players prefer to incur error due to variance rather than due to bias, even at the cost of higher total error. In addition, we show that competition can have counterintuitive implications---for example, reducing the error incurred by a firm's algorithm can be harmful to that firm---but we provide conditions under which such phenomena do not occur. In addition to our theoretical analysis, we also validate our insights by applying our metrics to a publicly available data set.

A rich class of mechanism design problems can be understood as incomplete-information games between a principal who commits to a policy and an agent who responds, with payoffs determined by an unknown state of the world. Traditionally, these models require strong and often-impractical assumptions about beliefs (a common prior over the state). In this paper, we dispense with the common prior. Instead, we consider a repeated interaction where both the principal and the agent may learn over time from the state history. We reformulate mechanism design as a reinforcement learning problem and develop mechanisms that attain natural benchmarks without any assumptions on the state-generating process. Our results make use of novel behavioral assumptions for the agent - based on counterfactual internal regret - that capture the spirit of rationality without relying on beliefs.11For the full version of this paper, see https://arxiv.org/abs/2009.05518.

This paper compares two leading approaches for robust optimization in the models of online algorithms and mechanism design. Competitive analysis compares the performance of an online algorithm to an offline benchmark in worst-case over inputs, and prior-independent mechanism design compares the expected performance of a mechanism on an unknown distribution (of inputs, i.e., agent values) to the optimal mechanism for the distribution in worst case over distributions. For competitive analysis, a critical concern is the choice of benchmark. This paper gives a method for selecting a good benchmark. We show that optimal algorithm/mechanism for the optimal benchmark is equal to the prior-independent optimal algorithm/mechanism. We solve a central open question in prior-independent mechanism design, namely we identify the prior-independent revenue-optimal mechanism for selling a single item to two agents with i.i.d. and regularly distributed values. We use this solution to solve the corresponding benchmark design problem. Via this solution and the above equivalence of prior-independent mechanism design and competitive analysis (a.k.a. prior-free mechanism design) we show that the standard method for lower bounds of prior-free mechanisms is not generally tight for the benchmark design program.11For the full version of this work, see https://arxiv.org/abs/2001.10157.

Econometric inference allows an analyst to back out the values of agents in a mechanism from the rules of the mechanism and bids of the agents. This paper gives an algorithm to solve the problem of inferring the values of agents in a dominant-strategy mechanism from: the social choice function implemented by the mechanism and the per-unit prices paid by the agents (the agent bids are not observed). For single-dimensional agents, this inference problem is a multi-dimensional inversion of the payment identity and is feasible only if the payment identity is uniquely invertible. The inversion is unique for single-unit proportional weights social choice functions (common, for example, in bandwidth allocation); and its inverse can be found efficiently. This inversion is not unique for social choice functions that exhibit complementarities. Of independent interest, we extend a result of Rosen (1965), that the Nash equilbria of “concave games” are unique and pure, to an alternative notion of concavity based on Gale and Nikaido (1965).