The Complexity of Pacing for Second-Price Auctions

References

• [1] Ashlagi I, Braverman M, Hassidim A, Lavi R, Tennenholtz M (2010) Position auctions with budgets: Existence and uniqueness. The BE J. Theoret. Econom. 10(1):1–32.Google Scholar
• [2] 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 in Theoret. Comput. Sci. Conf. (ITCS 2021), Leibniz International Proceedings in Informatics (LIPIcs), vol. 185 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 84:1–84:1.Google Scholar
• [3] Balseiro S, Kim A, Mahdian M, Mirrokni V (2021) Budget-management strategies in repeated auctions. Oper. Res. 69(3):859–876.Link, Google Scholar
• [4] Balseiro SR, Gur Y (2019) Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Sci. 65(9):3952–3968.Link, Google Scholar
• [5] 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
• [6] Balseiro SR, Kroer C, Kumar R (2022) Contextual standard auctions with budgets: Revenue equivalence and efficiency guarantees. Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 476–476.Google Scholar
• [7] Bei X, Garg J, Hoefer M, Mehlhorn K (2016) Computing equilibria in markets with budget-additive utilities. Sankowski P, Zaroliagis C, eds. 24th Annual Eur. Sympos. Algorithms (ESA 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 57 (Schloss Dagstuhl–Leibniz-Zentrum fur Informatik, Dagstuhl, Germany), 8:1–8:14.Google Scholar
• [8] Bitansky N, Paneth O, Rosen A (2015) On the cryptographic hardness of finding a Nash equilibrium. Guruswami V, ed. IEEE 56th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 1480–1498.Google Scholar
• [9] Borgs C, Chayes J, Immorlica N, Jain K, Etesami O, Mahdian M (2007) Dynamics of bid optimization in online advertisement auctions. Proc. 16th Internat. Conf. World Wide Web (ACM, New York), 531–540.Google Scholar
• [10] Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061–1103.Crossref, Google Scholar
• [11] Chen X, Deng X (2006) Settling the complexity of two-player Nash equilibrium. 2006 47th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS’06) (IEEE, Piscataway, NJ), 261–272.Google Scholar
• [12] Chen X, Deng X (2009) On the complexity of 2d discrete fixed point problem. Theoret. Comput. Sci. 410(44):4448–4456.Crossref, Google Scholar
• [13] Chen X, Teng SH (2009) Spending is not easier than trading: On the computational equivalence of Fisher and Arrow-Debreu equilibria. Dong Y, Du D-Z, eds. Algorithms and Computation (Springer, Berlin, Heidelberg), 647–656.Google Scholar
• [14] Chen X, Kroer C, Kumar R (2021) Throttling equilibria in auction markets. Feldman M, Fu H, Talgam-Cohen I, eds. Web and Internet Econom. – 17th Internat. Conf. (WINE), Lecture Notes in Computer Science, vol. 13112 (Springer, Cham, Switzerland), 551.Google Scholar
• [15] Chen X, Paparas D, Yannakakis M (2017) The complexity of non-monotone markets. J. ACM. 64(3):1–56.Crossref, Google Scholar
• [16] Chen X, Teng SH, Valiant P (2007) The approximation complexity of win-lose games. Proc. 18th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 159–168.Google Scholar
• [17] Choudhuri AR, Hubáček P, Kamath C, Pietrzak K, Rosen A, Rothblum GN (2019) Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 1103–1114.Google Scholar
• [18] Conitzer V, Kroer C, Sodomka E, Stier-Moses NE (2022a) Multiplicative pacing equilibria in auction markets. Oper. Res. 70(2):963–989.Link, Google Scholar
• [19] Conitzer V, Kroer C, Panigrahi D, Schrijvers O, Stier-Moses NE, Sodomka E, Wilkens CA (2022b) Pacing equilibrium in first price auction markets. Management Sci. 68(12):8515–8535.Link, Google Scholar
• [20] Daskalakis C, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1):195–259.Crossref, Google Scholar
• [21] Deng X, Qi Q, Saberi A (2012) Algorithmic solutions for envy-free cake cutting. Oper. Res. 60(6):1461–1476.Link, Google Scholar
• [22] Dobzinski S, Leme RP (2014) Efficiency guarantees in auctions with budgets. Esparza J, Fraigniaud P, Husfeldt T, Koutsoupias E, eds. Automata, Languages, and Programming (Springer, Berlin, Heidelberg), 392–404.Google Scholar
• [23] Dobzinski S, Lavi R, Nisan N (2012) Multi-unit auctions with budget limits. Games Econom. Behav. 74(2):486–503.Crossref, Google Scholar
• [24] Etessami K, Yannakakis M (2010) On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6):2531–2597.Crossref, Google Scholar
• [25] Facebook (2017) Your guide to Facebook bid strategy. Accessed June 30, 2021, https://www.facebook.com/gms_hub/share/biddingstrategyguide_final.pdf.Google Scholar
• [26] Fearnley J, Goldberg PW, Hollender A, Savani R (2021) The complexity of gradient descent: CLS = PPAD ∩ PLS. J. ACM 70(1):1–74.Google Scholar
• [27] Filos-Ratsikas A, Hollender A, Sotiraki K, Zampetakis M (2023) Consensus-halving: Does it ever get easier? SIAM J. Comput. 52(2):412–451.Google Scholar
• [28] Filos-Ratsikas A, Giannakopoulos Y, Hollender A, Lazos P, Poças D (2023) On the complexity of equilibrium computation in first-price auctions. SIAM J. Comput. 52(1):80–131.Google Scholar
• [29] Garg S, Pandey O, Srinivasan A (2016) Revisiting the cryptographic hardness of finding a Nash equilibrium. Proc. 36th Annual Internat. Cryptology Conf. Adv. Cryptol. (Springer, Berlin, Heidelberg), 579–604.Google Scholar
• [30] Goel G, Mirrokni V, Leme RP (2015) Polyhedral clinching auctions and the adwords polytope. J. ACM. 62(3):1–27.Crossref, Google Scholar
• [31] Goldberg PW (2011) A survey of PPAD-completeness for computing Nash equilibria. Preprint, submitted March 14, https://arxiv.org/abs/1103.2709.Google Scholar
• [32] Hubáček P, Yogev E (2020) Hardness of continuous local search: Query complexity and cryptographic lower bounds. SIAM J. Comput. 49(6):1128–1172.Google Scholar
• [33] Kuhn HW (1960) Some combinatorial lemmas in topology. IBM J. Res. Develop. 4(5):518–524.Crossref, Google Scholar
• [34] Li J, Tang P (2022) Auto-bidding equilibrium in ROI-constrained online advertising markets. Preprint, submitted October 12, https://arxiv.org/abs/2210.06107.Google Scholar
• [35] Mehta A (2013) Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• [36] Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM. 54(5):22.Crossref, Google Scholar
• [37] Othman A, Papadimitriou C, Rubinstein A (2016) The complexity of fairness through equilibrium. ACM Trans. Econom. Comput. 4(4):1–19.Crossref, Google Scholar
• [38] Papadimitriou CH (1994) On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci. 48(3):498–532.Crossref, Google Scholar
• [39] Rosen A, Segev G, Shahaf I (2021) Can PPAD hardness be based on standard cryptographic assumptions? J. Cryptology 34(1):8.Google Scholar
• [40] Roughgarden T (2020) Complexity theory, game theory, and economics: The Barbados lectures. Found. Trends Theor. Comput. Sci. 14(3–4):222–407.Crossref, Google Scholar
• [41] Vazirani VV, Yannakakis M (2011) Market equilibrium under separable, piecewise-linear, concave utilities. J. ACM. 58(3):1–25.Crossref, Google Scholar