Management Science Review

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 https://doi.org/10.1287/mnsc.2018.3174.

REFERENCE

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

Learning consumer demand from early sales is a complex but a potentially rewarding practice for retailers of fashion products. With learning capability, a retailer can adjust prices during a sales season in response to sales observations; i.e., the retailer can benefit from the ability to act upon updated information. The potential value of demand learning under dynamic pricing could be significant and has been the preeminent motivation for retailers to acquire such capability. Nonetheless, in fashion retail environments, consumers may be cognizant of a retailer’s learn-and-price strategy; as a result, they may strategically adjust their purchase timing in anticipation of price changes driven by the dynamics of the retailer’s learning process. This gives rise to an important question: Is the adoption of learning technology truly beneficial for a retailer that sells fashion goods to strategic consumers? In the paper “Responsive Pricing of Fashion Products: The Effects of Demand Learning and Strategic Consumer Behavior”, Yossi Aviv, Mike Mingcheng Wei, and Fuqiang Zhang address this question.

View Full Post »

It has been argued, that the amazing expansion that many digital markets, and especially the market for mobile smartphone apps, have seen over the past decade was fueled by the possibility to collect previously unseen amounts of user data.

View Full Post »

In the book The Innovator’s Prescription, Harvard’s Clayton Christensen and colleagues have described hospitals as “some of the most managerially intractable institutions in the annals of capitalism”. While there are many factors that make hospitals difficult to manage, they argue that an operational dilemma lies at the heart of this managerial complexity: The tension between standardization and compliance on the one hand and creative autonomous solution finding on the other. These two operational modes require very different management styles and mixing them in the same organizational unit leads to dissonance and confusion. It is no coincidence that R&D and manufacturing are clearly separated in organizations that do both.

View Full Post »

Existing knowledge suggests that State-owned enterprises (SOEs) are managed inefficiently and influenced by inadequate political goals. This conventional thought, however, contradicts with the observation that state capitalism in China has been one of the most important contributors to its miracle economic growth in the past 4 decades. This contradiction is especially puzzling given that CEOs in Chinese SOEs are poorly incentivized using the traditional managerial incentives measures, i.e., monetary compensation.

View Full Post »

Service sectors are very labor intensive – they hire millions of workers, but generally suffer from low labor productivity (about three fourth of the productivity of industry sectors). Effective team management has the potential to serve as a powerful operational lever to improve labor productivity, not only because service workers often work in teams/groups, but also because effective teams often create value more than the sum of their individual parts.

View Full Post »

Much of the literature on oligopolistic competition typically features firms operating in a single, well-defined, and isolated market. In practice though, firms compete with one another across several different geographical or product markets. In fact, there is strong empirical evidence that multi-market competition is prevalent in many industries (e.g., cement, healthcare, electricity, airlines, banking) and single-market models are far too limited to provide an accurate description of the strategic interactions in such environments.

View Full Post »

Why would a computer algorithm decide to show an ad promoting careers in the STEM sector (Science, Technology, Engineering and Math) to 20% more men than women? That is the question at the heart of a new article published in Management Science entitled, “Algorithmic Bias? An Empirical Study of Apparent Gender-Based Discrimination in the Display of STEM Career Ads”.

View Full Post »

The importance of customer demand on motivating supplier innovation has long been recognized, and feedback from customers plays a key role in this “demand-pull innovation” process. Timely reception of feedback, accurate interpretation of requests, and prompt adjustment in intermediate stages are critical to the ultimate success of innovation, and they all require frequent and intensive interactions between suppliers and customers. With the rapid development of transportation and communication tools, does locating closer to major customers remains an important determinant to suppliers’ innovation success nowadays? In “Corporate Innovation along the Supply Chain (June, 2019)”, Yongqiang Chu, Xuan Tian, and Wenyu Wang empirically investigate this question.

View Full Post »

Everybody loves Silicon Valley. Imitations can be found worldwide: Silicon Forest (Oregon), Swamp (Florida), Gorge (UK), Glen (Scotland), Fjord (Norway), Wadi (Israel), Savannah (Kenya), and many more. Policy makers, in particular, are eager to foster entrepreneurial ecosystems by promoting entrepreneurship, with the hope to foster economic growth, employment, and innovation. However, very different approaches can be taken by governments to achieve these goals. The question becomes how to foster entrepreneurship? This is the question asked by Thomas Hellmann and Veikko Thiele in their Management Science paper called “Fostering Entrepreneurship: Promoting Founding or Funding?”

View Full Post »