This article introduces a near-optimal bidding algorithm for use in real-time display advertising auctions. These auctions constitute a dominant distribution channel for internet display advertising and a potential funding model for addressable media. The proposed efficient, implementable learning algorithm is proven to rapidly converge to the optimal strategy while achieving zero regret and constituting a competitive equilibrium. This is the first algorithmic solution to the online knapsack problem to offer such theoretical guarantees without assuming a priori knowledge of object values or costs. Furthermore, it meets advertiser requirements by accommodating any valuation metric while satisfying budget constraints. Across a series of 100 simulated and 10 real-world campaigns, the algorithm delivers 98% of the value achievable with perfect foresight and outperforms the best available alternative by 11%. Finally, we show how the algorithm can be augmented to simultaneously estimate impression values and learn the bidding policy. Across a series of simulations, we show that the total regret delivered under this dual objective is less than that from any competing algorithm required only to learn the bidding policy.
AgrawalShipraGoyalNavin (2013), “Further Optimal Regret Bounds for Thompson Sampling,” Artificial Intelligence and Statistics, 31, 99–107.
2.
AgrawalShipraWangZizhuoYeYinyu (2014), “A Dynamic Near-Optimal Algorithm for Online Linear Programming,” Operations Research, 62 (4), 876–90.
3.
AmarJonathanRenegarNicholas (2018), “The Second-Price Knapsack Problem: Near-Optimal Real Time Bidding in Internet Advertisement,” https://arxiv.org/abs/1810.10661.
4.
AndersonErinLodishLeonard M.WeitzBarton A. (1987), “Resource Allocation Behavior in Conventional Channels,” Journal of Marketing Research, 24 (1), 85–97.
5.
BalseiroSantiago R.BesbesOmarWeintraubGabriel Y. (2015), “Repeated Auctions with Budgets in ad Exchanges: Approximations and Design,” Management Science, 61 (4), 864–84.
6.
BalseiroSantiago R.GurYonatan (2019), “Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium,” Management Science, 65 (9), 3952–68.
7.
CaiHanRenKanZhangWeinanMalialisKleanthisWangJunYuYong, et al. (2017), “Real-Time Bidding by Reinforcement Learning in Display Advertising,” in Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. Cambridge, UK: Association for Computing Machinery, 661–70.
ChapelleOlivierLiLihong (2011), “An Empirical Evaluation of Thompson Sampling,” Advances in Neural Information Processing Systems, 24, 2249–57.
10.
ChoiHanaMelaCarl F.BalseiroSantiago R.LearyAdam (2020), “Online Display Advertising Markets: A Literature Review and Future Directions,” Information Systems Research, 31 (2), 556–75.
11.
CormenThomas H.LeisersonCharles E.RivestRonald L.SteinClifford (2009), Introduction to Algorithms, 3rd ed. Boston: MIT Press.
12.
DanaherPeter J. (1991), “Optimizing Response Functions of Media Exposure Distributions,” Journal of the Operational Research Society, 42 (7), 537–42.
13.
DanaherPeter J.van HeerdeHarald. J. (2018), “Delusion in Attribution: Caveats in Using Attribution for Multimedia Budget Allocation,” Journal of Marketing Research, 55 (5), 667–85.
14.
DeanBrian C.GoemansMichel X.VondrákJan (2008), “Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity,” Mathematics of Operations Research, 33 (4), 945–64.
15.
DinnerIsaac M.Van HeerdeHarald J.NeslinScott A. (2014), “Driving Online and Offline Sales: The Cross-Channel Effects of Traditional, Online Display, and Paid Search Advertising,” Journal of Marketing Research, 50 (5), 527–45.
GordonBrett R.ZettelmeyerFlorianBhargavaNehaChapskyDan. (2019), “A Comparison of Approaches to Advertising Measurement: Evidence from Big Field Experiments at Facebook,” Marketing Science, 38 (2), 193–225.
21.
HeiseMarcAbou NaboutNadiaSkieraBernd (2016), “An Analysis of the Profitability of Even Pacing in Real-Time Bidding,” working paper, Goethe University.
KaufmannEmilieKordaNathanielMunosRémy (2012), “Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis,” in Algorithmic Learning Theory, BshoutyNader H.StoltzGillesVayatisNicolasZeugmannThomas, eds. Berlin: Springer, 199–213.
25.
KleywegtAnton J.PapastavrouJason D. (1998), “The Dynamic and Stochastic Knapsack Problem,” Operations Research, 46 (1), 17–35.
26.
LeeKuang-ChihJalaliAliDasdanAli (2013), “Real Time Bid Optimization with Smooth Budget Delivery in Online Advertising,” in Proceedings of the Seventh International Workshop on Data Mining for Online Advertising. Chicago: Association for Computing Machinery, 1–9.
27.
LeeflangPeter S.WittinkDick R. (2000), “Building Models for Marketing Decisions: Past, Present and Future,” International Journal of Research in Marketing, 17 (2/3), 105–26.
LiaoHairenPengLingxiaoLiuZhenchuanShenXuehua (2014), “iPinYou Global RTB Bidding Algorithm Competition Dataset,” Proceedings of the Eighth International Workshop on Data Mining for Online Advertising. New York: Association for Computing Machinery, 1–6.
30.
LittleJohn D. (1970), “Models and Managers: The Concept of a Decision Calculus,” Management Science, 16 (8), B466–85.
LuekerGeorge S. (1998), “Average-Case Analysis of Off-Line and On-Line Knapsack Problems,” Journal of Algorithms, 29 (2), 277–305.
33.
MantralaMurali K.SinhaPrabhakantZoltnersAndris A. (1992), “Impact of Resource Allocation Rules on Marketing Investment-level Decisions and Profitability,” Journal of Marketing Research, 29 (2), 162–75.
PasupathyRaghuKimSujin (2011), “The Stochastic Root-Finding Problem: Overview, Solutions, and Open Questions,” ACM Transactions on Modeling and Computer Simulation, 21 (3), 19.
37.
PaulsonCourtneyLuoLanJamesGareth M. (2018), “Efficient Large-Scale Internet Media Selection Optimization for Online Display Advertising,” Journal of Marketing Research, 55 (4), 489–506.
RustRoland T. (1986), Advertising Media Models: A Practical Guide. New York: The Free Press.
40.
SchwartzEric M.BradlowEric T.FaderPeter S. (2017), “Customer Acquisition Via Display Advertising Using Multi-Armed Bandit Experiments,” Marketing Science, 36 (4), 500–522.
41.
ShenJianqiangOrtenBurkayGeyikSahin C.LiuDanielShariatShahriarBianFang (2015) “From 0.5 Million to 2.5 Million: Efficiently Scaling Up Real-Time Bidding,” in 2015 IEEE International Conference on Data Mining (ICDM). Piscataway, NJ: Institute of Electrical and Electronics Engineers, 973–78.
ZeithammerRobert (2016), “The Futility of Soft Floor Auctions,” working paper.
49.
ZhangWeinanYuanShuaiWangJun (2014), “Optimal Real-Time Bidding for Display Advertising,” in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: Association for Computing Machinery, 1077–86.
50.
ZhangWeinanDuTianmingWangJun (2016), “Deep Learning over Multi-Field Categorical Data,” in European Conference on Information Retrieval. Padua, Italy: Springer, 45–57.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
