1 September 2019 in Management Science
In online advertising markets, advertisers often purchase ad placements through bidding in repeated auctions based on realized viewer information. We study how budget-constrained advertisers may compete in such sequential auctions in the presence of uncertainty about future bidding opportunities and competition. We formulate this problem as a sequential game of incomplete information, in which bidders know neither their own valuation distribution nor the budgets and valuation distributions of their competitors. We introduce a family of practical bidding strategies we refer to as adaptive pacing strategies, in which advertisers adjust their bids according to the sample path of expenditures they exhibit, and analyze the performance of these strategies in different competitive settings. We establish the asymptotic optimality of these strategies when competitors’ bids are independent and identically distributed over auctions, but also when competing bids are arbitrary. When all the bidders adopt these strategies, we establish the convergence of the induced dynamics and characterize a regime (well motivated in the context of online advertising markets) under which these strategies constitute an approximate Nash equilibrium in dynamic strategies: the benefit from unilaterally deviating to other strategies, including ones with access to complete information, becomes negligible as the number of auctions and competitors grows large. This establishes a connection between regret minimization and market stability, by which advertisers can essentially follow approximate equilibrium bidding strategies that also ensure the best performance that can be guaranteed off equilibrium. This paper was accepted by Noah Gans, stochastic models and simulation.
1 December 2019 in Stochastic Systems
In a multi-armed bandit problem, a gambler needs to choose at each round one of K arms, each characterized by an unknown reward distribution. The objective is to maximize cumulative expected earnings over a planning horizon of length T, and performance is measured in terms of regret relative to a (static) oracle that knows the identity of the best arm a priori. This problem has been studied extensively when the reward distributions do not change over time, and uncertainty essentially amounts to identifying the optimal arm. We complement this literature by developing a flexible non-parametric model for temporal uncertainty in the rewards. The extent of temporal uncertainty is measured via the cumulative mean change in the rewards over the horizon, a metric we refer to as temporal variation, and regret is measured relative to a (dynamic) oracle that plays the point-wise optimal action at each period. Assuming that nature can choose any sequence of mean rewards such that their temporal variation does not exceed V (a temporal uncertainty budget), we characterize the complexity of this problem via the minimax regret, which depends on V (the hardness of the problem), the horizon length T, and the number of arms K.
1 October 2023 in Management Science
We consider a platform facilitating trade between sellers and buyers with the objective of maximizing consumer surplus. Even though in many such marketplaces, prices are set by revenue-maximizing sellers, platforms can influence prices through (i) price-dependent promotion policies that can increase demand for a product by featuring it in a prominent position on the web page and (ii) the information revealed to sellers about the value of being promoted. Identifying effective joint information design and promotion policies is a challenging dynamic problem as sellers can sequentially learn the promotion value from sales observations and update prices accordingly. We introduce the notion of confounding promotion policies, which are designed to prevent a Bayesian seller from learning the promotion value (at the expense of the short-run loss of diverting some consumers from the best product offering). Leveraging these policies, we characterize the maximum long-run average consumer surplus that is achievable through joint information design and promotion policies when the seller sets prices myopically. We then construct a Bayesian Nash equilibrium, in which the seller’s best response to the platform’s optimal policy is to price myopically in every period. Moreover, the equilibrium we identify is platform optimal within the class of horizon-maximin equilibria, in which strategies are not predicated on precise knowledge of the horizon length and are designed to maximize payoff over the worst-case horizon. Our analysis allows one to identify practical long-run average optimal platform policies in a broad range of demand models. This paper was accepted by David Simchi-Levi, revenue management and market analytics. Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2023.4677 .
1 January 2014 in SSRN Electronic Journal
In a multi-armed bandit (MAB) problem a gambler needs to choose at each round of play one of K arms, each characterized by an unknown reward distribution. Rewa
1 November 2022 in Operations Research
In nonparametric contextual bandit formulations, a key complexity driver is the smoothness of payoff functions with respect to covariates. In many practical settings, the smoothness of payoffs is unknown, and misspecification of smoothness may severely deteriorate the performance of existing methods. In the paper “Smoothness-Adaptive Contextual Bandits,” Yonatan Gur, Ahmadreza Momeni, and Stefan Wager consider a framework where the smoothness of payoff functions is unknown and study when and how algorithms may adapt to unknown smoothness. First, they establish that designing algorithms that adapt to unknown smoothness is, in general, impossible. However, under a natural self-similarity condition, they establish that adapting to unknown smoothness is possible and devise a general policy for achieving smoothness-adaptive performance. The policy infers the smoothness of payoffs throughout the decision-making process while leveraging the structure of off-the-shelf nonadaptive policies. It matches (up to a logarithmic scale) the performance that is achievable when the smoothness of payoffs is known in advance.