The Zero Regrets Algorithm: Optimizing over Pure Nash Equilibria via Integer Programming

References

• Aboolian R, Berman O, Krass D (2007) Competitive facility location and design problem. Eur. J. Oper. Res. 182(1):40–62.Crossref, Google Scholar
• Anderson E, Chen B, Shao L (2017) Supplier competition with option contracts for discrete blocks of capacity. Oper. Res. 65(4):952–967.Link, Google Scholar
• Anshelevich E, Dasgupta A, Tardos E, Wexler T (2003) Near-optimal network design with selfish agents. Proc. 35th ACM Sympos. Theory Comput. (ACM, New York), 511–520.Google Scholar
• Anshelevich E, Dasgupta A, Kleinberg J, Tardos E, Wexler T, Roughgarden T (2008) The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4):1602–1623.Crossref, Google Scholar
• Audet C, Belhaiza S, Hansen P (2006) Enumeration of all the extreme equilibria in game theory: Bimatrix and polymatrix games. J. Optim. Theory Appl. 129(3):349–372.Crossref, Google Scholar
• Avis D, Rosenberg GD, Savani R, von Stengel B (2010) Enumeration of Nash equilibria for two-player games. Econom. Theory 42(1):9–37.Crossref, Google Scholar
• Beck M, Stein O (2023) Semi-infinite models for equilibrium selection. Minimax Theory Appl. Forthcoming.Google Scholar
• Bernheim BD (1984) Rationalizable strategic behavior. Econometrica 52(4):1007–1028.Crossref, Google Scholar
• Bikhchandani S, Mamer JW (1997) Competitive equilibrium in an exchange economy with indivisibilities. J. Econom. Theory 74(2):385–413.Crossref, Google Scholar
• Caprara A, Carvalho M, Lodi A, Woeginger GJ (2014) A study on the computational complexity of the bilevel knapsack problem. SIAM J. Optim. 24(2):823–838.Crossref, Google Scholar
• Carvalho M (2016) Computation of equilibria on integer programming games. Unpublished PhD thesis, Universidade do Porto, Porto, Portugal.Google Scholar
• Carvalho M, Lodi A, Pedroso J (2018) Existence of Nash equilibria on integer programming games. Vaz AIF, Almeida JaP, Oliveira JF, Pinto AA, eds. Proc. Oper. Res., APDIO 2017 vol. 223 (Springer International Publishing, Cham, Switzerland), 11–23.Crossref, Google Scholar
• Carvalho M, Lodi A, Pedroso J (2022) Computing equilibria for integer programming games. Eur. J. Oper. Res. 303(3):1057–1070.Crossref, Google Scholar
• Carvalho M, Dragotto G, Lodi A, Sankaranarayanan S (2021) The cut and play algorithm: Computing Nash equilibria via outer approximations. Preprint, submitted November 10, https://arxiv.org/abs/2111.05726.Google Scholar
• Carvalho M, Lodi A, Pedroso JP, Viana A (2017) Nash equilibria in the two-player kidney exchange game. Math. Programming 161(1–2):389–417.Crossref, Google Scholar
• Chen HL, Roughgarden T (2006) Network design with weighted players. Proc. 18th Annual ACM Sympos. Parallelism Algorithms Architectures (ACM, New York), 29–38.Google Scholar
• Chvátal V (1973) Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4(4):305–337.Crossref, Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming, Graduate Texts in Mathematics, vol. 271 (Springer International Publishing, Cham, Switzerland).Crossref, Google Scholar
• Crönert T, Minner S (2023) Equilibrium identification and selection in finite games. Oper. Res. Forthcoming.Google Scholar
• Daskalakis C, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. Comm. ACM 52(2):89–97.Crossref, Google Scholar
• David Fuller J, Çelebi E (2017) Alternative models for markets with nonconvexities. Eur. J. Oper. Res. 261(2):436–449.Crossref, Google Scholar
• Della Croce F, Scatamacchia R (2020) An exact approach for the bilevel knapsack problem with interdiction constraints and extensions. Math. Programming 183:249–281.Crossref, Google Scholar
• Del Pia A, Ferris M, Michini C (2017) Totally unimodular congestion games. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 577–588. Google Scholar
• DeNegre S (2011) Interdiction and discrete bilevel linear programming. Unpublished PhD thesis, Lehigh University, Bethlehem, PA.Google Scholar
• Dragotto G, Sankaranarayanan S, Carvalho M, Lodi A (2021) ZERO: Playing mathematical programming games. Preprint, submitted November 15, https://arxiv.org/abs/2111.07932.Google Scholar
• Facchinei F, Kanzow C (2007) Generalized Nash equilibrium problems. 4OR 5(3):173–210.Crossref, Google Scholar
• Facchinei F, Pang JS, eds. (2004) Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Series in Operations Research and Financial Engineering (Springer, New York).Google Scholar
• Federgruen A, Hu M (2015) Multi-product price and assortment competition. Oper. Res. 63(3):572–584.Link, Google Scholar
• Gabriel SA, Siddiqui SA, Conejo AJ, Ruiz C (2013) Solving discretely-constrained Nash-Cournot games with an application to power markets. Networks Spatial Econom. 13(3):307–326.Crossref, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197.Crossref, Google Scholar
• Harks T, Schwarz J (2022) Generalized Nash equilibrium problems with mixed-integer variables. Preprint, submitted, February 21 https://arxiv.org/abs/2107.13298.Google Scholar
• Harsanyi JC (1995) A new theory of equilibrium selection for games with complete information. Games Econom. Behav. 8(1):91–122.Crossref, Google Scholar
• Hemmecke R, Onn S, Weismantel R (2009) Nash-equilibria and N-fold integer programming. Preprint, submitted March 26, https://arxiv.org/abs/0903.4577.Google Scholar
• Karp R, Papadimitriou C (1982) On linear characterizations of combinatorial optimization problems. SIAM J. Comput. 11(4):620–632.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• Kleer P, Schäfer G (2021) Computation and efficiency of potential function minimizers of combinatorial congestion games. Math. Programming 190(1–2):523–560.Crossref, Google Scholar
• Köppe M, Ryan CT, Queyranne M (2011) Rational generating functions and integer programming games. Oper. Res. 59(6):1445–1460.Link, Google Scholar
• Koutsoupias E, Papadimitriou C (1999) Worst-case equilibria. Goos G, Hartmanis J, van Leeuwen J, Meinel C, Tison S, eds. STACS 99, vol. 1563 (Springer, Berlin, Heidelberg), 404–413.Crossref, Google Scholar
• McLennan A (2005) The expected number of Nash equilibria of a normal form game. Econometrica 73(1):141–174.Crossref, Google Scholar
• Nash JF (1950) Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA 36(1):48–49.Crossref, Google Scholar
• Nash JF (1951) Non-cooperative games. Ann. Math 54(2):286–295.Crossref, Google Scholar
• Nikaidô H, Isoda K (1955) Note on non-cooperative convex games. Pacific J. Math. 5(1):807–815.Crossref, Google Scholar
• Nisan N, Roughgarden T, Tardos E, Vazirani VV (2008) Algorithmic Game Theory (Cambridge University Press, Cambridge, UK).Google Scholar
• Pearce DG (1984) Rationalizable strategic behavior and the problem of perfection. Econometrica 52(4):1029–1050.Crossref, Google Scholar
• Porter R, Nudelman E, Shoham Y (2008) Simple search methods for finding a Nash equilibrium. Games Econom. Behav. 63(2):642–662.Crossref, Google Scholar
• Rosenberg GD (2005) Enumeration of all extreme equilibria of bimatrix games with integer pivoting and improved degeneracy check. CDAM Res. Report LSE-CDAM-2004-18 (London School of Economics Research Reports, London), 68.Google Scholar
• Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2(1):65–67.Crossref, Google Scholar
• Roughgarden T, Tardos E (2004) Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econom. Behav. 47(2):389–403.Crossref, Google Scholar
• Sagratella S (2016) Computing all solutions of Nash equilibrium problems with discrete strategy sets. SIAM J. Optim. 26(4):2190–2218.Crossref, Google Scholar
• Sandholm T, Gilpin A, Conitzer V (2005) Mixed-integer programming methods for finding Nash equilibria. Proc. 20th National Conf. Artificial Intelligence, vol. 2 (AAAI Press, Palo Alto, CA), 495–501.Google Scholar
• Schulz AS, Stier-Moses NE (2003) On the performance of user equilibria in traffic networks. Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 86–87.Google Scholar
• Schwarze S, Stein O (2022) A branch-and-prune algorithm for discrete Nash equilibrium problems. https://optimization-online.org/2022/03/8836/.Google Scholar
• Sherali HD, Adams WP (1999) A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Nonconvex Optimization and Its Applications, vol. 31 (Springer, Boston).Crossref, Google Scholar
• Tadelis S (2013) Game Theory: An Introduction (Princeton University Press, Princeton, NJ).Google Scholar
• Tardos E (2004) Network games. Proc. 36th Annual ACM Sympos. Theory Comput. (ACM, New York), 341–342.Google Scholar
• Vielma JP (2015) Mixed integer linear programming formulation techniques. SIAM Rev. 57(1):3–57.Crossref, Google Scholar