Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium

In display 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 as well as competitors’ heterogeneous preferences, budgets, and strategies. We formulate this problem as a sequential game of incomplete information, where bidders know neither their own valuation distribution, nor the budgets and valuation distributions of their competitors. We introduce a family of dynamic bidding strategies we refer to as adaptive pacing strategies, in which advertisers adjust their bids throughout the campaign according to the sample path of expenditures they exhibit. We analyze the performance of these strategies under different assumptions on competitors’ behavior. Under arbitrary competitors’ bids, we establish through matching lower and upper bounds the asymptotic optimality of this class of strategies as the number of auctions grows large. When all the bidders adopt these strategies, the dynamics converge to a tractable and meaningful steady state. Moreover, we characterize a regime (well motivated in the context of display advertising markets) under which these strategies constitute an approximate Nash equilibrium in dynamic strategies: The benefit of 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 equilibrium bidding strategies that also ensure the best performance that can be guaranteed off-equilibrium.