Online Advertising: Competing Effectively when Budget is Limited

In online advertising markets, advertising campaigns are often budgeted, as a mean to control expenditure. In practice, these budget limit the total expenditures of advertisers throughout their campaign and strategically couple competitive interactions between competing advertisers. 

A key operational challenge that is fundamental for managing budgeted campaigns is to balance present and future bidding opportunities effectively. This challenge has received increasing attention in the online advertising industry, where platforms now provide budget pacing services to help advertisers “pace” their expenditure rate and maximize the return from their campaigns. Budget pacing is particularly challenging due to the uncertainties that characterize online ad markets. Advertisers not only have uncertainties about their future opportunities, but also know very little about important characteristics of their competitors, such as their budgets, their expectations regarding future opportunities, and their strategic and technical sophistication level. While some firms devote considerable resources to develop data-driven dynamic algorithms that respond in real-time to competitors’ actions, other, less resourceful firms may adopt static and user-independent strategies.

The paper “Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium” (Santiago R. Balseiro and Yonatan Gur, Management Science, 2019, Volume 65, Issue 9) studies how budget-constrained advertisers may compete in sequential auctions under uncertainty. The authors formulate this problem as a sequential game of incomplete information, where bidders know neither their valuation distribution nor the budgets and value distributions of their competitors. They introduce a class of simple and practical strategies referred to as adaptive pacing. These strategies are based on a primal-dual approximation method designed to determine the extent to which advertisers should adjust their bids based only on the sample path of expenditures they exhibit.

The authors establish the asymptotic optimality of these strategies against (stationary) stochastic competing bids, as well as against arbitrary bids. Moreover, when all bidders adopt these strategies, the authors establish that the induced dynamics converge, and characterize a regime (that is very relevant to practice in display advertising markets) under which these strategies constitute an approximate Nash equilibrium in dynamic strategies. Notably, this strong equilibrium concept implies that the benefit of deviating from these strategies diminishes to zero even when advertisers know their value distribution as well as the value distributions and budgets of their competitors upfront, and even when they can acquire real-time information on the past values, bids, and payoffs of their competitors. Finally, using data from a leading advertising platform, they demonstrate that adaptive pacing strategies perform well in practice.

This work establishes a novel connection between regret minimization and market stability in the context of online advertising markets, by which advertisers can follow approximate equilibrium strategies that also ensure the best performance that can be guaranteed off-equilibrium.

For more perspective on this research, the E-i-C asked two experts, Dr. Nicolas Stier-Moses, Facebook Core Data Science and Professor Ramesh Johari, Stanford University, Department of Management Science and Engineering, for comments and reflections on the article. Their responses are given below:

Nicolas Stier-Moses, Facebook

Marketplace modeling is one of areas with most widespread impact in the real world among those addressed by the Operations Research and Management Science community and its journals. Several decades ago, researchers in the area of mechanism design had been trying to find optimal mechanisms and this culminated in the Nobel-prize winning optimal auction paper by Myerson published in Math of Operations Research in 1981. The Revenue Management and Pricing Section of INFORMS, which was traditionally focused on airline, hospitality and other service-related applications, more explicitly expanded its charter to include studying marketplaces since pricing is a key aspect in them. INFORMS recently constituted the Auctions and Market Design Section to host some of the work in those areas. Putting this in perspective, the virtual marketplaces that allow participants to buy and sell advertising online produce billions of transactions with an ad spend of around a hundred billion of dollars per year in the US, according to some current estimates. This has allowed advertisers to interact with Internet users that are more relevant than when using traditional media, increasing the return on investment. These interactions generated new business needs and, in turn, this has contributed to the emergence of a very complex ecosystem of digital advertising companies. Those interactions are the subject of many studies addressed by this research community.

The article “Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium” by Balseiro and Gur, featured in Management Science, 2019, Volume 65, Issue 9, precisely addresses the interactions between advertisers and platforms. Advertisers participate in repeated auctions to place ads in front of users, constrained by an overall budget that limits their total spend. The results focus on one aspect of crucial importance: how to align budgets with bids relying on a dynamic algorithm that updates the bids to satisfy the budgets. From the theoretical point of view, researchers had found some impossibility results about abstract optimal mechanisms for repeated auctions with budgets. Yet, platforms in the high-tech industry need to offer practical solutions to the problem because they rely on those repeated auctions as a strategic revenue stream. Instead of implementing complex mechanisms that are hard to implement or to understand by their advertisers, platforms went ahead to implement auction markets that simplify the interaction between them. The advertisers communicate their maximum (or average) bids and their overall budgets for their campaigns, and the platforms run the sequential auctions using those parameters to determine winners and prevailing prices. The most popular mechanisms used in practice attempt to learn the bids to be applied to the set of auctions associated with an ad campaign by either shading the bid appropriately or by determining a participation probability, generically referred to as “pacing.” In both cases, the goal is to reduce the rate of spend so the participant does not run out of budget prematurely if the budget is too low with respect to the specified bid.

This practical motivation prompted a recent research stream that looks at practically-motivated mechanisms, instead of optimal ones, and explores their properties. Advertisers are asked to create a bidding strategy in advance when setting up a campaign since frequently advertisers do not look at auctions one-by-one and there is uncertainty in the value generated when winning an auction (e.g., conversions down the funnel are stochastic and the lifetime value of a user is revealed over time). In addition, often advertisers bid without knowing who else participates in a particular auction. With campaigns already in place, platforms proceed to find bids that are consistent with budgets. The main complication is that the shading of bids is done for all participants simultaneously and hence it creates externalities between participants. This motivates the whole process to be interpreted as a game. Some papers in the last couple of years---starting with “Repeated Auctions with Budgets in Ad Exchanges: Approximations and Design” by Balseiro et al. (Management Science, 2015, Vol 61, Issue 4) ---discuss versions of this game, prove results about the existence of equilibria, provide an understanding of equilibrium properties, and suggest algorithms to compute those equilibria.

However, most of those papers and results quoted earlier involve static models. This is in stark contrast with reality in which learning optimal shading factors for bids is a dynamic process. The main contribution of the article by Balseiro and Gur is to consider dynamics in which participants learn how to adapt the spending rate so the budget is exhausted at the end of the planning period. The article suggests a simple form of additive learning that operates on the Lagrangian dual space and studies it in depth, answering several questions of practical relevance. These strategic considerations faced by advertisers may be implemented by them directly, by agents acting on their behalf, or by platforms themselves.

The article is very thorough in exploring variations of the assumptions, which are quite general and realistic. For instance, competing advertisers are assumed to have various degrees of bounded rationality. They may bid independently, following identical distributions; arbitrarily, possibly trying to negatively impact others in an adversarial manner; or following the same learning procedure as everybody else. In the context of the dynamic model, this pushes the boundary of what was previously understood for games of this kind. The crux of the article consists in proposing “a class of practical budget-pacing strategies with performance guarantees ... and concrete notions of optimality under competition.” The outcome is a learning strategy that works under uncertainty and competition, and that leads to endogenous and non-stationary spending rates. Relying on the strategy suggested by the article, participants can follow an equilibrium strategy, while being robust when competitors do not follow it and guarantee good performance. To complete the exposition, not only the paper explores the setting theoretically, but also they provide an empirical analysis of a real market.

The paper is very timely in opening the door to future work that can address and provide further insights about very practical questions the industry is facing. Importantly, first price auctions are known to suffer from incentive issues when taken in isolation. From a theoretical point of view, pacing for first price auctions, though, was shown to be attractive for large platforms with a thick demand density over repeated auctions (Conitzer et al., working paper 2019). Coincidentally, several real-world ad exchange platforms switched to first price auctions recently while Google AdX just announced they will convert their systems by the end of 2019. The dynamics studied in this article can continue to shed light into the differences between first- and second-price pacing mechanisms.

To conclude, another interesting area to dwell deeper is on computation. The computational study shown in the article relies on a medium size instance. In practice, to shed light on actual questions related to their marketplaces, platforms need to compute equilibria for much larger instances. It would be interesting to understand how convergence behaves as instances scale to billions of auctions and millions of advertisers, and to develop computational techniques that are efficient to support such large instances.

Ramesh Johari, Stanford University

From its beginnings nearly two decades ago, the Internet advertising industry has swelled to become a significant sector of the modern online economy.  The industry was valued at over $70 billion in transaction volume as of 2016.  There are several different forms of advertising, including both sponsored search results (e.g., displayed alongside ``organic'' search results when queries are issued at a search engine such as Google), and display advertising (ad images displayed alongside published content).

With few exceptions, these are in fact large auction marketplaces where advertisers bid to be able to display their ad; Google, Facebook, Yahoo!, and Microsoft all run such marketplaces.  Advertisers set a budget for a fixed period of advertising (called a “campaign”), and bid sequentially in auctions to attempt to maximize their return on the budget.  Given the speed at which these auctions take place, advertisers must rely on algorithmic techniques to dynamically optimize their bidding strategy.  Indeed, an entire industry on search engine marketing (SEM) optimization has arisen to help bidders optimize their spend allocation over time.

The central algorithmic challenge is this: how much should an advertiser bid for a given opportunity?  The bidding problem is complicated by the fact that the bidder operates in a highly uncertain environment.  While the advertiser is likely well informed about the value of the current opportunity, she is unlikely to be so well informed about the value of future opportunities.  Even worse, she is also likely to be highly uncertain about the competition: both their budgets, as well as their values for advertising opportunities.

In the current paper, the authors tackle this question.  They study a simple algorithm that can provably perform well for the advertiser, under a wide range of modeling assumptions about the sources of uncertainty described above.  The algorithm they study, referred to as adaptive pacing, is intuitive and simple to describe.  At each time period, the auction being run is a second-price auction; thus if there were no dynamic budgetary considerations in play, bidding truthfully would be the advertisers optimal choice.  Because the budget limited, the advertiser will want to shade her bid downwards.  The adaptive pacing policy maintains a “bid shading multiplier”; the actual bid is the valuation times this bid shading multiplier.  At each time step, the algorithm compares the actual expenditure in the auction to the expected rate of spend (budget per auction during the campaign).  If the actual expenditure is higher (resp., lower) than this expected rate, then the algorithm surmises that future opportunities offer higher (resp., lower) “bang for the buck” than current opportunities, and therefore the algorithm lowers (resp., raises) the bid shading multiplier.  The algorithm has a natural interpretation as an approximate primal-dual algorithm: the bid shading multiplier encodes a shadow price on the budget constraint, and adaptively trades off present and future spend. 

Though relatively simple to describe, the proposed adaptive pacing policy turns out to have surprisingly strong robustness guarantees.  The authors evaluate performance by measuring regret of the adaptive pacing policy against the optimal dynamic bidding policy in hindsight (i.e., with full knowledge of the realization of valuations and competitors' bids), asymptotically in the number of auctions the advertiser joins.  Note that to characterize asymptotic regret, the authors must specify how competing bids evolve in the system; the authors provide a rich treatment here.  In particular, when competing bids are essentially arbitrary, the authors show that the adaptive pacing policy asymptotically attains the maximum achievable fraction of the reward rate of the optimal benchmark.  When competing bids are i.i.d., the authors show that the adaptive pacing policy asymptotically achieves exactly the benchmark reward rate.

Finally, the authors consider what happens if all advertisers use the adaptive pacing policy.  In particular, in a model where advertisers are matched to auctions i.i.d. at each time step (referred to as “parallel auctions”), the authors show that adaptive pacing is approximately a dynamic Nash equilibrium strategy as the number of advertisers and number of auctions grows large --- in other words, the gain for any single advertiser to switching to any other dynamic policy becomes vanishingly small.  (A related 2018 preprint by Conitzer, Kroer, Sodomka, and Stier Moses studies competition in a complete information setting when multiple advertisers employ multiplicative bid shading strategies; numerical experiments there also provide supporting evidence that such strategies can constitute an equilibrium.) Taken together, the results provide a compelling picture of the value of adaptive pacing: as the authors note, these results ensure good performance both in equilibrium and out of equilibrium.

We close by briefly discussing several aspects of the paper that suggest natural open directions for future work. First, the authors' model has all advertisers begin their campaigns at the same time; this synchronicity assumption simplifies the analysis.  In reality, however, competitors have very different levels of information and experience, entering and departing auctions over time.  Does adaptive pacing continue to yield an approximate equilibrium under these conditions?  

More broadly, the paper encourages us to consider the value of information in the Internet advertising industry.  In particular, it is interesting to reflect on the relative profitability of the bid optimization industry in light of the paper's results.  In order for bid optimization to be a profitable third-party service, the information and computation advantage offered by such firms must be significant.  The results of the paper suggest that the additional value of such firms may be small if the market equilibrates to all advertisers employing the adaptive pacing policy.  Empirical validation of the added value of superior information would be worthwhile, since this would be a key pathway by which such firms can claim to offer additional value.

Finally, an important aspect of modern Internet advertising is the wide range of available options for advertisers; for example, in sponsored search, an advertiser must explore to find the optimal set of keywords to bid on.  Indeed, an important function of many bid optimization platforms is to help their clients select keywords; this learning problem is at least as acute as the budget optimization problem studied by the authors.  A natural direction then involves developing methods that combine the adaptive pacing policy with multi-armed bandit algorithms for keyword selection, and similarly investigating whether such policies have natural robustness and approximate equilibrium properties.

Read the full article at


Balseiro SR and Gur Y (2019). Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium. Management Science 65(9).