Liquid Welfare Guarantees for No-Regret Learning in Sequential Budgeted Auctions

References

• [1] Aggarwal G, Badanidiyuru A, Mehta A (2019) Autobidding with constraints. Caragiannis I, Mirrokni VS, Nikolova E, eds. Web and Internet Economics. WINE 2019, Lecture Notes in Computer Science, vol. 11920 (Springer, Cham, Switzerland), 17–30.Crossref, Google Scholar
• [2] Alcobendas M, Zeithammer R (2022) Adjustment of bidding strategies after a switch to first-price rules. Preprint, submitted February 16, http://dx.doi.org/10.2139/ssrn.4036006.Google Scholar
• [3] 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 Theoret. Comput. Sci. Conf. (ITCS 2021). Leibniz Internat. Proc. Inform. (LIPIcs), vol. 185 (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany), 84:1.Google Scholar
• [4] Badanidiyuru A, Kleinberg R, Slivkins A (2018) Bandits with knapsacks. J. Assoc. Comput. Machinery 65(3):1–55.Crossref, Google Scholar
• [5] Balseiro SR, Gur Y (2019) Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Sci. 65(9):3952–3968.Link, Google Scholar
• [6] Balseiro SR, Kroer C, Kumar R (2023) Contextual standard auctions with budgets: Revenue equivalence and efficiency guarantees. Management Sci. 69(11):6837–6854.Link, Google Scholar
• [7] Balseiro SR, Kim A, Mahdian M, Mirrokni VS (2021) Budget-management strategies in repeated auctions. Oper. Res. 69(3):859–876.Link, Google Scholar
• [8] Castiglioni M, Celli A, Kroer C (2022) Online learning with knapsacks: The best of both worlds. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Internat. Conf. Machine Learn. (ICML 2022), vol. 162 (PMLR, New York), 2767–2783.Google Scholar
• [9] Chen Z, Deng X, Li J, Wang C, Yang M (2022a) Budget-constrained auctions with unassured priors. Preprint, submitted March 31, https://arxiv.org/abs/2203.16816.Google Scholar
• [10] Chen Z, Wang C, Wang Q, Pan Y, Shi Z, Tang C, Cai Z, Ren Y, Zhu Z, Deng X (2022b) Dynamic budget throttling in repeated second-price auctions. Preprint, submitted July 11, https://arxiv.org/abs/2207.04690.Google Scholar
• [11] Choi H, Mela CF, Balseiro SR, Leary A (2020) Online display advertising markets: A literature review and future directions. Inform. Systems Res. 31(2):556–575.Link, Google Scholar
• [12] Conitzer V, Kroer C, Sodomka E, Moses NES (2022b) Multiplicative pacing equilibria in auction markets. Oper. Res. 70(2):963–989.Link, Google Scholar
• [13] Conitzer V, Kroer C, Panigrahi D, Schrijvers O, Moses NES, Sodomka E, Wilkens CA (2022a) Pacing equilibrium in first price auction markets. Management Sci. 68(12):8515–8535.Link, Google Scholar
• [14] Deng X, Hu X, Lin T, Zheng W (2022) Nash convergence of mean-based learning algorithms in first price auctions. Laforest F, Troncy R, Simperl E, Agarwal D, Gionis A, Herman I, Médini L, eds. WWW ‘22 ACM Web Conf. 2022 (Association for Computing Machinery, New York), 141–150.Google Scholar
• [15] Deng Y, Mao J, Mirrokni VS, Zuo S (2021) Toward efficient auctions in an auto-bidding world. Leskovec J, Grobelnik M, Najork M, Tang J, Zia L, eds. WWW ‘21 Web Conf. 2021 (Association for Computing Machinery, New York), 3965–3973.Google Scholar
• [16] Despotakis S, Ravi R, Sayedi A (2021) First-price auctions in online display advertising. J. Marketing Res. 58(5):888–907.Crossref, Google Scholar
• [17] Dobzinski S, Paes Leme R (2014) Efficiency guarantees in auctions with budgets. Esparza J, Fraigniaud P, Husfeldt T, Koutsoupias E, eds. Automata Languages Programming. ICALP 2014, Lecture Notes in Computer Science, vol. 8572 (Springer, Berlin, Heidelberg), 392–404.Google Scholar
• [18] eMarketer (2022) US digital ad spending. (November 1), https://www.emarketer.com/chart/261096/us-programmatic-digital-display-ad-spending-2020-2024-billions-change.Google Scholar
• [19] Feldman M, Fu H, Gravin N, Lucier B (2020) Simultaneous auctions without complements are (almost) efficient. Games Econom. Behav. 123:327–341.Crossref, Google Scholar
• [20] Feng Z, Guruganesh G, Liaw C, Mehta A, Sethi A (2021) Convergence analysis of no-regret bidding algorithms in repeated auctions. 35th AAAI Conf. Artificial Intelligence (AAAI 2021) (AAAI Press, Washington, DC), 5399–5406.Google Scholar
• [21] Fikioris G, Tardos É (2023) Approximately stationary bandits with knapsacks. Neu G, Rosasco L, eds. 36th Annual Conf. Learning Theory (COLT 2023), vol. 195 (PMLR, New York), 3758–3782.Google Scholar
• [22] Fotakis D, Lotidis K, Podimata C (2019) A bridge between liquid and social welfare in combinatorial auctions with submodular bidders. 33rd AAAI Conf. Artificial Intelligence (AAAI 2019) (AAAI Press, Washington, DC), 1949–1956.Google Scholar
• [23] Gaitonde J, Li Y, Light B, Lucier B, Slivkins A (2022) Budget pacing in repeated auctions: Regret and efficiency without convergence. Preprint, submitted May 18, https://arxiv.org/abs/2205.08674.Google Scholar
• [24] Immorlica N, Sankararaman KA, Schapire RE, Slivkins A (2022) Adversarial bandits with knapsacks. J. Assoc. Comput. Machinery 69(6):40:1–40:47.Crossref, Google Scholar
• [25] Kesselheim T, Singla S (2020) Online learning with vector costs and bandits with knapsacks. Abernethy JD, Agarwal S, eds. Conf. Learning Theory (COLT 2020), vol. 125 (PMLR, New York), 2286–2305.Google Scholar
• [26] Kolumbus Y, Nisan N (2022) Auctions between regret-minimizing agents. Laforest F, Troncy R, Simperl E, Agarwal D, Gionis A, Herman I, Médini L, eds. WWW ‘22 ACM Web Conf. 2022 (Association for Computing Machinery, New York), 100–111.Google Scholar
• [27] Leme RP, Syrgkanis V, Tardos É (2012) Sequential auctions and externalities. Rabani Y, ed. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (SODA 2012) (Society for Industrial and Applied Mathematics, Philadelphia), 869–886.Google Scholar
• [28] Lucier B, Pattathil S, Slivkins A, Zhang M (2023) Autobidders with budget and ROI constraints: Efficiency, regret, and pacing dynamics. Preprint, submitted January 30, https://arxiv.org/abs/2301.13306.Google Scholar
• [29] Slivkins A (2019) Introduction to multi-armed bandits. Foundations Trends Machine Learn. 12(1–2):1–286.Crossref, Google Scholar
• [30] Syrgkanis V, Tardos É (2013) Composable and efficient mechanisms. Boneh D, Roughgarden T, Feigenbaum J, eds. Sympos. Theory Comput. Conf. (STOC’13) (Association for Computing Machinery, New York), 211–220.Google Scholar
• [31] Wong M (2021) Moving adsense to a first-price auction. Google AdSense (October 7), https://blog.google/products/adsense/our-move-to-a-first-price-auction/.Google Scholar