Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees

References

• Abhishek V, Hosanagar K (2013) Optimal bidding in multi-item multislot sponsored search auctions. Oper. Res. 61(4):855–873.Link, Google Scholar
• Aggarwal G, Badanidiyuru A, Mehta A (2019) Autobidding with constraints. Caragiannis I, Mirrokni VS, Nikolova E, eds. Web Internet Econom. 15th Internat. Conf. Proc. (Springer, Cham, Switzerland), 17–30.Google Scholar
• Aliprantis CD, Border KC (2006) Infinite Dimensional Analysis: A Hitchhiker’s Guide (Springer Science & Business Media).Google Scholar
• Azar Y, Feldman M, Gravin N, Roytman A (2017) Liquid price of anarchy. Internat. Sympos. Algorithmic Game Theory (Springer, Cham, Switzerland), 3–15.Google Scholar
• Babaioff M, Cole R, Hartline JD, Immorlica N, Lucier B (2021) Non-quasi-linear agents in quasi-linear mechanisms (extended abstract). Lee JR, ed. 12th Innovations Theoretical Comput. Sci. Conf. (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 84:1–84:1.Google Scholar
• Balseiro S, Kim A, Mahdian M, Mirrokni V (2021) Budget-management strategies in repeated auctions. Oper. Res. 69(3):859–876.Link, Google Scholar
• Balseiro SR, Gur Y (2019) Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Sci. 65(9):3952–3968.Link, Google Scholar
• Balseiro SR, Besbes O, Weintraub GY (2015) Repeated auctions with budgets in ad exchanges: Approximations and design. Management Sci. 61(4):864–884.Link, Google Scholar
• Bertsekas DP, Hager WW, Mangasarian OL (1998) Nonlinear Programming (Athena Scientific, Belmont, MA).Google Scholar
• Bigler J (2021) Rolling out first price auctions to Google Ad Manager partners. Accessed February 17, 2021, https://www.blog.google/products/admanager/rolling-out-first-price-auctions-google-ad-manager-partners/.Google Scholar
• Borgs C, Chayes J, Immorlica N, Jain K, Etesami O, Mahdian M (2007) Dynamics of bid optimization in online advertisement auctions. Williamson CL, Zurko ME, Patel-Schneider PF, Shenoy PJ, eds. Proc. 16th Internat. Conf. World Wide Web (ACM, New York), 531–540.Google Scholar
• Che Y-K, Gale I (1998) Standard auctions with financially constrained bidders. Rev. Econom. Stud. 65(1):1–21.Crossref, Google Scholar
• Chen X, Kroer C, Kumar R (2021a) The complexity of pacing for second-price auctions. Biró P, Chawla S, Echenique F, eds. 22nd ACM Conf. Econom. Comput. (ACM, New York), 318.Google Scholar
• Chen X, Owen Z, Pixton C, Simchi-Levi D (2021b) A statistical learning approach to personalization in revenue management. Management Sci. 68(3):1923–1937.Link, Google Scholar
• Ciocan DF, Iyer K (2021) Tractable equilibria in sponsored search with endogenous budgets. Oper. Res. 69(1):227–244.Link, Google Scholar
• Conitzer V, Kroer C, Sodomka E, Stier Moses NE (2022a) Multiplicative pacing equilibria in auction markets. Oper. Res. 70(2):963–989.Google Scholar
• Conitzer V, Kroer C, Panigrahi D, Schrijvers O, Sodomka E, Stier-Moses NE, Wilkens C (2022b) Pacing equilibrium in first-price auction markets. Management Sci. 68(12): 8515–8535.Google Scholar
• Dobzinski S, Leme RP (2014) Efficiency guarantees in auctions with budgets. Esparza J, Fraigniaud P, Husfeldt T, Koutsoupias E, eds. Internat. Colloquium Automata Languages Programming (Springer, Berlin), 392–404.Google Scholar
• Evans LC, Gariepy RF (2015) Measure Theory and Fine Properties of Functions (CRC Press, New York).Crossref, Google Scholar
• Goel G, Mirrokni V, Leme RP (2015) Polyhedral clinching auctions and the AdWords polytope. J. ACM 62(3):1–27.Crossref, Google Scholar
• Goke S, Weintraub GY, Mastromonaco R, Seljan S (2021) Learning new auction format by bidders in internet display ad auctions. Preprint, submitted October 20, https://arxiv.org/abs/2007.00514.Google Scholar
• Golrezaei N, Javanmard A, Mirrokni V (2021) Dynamic incentive-aware learning: Robust pricing in contextual auctions. Oper. Res. 69(1):297–314.Link, Google Scholar
• Gummadi R, Key P, Proutiere A (2011) Repeated auctions under budget constraints: Optimal bidding strategies and equilibria. 49th Annual Allerton Conference on Communication, Control, and Computing (IEEE, Piscataway, NJ), 588.Google Scholar
• Iyer K, Johari R, Sundararajan M (2014) Mean field equilibria of dynamic auctions with learning. Management Sci. 60(12):2949–2970.Link, Google Scholar
• Kotowski MH (2020) First-price auctions with budget constraints. Theoretical Econom. 15(1):199–237.Crossref, Google Scholar
• Koutsoupias E, Papadimitriou C (2009) Worst-case equilibria. Comput. Sci. Rev. 3(2): 65–69.Google Scholar
• Krishna V (2009) Auction Theory (Academic Press, Cambridge, MA).Google Scholar
• Kroer C, Peysakhovich A, Sodomka E, Stier-Moses NE (2022) Computing large market equilibria using abstractions. Oper. Res. 70(1):329–351.Google Scholar
• Langford J, Zhang T (2007) The epoch-greedy algorithm for contextual multi-armed bandits. Platt J, Koller D, Singer Y, Roweis S, eds. Adv. Neural Inform. Processing Systems vol 20, (Curran Associates, Inc., Red Hook, NY).Google Scholar
• Li L, Chu W, Langford J, Schapire RE (2010) A contextual-bandit approach to personalized news article recommendation. Rappa M, Jones P, Freire J, Chakrabarti S, eds. Proc. 19th Internat. Conf. World Wide Web (ACM, New York), 661–670.Google Scholar
• Lobel I, Leme RP, Vladu A (2018) Multidimensional binary search for contextual decision-making. Oper. Res. 66(5):1346–1361.Link, Google Scholar
• McMahan HB, Holt G, Sculley D, Young M, Ebner D, Grady J, Nie L, Phillips T, Davydov E, Golovin D, et al. (2013) Ad click prediction: A view from the trenches. Dhillon IS, Koren Y, Ghani R, Senator TE, Bradley P, Parekh R, He J, Grossman RL, Uthurusamy R, eds. Proc. 19th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 1222–1230.Google Scholar
• Mehta A (2013) Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4):265–368.Google Scholar
• Pai MM, Vohra R (2014) Optimal auctions with financially constrained buyers. J. Econom. Theory 150:383–425.Crossref, Google Scholar
• Roughgarden T, Syrgkanis V, Tardos E (2017) The price of anarchy in auctions. J. Artificial Intelligence Res. 59(1):59–101.Crossref, Google Scholar
• Schmeidler D (1973) Equilibrium points of nonatomic games. J. Statist. Phys. 7(4):295–300.Crossref, Google Scholar
• Talluri KT, Van Ryzin GJ (2006) The Theory and Practice of Revenue Management, vol. 68 (Springer Science & Business Media, Berlin).Google Scholar