The Cut-and-Play Algorithm: Computing Nash Equilibria via Outer Approximations

References

• Balas E (1985) Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebraic Discrete Methods 6(3):466–486.Crossref, Google Scholar
• Balas E (1998) Disjunctive programming: Properties of the convex hull of feasible points. Discrete Appl. Math. 89(1–3):3–44.Crossref, Google Scholar
• Basu A, Ryan CT, Sankaranarayanan S (2019) Mixed-integer bilevel representability. Math. Programming 185:163–197.Crossref, Google Scholar
• Bixby RE (2002) Solving real-world linear programs: A decade and more of progress. Oper. Res. 50(1):3–15.Link, Google Scholar
• Carvalho M, Lodi A, Pedroso JP (2018a) Existence of Nash equilibria on integer programming games. Vaz AIF, Almeida JP, Oliveira JF, Pinto AA, eds. Operational Research, vol. 223 (Springer International Publishing, Cham, Switzerland), 11–23.Crossref, Google Scholar
• Carvalho M, Lodi A, Pedroso JP (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 (2023a) Integer Programming Games: A Gentle Computational Overview, TutORials in Operations Research (INFORMS), 31–51.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
• Carvalho M, Pedroso JP, Telha C, Van Vyve M (2018b) Competitive uncapacitated lot-sizing game. Internat. J. Production Econom. 204:148–159.Crossref, Google Scholar
• Carvalho M, Dragotto G, Feijoo F, Lodi A, Sankaranarayanan S (2023b) When Nash meets Stackelberg. Management Sci. 70(10):7308–7324.Link, Google Scholar
• Chvátal V, Cook W, Espinoza D (2013) Local cuts for mixed-integer programming. Math. Programming Comput. 5(2):171–200.Crossref, Google Scholar
• Coin-OR (2023) The COIN-OR cut generation library. Accessed May 20, 2021, https://github.com/coin-or/Cgl.Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2010) Extended formulations in combinatorial optimization. 4OR 8(1):1–48. Crossref, Google Scholar
• Cottle R, Pang JS, Stone RE (2009) The Linear Complementarity Problem, Classics in Applied Mathematics (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Crönert T, Minner S (2021) Location selection for hydrogen fuel stations under emerging provider competition. Transportation Res. Part C: Emerging Tech. 133:103426.Crossref, Google Scholar
• Crönert T, Minner S (2022) Equilibrium identification and selection in finite games. Oper. Res. 72(2):816–831.Link, Google Scholar
• Dantzig GB (1951) A proof of the equivalence of the programming problem and the game problem. Koopmans TC, ed. Activity Analysis of Production and Allocation, vol. 13 (Wiley and Sons, New York).Google Scholar
• Daskalakis C (2022) Non-concave games: A challenge for game theory’s next 100 years. Accessed June 25, 2025, https://cowles.yale.edu/sites/default/files/2022-10/nonconvex-games-non-concave-utilities-and-machine-learning.pdf.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
• Dey SS, Molinaro M, Wang Q (2015) Approximating polyhedra with sparse inequalities. Math. Programming 154(1–2):329–352.Crossref, Google Scholar
• Dirkse SP, Ferris MC (1995) The PATH solver: A nommonotone stabilization scheme for mixed complementarity problems. Optim. Methods Software 5(2):123–156.Crossref, Google Scholar
• Dragotto G, Scatamacchia R (2023) The zero regrets algorithm: Optimizing over pure Nash equilibria via integer programming. INFORMS J. Comput. 35(5):1143–1160.Link, Google Scholar
• Dragotto G, Boukhtouta A, Lodi A, Taobane M (2023) The critical node game. J. Combinatorial Optim. 47(5):74.Google Scholar
• Dragotto G, Sankaranarayanan S, Carvalho M, Lodi A (2021) ZERO: Playing mathematical programming games. Preprint, submitted December 12, https://arxiv.org/abs/2111.07932.Google Scholar
• Dresher M, Karlin S (1953) Solutions of convex games as fixed points. Kuhn HW, Tucker AW, eds. Contributions to the Theory of Games, vol. II (Princeton University Press, Princeton, NJ), 75–86.Crossref, Google Scholar
• Dresher M, Karlin S, Shapley LS (1952) Polynomial games. Kuhn HW, Tucker AW, eds. Contributions to the Theory of Games, vol. I (Princeton University Press, Princeton, NJ), 161–180.Google Scholar
• Facchinei F, Pang JS (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Series in Operations Research (Springer, New York).Google Scholar
• Ferris MC, Munson TS (1999) Interfaces to PATH 3.0: Design, implementation and usage. Comput. Optim. Appl. 12(1/3):207–227. Crossref, Google Scholar
• Fischetti M, Lodi A, Tramontani A (2011) On the separation of disjunctive cuts. Math. Programming 128(1–2):205–230.Crossref, Google Scholar
• Fuller JD, Pirnia M (2022) Nonconvex multicommodity near equilibrium models: Energy markets perspective. Oper. Res. Perspectives 9:100243.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.Google Scholar
• Harks T, Schwarz J (2021) Generalized Nash equilibrium problems with mixed-integer variables. Preprint, submitted July 21, https://arxiv.org/abs/2107.13298.Google Scholar
• Hu X, Ralph D (2007) Using EPECs to model bilevel games in restructured electricity markets with locational prices. Oper. Res. 55(5):809–827.Link, Google Scholar
• Kleinert T, Schmidt M (2023) Why there is no need to use a big-M in linear bilevel optimization: A computational study of two ready-to-use approaches. Comput. Management Sci. 20(1):3–1619.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
• Lamas A, Chevalier P (2018) Joint dynamic pricing and lot-sizing under competition. Eur. J. Oper. Res. 266(3):864–876.Crossref, Google Scholar
• Lemke CE, Howson JT Jr (1964) Equilibrium points of bimatrix games. J. Soc. Indrustrial Appl. Math. 12(2):413–423.Crossref, Google Scholar
• Nash J (1951) Non-cooperative games. Ann. Math. 54(2):286–295.Crossref, Google Scholar
• Nash JF (1950) Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA 36(1):48–49.Crossref, Google Scholar
• Nowak D (2021) Nonconvex Nash games: Solution concepts and algorithms. PhD thesis, Technische Universität, Darmstadt, Germany.Google Scholar
• Padberg M, Rinaldi G (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33(1):60–100.Crossref, Google Scholar
• Pang JS, Fukushima M (2005) Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Management Sci. 2(1):21–56.Crossref, Google Scholar
• Pang JS, Scutari G (2011) Nonconvex games with side constraints. SIAM J. Optim. 21(4):1491–1522.Crossref, Google Scholar
• Perregaard M, Balas E (2001) Generating cuts from multiple-term disjunctions. Goos G, Hartmanis J, van Leeuwen J, Aardal K, Gerards B, eds. Integer Programming and Combinatorial Optimization, vol. 2081 (Springer, Berlin), 348–360.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
• Rosenmüller J (1971) On a generalization of the Lemke–Howson algorithm to noncooperative n-person games. SIAM J. Appl. Math. 21(1):73–79.Crossref, Google Scholar
• Roth AE (2002) The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica 70(4):1341–1378.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
• Sagratella S, Schmidt M, Sudermann-Merx N (2020) The noncooperative fixed charge transportation problem. Eur. J. Oper. Res. 284(1):373–382.Crossref, Google Scholar
• Sandholm T, Gilpin A, Conitzer V (2005) Mixed-integer programming methods for finding Nash equilibria. Proc. 20th Natl. Conf. Artificial Intelligence, vol. 2 (AAAI Press, Pittsburgh, PA), 495–501.Google Scholar
• Schwarze S, Stein O (2023) A branch-and-prune algorithm for discrete Nash equilibrium problems. Comput. Optim. Appl. 86(2):491–519.Crossref, Google Scholar
• Sherali HD (1984) A multiple leader Stackelberg model and analysis. Oper. Res. 32(2):390–404.Link, Google Scholar
• Stein ND, Ozdaglar A, Parrilo PA (2008) Separable and low-rank continuous games. Int. J. Game Theory 37(4):475–504.Crossref, Google Scholar
• von Neumann J (1928) Zur theorie der gesellschaftsspiele. Math. Ann. 100(1):295–320.Crossref, Google Scholar
• Wilson R (1971) Computing equilibria of n-person games. SIAM J. Appl. Math. 21(1):80–87.Crossref, Google Scholar
• Woeginger GJ (2021) The trouble with the second quantifier. 4OR 19(2):157–181.Crossref, Google Scholar