Computing Bayes–Nash Equilibrium Strategies in Auction Games via Simultaneous Online Dual Averaging

References

• Andrade GP, Frongillo R, Piliouras G (2021) Learning in matrix games can be arbitrarily complex. Preprint, submitted March 5, https://arxiv.org/abs/2103.03405.Google Scholar
• Anton JJ, Yao DA (1992) Coordination in split award auctions. Quart. J. Econom. 107(2):681–707.Crossref, Google Scholar
• Armantier O, Florens J-P, Richard J-F (2008) Approximation of Nash equilibria in Bayesian games. J. Appl. Econometrics 23(7):965–981.Crossref, Google Scholar
• Athey S (2001) Single crossing properties and the existence of pure strategy equilibria in games of incomplete information. Econometrica 69(4):861–889.Crossref, Google Scholar
• Ausubel LM, Baranov O (2020) Core-selecting auctions with incomplete information. Internat. J. Game Theory 49:251–273.Crossref, Google Scholar
• Bailey JP, Piliouras G (2018) Multiplicative weights update in zero-sum games. Proc. 2018 ACM Conf. Econom. Comput. (ACM, New York), 321–338.Google Scholar
• Balcan M-F, Blum A, Haghtalab N, Procaccia AD (2015) Commitment without regrets: Online learning in Stackelberg security games. Proc. 16th ACM Conf. Econom. Comput. (ACM, New York), 61–78.Google Scholar
• Beck A, Teboulle M (2003) Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3):167–175.Crossref, Google Scholar
• Benaim M, Hirsch MW (1999) Mixed equilibria and dynamical systems arising from fictitious play in perturbed games. Games Econom. Behav. 29(1–2):36–72.Crossref, Google Scholar
• Bichler M, Goeree JK (2017) Handbook of Spectrum Auction Design (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Bichler M, Guler K, Mayer S (2015) Split-award procurement auctions—Can Bayesian equilibrium strategies predict human bidding behavior in multi-object auctions? Production Oper. Management 24(6):1012–1027.Crossref, Google Scholar
• Bichler M, Kohring N, Heidekrüger S (2023) Learning equilibria in asymmetric auction games. INFORMS J. Comput. 35(3):523–542.Link, Google Scholar
• Bichler M, Fichtl M, Heidekrüger S, Kohring N, Sutterer P (2021) Learning equilibria in symmetric auction games using artificial neural networks. Nature Machine Intelligence 3:687–695.Crossref, Google Scholar
• Bosshard V, Bünz B, Lubin B, Seuken S (2020) Computing Bayes-Nash equilibria in combinatorial auctions with verification. J. Artificial Intelligence Res. 69:531–570.Crossref, Google Scholar
• Bowling M (2005) Convergence and no-regret in multiagent learning. Adv. Neural Inform. Processing Systems, 209–216.Google Scholar
• Brown GW (1951) Iterative solution of games by fictitious play. Activity Anal. Production Allocation 13(1):374–376.Google Scholar
• Brown N, Sandholm T (2019) Superhuman AI for multiplayer poker. Science 365(6456):885–890.Crossref, Google Scholar
• Cai Y, Papadimitriou C (2014) Simultaneous Bayesian auctions and computational complexity. Proc. 15th ACM Conf. Econom. Comput. (ACM, New York), 895–910.Google Scholar
• Campo S, Perrigne I, Vuong Q (2003) Asymmetry in first-price auctions with affiliated private values. J. Appl. Econometrics 18(2):179–207.Crossref, Google Scholar
• Cheung YK, Piliouras G (2020) Chaos, extremism and optimism: Volume analysis of learning in games. Preprint, submitted May 28, https://arxiv.org/abs/2005.13996.Google Scholar
• Dasgupta S, Spulber DF (1989) Managing procurement auctions. Inform. Econ. Policy 4(1):5–29.Crossref, Google Scholar
• Daskalakis C, Goldberg P, Papadimitriou C (2009) The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1):195–259.Crossref, Google Scholar
• Daskalakis C, Frongillo R, Papadimitriou CH, Pierrakos G, Valiant G (2010) On learning algorithms for Nash equilibria. Internat. Sympos. Algorithmic Game Theory (Springer, Berlin), 114–125.Google Scholar
• Debreu G (1952) A social equilibrium existence theorem. Proc. Natl. Acad. Sci. USA 38(10):886–893.Crossref, Google Scholar
• Even-Dar E, Mansour Y, Nadav U (2009) On the convergence of regret minimization dynamics in concave games. Proc. 41st Annual ACM Sympos. Theory Comput. (ACM, New York), 523–532.Google Scholar
• Facchinei F, Pang J-S (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Series in Operations Research, vol. 2 (Springer, New York).Google Scholar
• Fey M (2008) Rent-seeking contests with incomplete information. Public Choice 135(3):225–236.Crossref, Google Scholar
• Fibich G, Gavious A, Sela A (2006) All-pay auctions with risk-averse players. Internat. J. Game Theory 34(4):583–599.Crossref, Google Scholar
• Foster DP, Vohra RV (1997) Calibrated learning and correlated equilibrium. Games Econom. Behav. 21(1–2):40–55.Crossref, Google Scholar
• Foster DJ, Li Z, Lykouris T, Sridharan K, Tardos E (2016) Learning in games: Robustness of fast convergence. Adv. Neural Inform. Processing Systems, vol. 29 (Curran Associates, Inc., Red Hook, NY), 4734–4742.Google Scholar
• Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1–2):95–110.Crossref, Google Scholar
• Fudenberg D, Levine DK (2009) Learning and equilibrium. Annual Rev. Econom. 1(1):385–420.Crossref, Google Scholar
• Geiger C, Kanzow C (2002) Theorie und Numerik Restringierter Optimierungsaufgaben (Springer-Verlag, Berlin).Crossref, Google Scholar
• Glicksberg IL (1952) A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points. Proc. Amer. Math. Soc. 3(1):170–174.Google Scholar
• Goeree JK, Lien Y (2016) On the impossibility of core-selecting auctions. Theoretical Econom. 11(1):41–52.Crossref, Google Scholar
• Grossmann C, Roos H-G, Stynes M (2007) Numerical methods for variational inequalities and optimal control. Numerical Treatment of Partial Differential Equations: Translated and Revised by Martin Stynes (Springer, Berlin, Heidelberg), 435–498.Google Scholar
• Haimanko O (2021) Bayesian Nash equilibrium existence in (almost continuous) contests. Econom. Theory 71(3):1231–1258.Crossref, Google Scholar
• Hart S, Mas-Colell A (2000) A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5):1127–1150.Crossref, Google Scholar
• Hart S, Mas-Colell A (2003) Uncoupled dynamics do not lead to Nash equilibrium. Amer. Econom. Rev. 93(5):1830–1836.Crossref, Google Scholar
• Hartline J, Syrgkanis V, Tardos E (2015) No-regret learning in Bayesian games. Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 28 (Curran Associates, Inc., Red Hook, NY), 3061–3069.Google Scholar
• Hazan E, Kale S (2012) Projection-free online learning. Proc. 29th Internat. Conf. Machine Learn. (Omnipress, Madison, WI), 1843–1850.Google Scholar
• Jackson MO, Swinkels JM (2005) Existence of equilibrium in single and double private value auctions. Econometrica 73(1):93–139.Crossref, Google Scholar
• Jackson MO, Simon LK, Swinkels JM, Zame WR (2002) Communication and equilibrium in discontinuous games of incomplete information. Econometrica 70(5):1711–1740.Crossref, Google Scholar
• Jafari A, Greenwald A, Gondek D, Ercal G (2001) On no-regret learning, fictitious play, and Nash equilibrium. Internat. Conf. Machine Learn., vol. 1 (Morgan Kaufmann Publishers, Burlington, MA), 226–233.Google Scholar
• Juditsky A, Kwon J, Moulines É (2023) Unifying mirror descent and dual averaging. Math. Programming 199:793–830.Crossref, Google Scholar
• Kinderlehrer D, Stampacchia G (1980) An Introduction to Variational Inequalities and Their Applications (SIAM) (Academic Press, New York).Google Scholar
• Kokott G-M, Bichler M, Paulsen P (2019) The beauty of Dutch: Ex-post split-award auctions in procurement markets with diseconomies of scale. Eur. J. Oper. Res. 278(1):202–210.Crossref, Google Scholar
• Krishna V (2009) Auction Theory, 2nd ed. (Academic Press, Burlington, MA).Google Scholar
• Letcher A, Balduzzi D, Racanière S, Martens J, Foerster JN, Tuyls K, Graepel T (2019) Differentiable game mechanics. J. Machine Learn. Res. 20(84):1–40.Google Scholar
• Maskin E, Riley J (1984) Optimal auctions with risk averse buyers. Econometrica 52(6):1473–1518.Crossref, Google Scholar
• McAfee RP, McMillan J (1987) Auctions and bidding. J. Econom. Literature 25(2):699–738.Google Scholar
• Mertikopoulos P, Zhou Z (2019) Learning in games with continuous action sets and unknown payoff functions. Math. Programming 173(1–2):465–507.Crossref, Google Scholar
• Mertikopoulos P, Papadimitriou C, Piliouras G (2018) Cycles in adversarial regularized learning. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 2703–2717.Google Scholar
• Milgrom PR, Weber RJ (1985) Distributional strategies for games with incomplete information. Math. Oper. Res. 10(4):619–632.Link, Google Scholar
• Nash JF (1950) Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA 36(1):48–49.Crossref, Google Scholar
• Nemirovskij AS, Yudin DB (1983) Problem Complexity and Method Efficiency in Optimization (Wiley, Hoboken, NJ).Google Scholar
• Nesterov Y (2009) Primal-dual subgradient methods for convex problems. Math. Programming 120(1):221–259.Crossref, Google Scholar
• Rabinovich Z, Naroditskiy V, Gerding EH, Jennings NR (2013) Computing pure Bayesian-Nash equilibria in games with finite actions and continuous types. Artificial Intelligence 195:106–139.Crossref, Google Scholar
• Rasooly I, Gavidia-Calderon C (2022) The importance of being discrete: On the inaccuracy of continuous approximations in auction theory. Preprint, submitted August 16, https://arxiv.org/abs/2006.03016.Google Scholar
• Reny PJ (2011) On the existence of monotone pure-strategy equilibria in Bayesian games. Econometrica 79(2):499–553.Crossref, Google Scholar
• Reny PJ (2020) Nash equilibrium in discontinuous games. Annual Rev. Econom. 12:439–470.Crossref, Google Scholar
• Rosen JB (1965) Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33(3):520–534.Crossref, Google Scholar
• Ryvkin D (2010) Contests with private costs: Beyond two players. Eur. J. Political Econom. 26(4):558–567.Crossref, Google Scholar
• Sanders JBT, Farmer JD, Galla T (2018) The prevalence of chaotic dynamics in games with many players. Scientific Rep. 8(1):1–13.Crossref, Google Scholar
• Sandholm T (2015) Abstraction for solving large incomplete-information games. 29th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA).Google Scholar
• Shalev-Shwartz S (2007) Online learning: Theory, algorithms, and applications. Ph.D. thesis, Hebrew University of Jerusalem, Jerusalem, Israel.Google Scholar
• Shalev-Shwartz S (2012) Online learning and online convex optimization. Foundations Trends Machine Learn. 4(2):107–194.Google Scholar
• Shoham Y, Leyton-Brown K (2008) Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Singh S, Kearns M, Mansour Y (2013) Nash convergence of gradient dynamics in iterated general-sum games. Preprint, submitted January 16, http://arxiv.org/abs/1301.3892.Google Scholar
• Stoltz G, Lugosi G (2007) Learning correlated equilibria in games with compact sets of strategies. Games Econom. Behav. 59(1):187–208.Crossref, Google Scholar
• Syrgkanis V, Agarwal A, Luo H, Schapire RE (2015) Fast convergence of regularized learning in games. Adv. Neural Inform. Processing Systems, vol. 28 (Curran Associates, Inc., Red Hook, NY).Google Scholar
• Tullock G (1980) Efficient rent seeking. Buchanan JM, Tollison RD, Tullock G, eds. Toward a Theory of the Rent Seeking Society (A&M University Press, College Station, TX), 97–112.Google Scholar
• Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1):8–37.Crossref, Google Scholar
• Viossat Y, Zapechelnyuk A (2013) No-regret dynamics and fictitious play. J. Econom. Theory 148(2):825–842.Crossref, Google Scholar
• Vlatakis-Gkaragkounis E-V, Flokas L, Lianeas T, Mertikopoulos P, Piliouras G (2020) No-regret learning and mixed Nash equilibria: They do not mix. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates, Inc., Red Hook, NY), 1380–1391.Google Scholar
• Vojnović M (2016) Contest Theory: Incentive Mechanisms and Ranking Methods (Cambridge University Press, Cambridge, UK).Google Scholar
• Zinkevich M (2003) Online convex programming and generalized infinitesimal gradient ascent. Proc. 20th Internat. Conf. Machine Learn. (AAAI Press, Palo Alto, CA), 928–936.Google Scholar