Identifying Socially Optimal Equilibria Using Combinatorial Properties of Nash Equilibria in Bimatrix Games

References

• Ahmadi AA, Zhang J (2021) Semidefinite programming and Nash equilibria in bimatrix games. INFORMS J. Comput. 33(2):607–628.Abstract, Google Scholar
• Andersen K, Pochet Y (2010) Coefficient strengthening: A tool for reformulating mixed-integer programs. Math. Programming 122(1):121.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
• Audet C, Hansen P, Jaumard B, Savard G (2001) Enumeration of all extreme equilibria of bimatrix games. SIAM J. Sci. Comput. 23(1):323–338.Crossref, Google Scholar
• Aumann RJ (1974) Subjectivity and correlation in randomized strategies. J. Math. Econom. 1(1):67–96.Crossref, Google Scholar
• Avis D, Fukuda K (1992) A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geometry 8(3):295–313.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
• Bai L, Rubin PA (2009) Combinatorial Benders cuts for the minimum tollbooth problem. Oper. Res. 57(6):1510–1522.Link, Google Scholar
• Barvinok A, Woods K (2003) Short rational generating functions for lattice point problems. J. Amer. Math. Soc. 16(4):957–979.Crossref, Google Scholar
• Bazaraa MS, Jarvis JJ, Sherali HD (2011) Linear Programming and Network Flows (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerical Math. 4(1):238–252.Crossref, Google Scholar
• Braverman M, Chen J, Kannan S (2016) Optimal provision-after-wait in healthcare. Math. Oper. Res. 41(1):352–376.Link, 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 (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
• Charnes A, Cooper W (1961) Management Models and Industrial Applications of Linear Programming, vol. I (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Chen X, Deng X (2006) Settling the complexity of two-player Nash equilibrium. Proc. 47th Annual IEEE Sympos. on Foundations of Comput. Sci., (IEEE, Piscataway, NJ), 261–272.Google Scholar
• Chinneck JW, Dravnieks EW (1991) Locating minimal infeasible constraint sets in linear programs. ORSA J. Comput. 3(2):157–168.Link, Google Scholar
• Codato G, Fischetti M (2006) Combinatorial Benders’ cuts for mixed-integer linear programming. Oper. Res. 54(4):756–766.Link, Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming (Springer, Berlin).Crossref, Google Scholar
• Conitzer V, Sandholm T (2008) New complexity results about Nash equilibria. Games Econom. Behav. 63(2):621–641.Crossref, Google Scholar
• Conitzer V, Kroer C, Sodomka E, Stier-Moses NE (2022) Multiplicative pacing equilibria in auction markets. Oper. Res. 70(2):963–989.Link, Google Scholar
• Côté JF, Dell’Amico M, Iori M (2014) Combinatorial Benders’ cuts for the strip packing problem. Oper. Res. 62(3):643–661.Link, Google Scholar
• Cottle RW, Pang JS, Stone RE (2009) The Linear Complementarity Problem (SIAM, Philadelphia).Crossref, Google Scholar
• Crönert T, Minner S (2022) Equilibrium identification and selection in finite games. Oper. Res, ePub ahead of print December 23, https://doi.org/10.1287/opre.2022.2413.Link, Google Scholar
• Daskalakis C, Goldberg PW, Papadimitriou CH (2006) The complexity of computing a Nash equilibrium. STOC: Proc. Annual ACM Sympos. on Theory of Comput., 71–78.Google Scholar
• Dehghanian A, Kurt M, Schaefer AJ (2019) Optimizing over pure stationary equilibria in consensus stopping games. Math. Programming Comput. 11(2):341–380.Crossref, Google Scholar
• Dehghanian A, Xie Y, Serban N (2023) Identifying socially optimal equilibria using combinatorial properties of Nash equilibria in bimatrix games. https://dx.doi.org/10.1287/ijoc.2022.0072.cd, https://github.com/INFORMSJoC/2022.0072.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
• Evangelista FS, Raghavan TES (1996) A note on correlated equilibrium. Internat. J. Game Theory 25(1):35–41.Crossref, Google Scholar
• Facchinei F, Pang J, Scutari G, Lampariello L (2014) VI-constrained hemivariational inequalities: Distributed algorithms and power control in ad-hoc networks. Math. Programming 145(1–2):59–96.Crossref, Google Scholar
• Filar JA, Vrieze K (1997) Competitive Markov Decision Processes (Springer-Verlag, New York).Google Scholar
• Fischetti M, Salvagnin D, Zanette A (2010) A note on the selection of Benders’ cuts. Math. Programming 124(1–2):175–182.Crossref, Google Scholar
• Gilboa I, Zemel E (1989) Nash and correlated equilibria: Some complexity considerations. Games Econom. Behav. 1(1):80–93.Crossref, Google Scholar
• Gleeson J, Ryan J (1990) Identifying minimally infeasible subsystems of inequalities. ORSA J. Comput. 2(1):61–63.Link, Google Scholar
• Goldberg PW, Papadimitriou CH (2006) Reducibility among equilibrium problems. Proc. Annual ACM Sympos. on Theory of Comput., 61–70.Google Scholar
• Govindan S, Wilson R (2003) A global Newton method to compute Nash equilibria. J. Econom. Theory 110(1):65–86.Crossref, Google Scholar
• Guo C, Bodur M, Taylor JA (2021) Copositive duality for discrete markets and games. Preprint, submitted January 13, https://arxiv.org/abs/2101.05379.Google Scholar
• Gurkan G, Pang JS (2009) Approximations of Nash equilibria. Math. Programming 117(1–2):223–253.Crossref, 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
• Hooker JN (2000) Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Hooker JN (2007) Planning and scheduling by logic-based Benders decomposition. Oper. Res. 55(3):588–602.Link, Google Scholar
• Hooker JN, Ottosson G (2003) Logic-based Benders decomposition. Math. Programming 96(1):33–60.Crossref, Google Scholar
• Hooker JN, Yan H (1995) Verifying logic circuits by Benders decomposition. Saraswat V, Hentenryck PV, eds. Principles and Practice of Constraint Programming: The Newport Papers (MIT Press, Cambridge, MA), 267–288.Google Scholar
• Jiang AX, Leyton-Brown K, Bhat NA (2011) Action-graph games. Games Econom. Behav. 71(1):141–173.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
• Kuhn HW (1961) An algorithm for equilibrium points in bimatrix games. Proc. Natl. Acad. Sci. USA 47(10):1657–1662.Crossref, Google Scholar
• Laporte G, Louveaux FV (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. 13(3):133–142.Crossref, Google Scholar
• Lemke CE (1965) Bimatrix equilibrium points and mathematical programming. Management Sci. 11(7):681–689.Link, Google Scholar
• Lemke CE, Howson J (1964) Equilibrium points of bimatrix games. J. Soc. Industry Appl. Math. 12(2):413–423.Crossref, Google Scholar
• Magnanti TL, Wong RT (1981) Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• Mailath GJ, Samuelson L (2006) Repeated Games and Reputations: Long-Run Relationships (Oxford University Press, Oxford, UK).Crossref, Google Scholar
• Mangasarian OL (1964) Equilibrium points of bimatrix games. J. Soc. Industry Appl. Math. 12(4):778–780.Crossref, Google Scholar
• McKelvey RD, McLennan A (1996) Computation of equilibria in finite games. Handbook of Computational Economics, vol. 1 (Elsevier, New York), 87–142.Google Scholar
• McKelvey RD, McLennan AM, Turocy TL (2014) Gambit: Software tools for game theory, version 16.0.2rc1. http://www.gambit-project.org.Google Scholar
• McLennan A (2005) The expected number of Nash equilibria of a normal form game. Econometrica 73(1):141–174.Crossref, Google Scholar
• Myerson RB (1991) Game Theory: Analysis of Conflict (Harvard University Press, Cambridge, MA).Google Scholar
• Nash JF (1950) Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA 36(1):48–49.Crossref, Google Scholar
• Osborne MJ (2004) An Introduction to Game Theory (Oxford University Press, Oxford, UK).Google Scholar
• Papadimitriou CH (2007) The complexity of finding Nash equilibria. Nisan N, Roughgarden T, Tardos E, Vazirani VV, eds. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 29–51.Crossref, Google Scholar
• Porter R, Nudelman E, Shoham Y (2004) Simple search methods for finding a Nash equilibrium. Proc. 19th National Conf. on Artifical Intelligence (AAAI Press, Palo Alto, CA), 664–669.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
• Qiu F, Ahmed S, Dey SS, Wolsey LA (2014) Covering linear programming with violations. INFORMS J. Comput. 26(3):531–546.Link, Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801–817.Crossref, Google Scholar
• Roughgarden T (2010) Computing equilibria: A computational complexity perspective. Econom. Theory 42(1):193–236.Crossref, Google Scholar
• Roughgarden T, Tardos E (2007) Introduction to the inefficiency of equilibria. Nisan N, Roughgarden T, Tardos E, Vazirani VV, eds. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 443–459.Crossref, Google Scholar
• Sandholm T, Gilpin A, Conitzer V (2005) Mixed-integer programming methods for finding Nash equilibria. Proc. National Conf. on Artificial Intelligence, 495–501.Google Scholar
• Scutari G, Facchinei F, Pang JS (2012) Equilibrium selection in MIMO communication games. Proc. IEEE 13th Internat. Workshop on Signal Processing Advances in Wireless Comm. (IEEE, New York), 80–84.Google Scholar
• Shoham Y, Leyton-Brown K (2008) Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• van der Laan G, Talman A, van der Heyden L (1987) Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using a general labelling. Math. Oper. Res. 12(3):377–397.Link, Google Scholar
• von Stengel B (2002) Computing equilibria for two-person games. Aumann RJ, Hart S, eds. Handbook of Game Theory with Economic Applications, vol. 3 (North-Holland, Amsterdam), 1723–1759.Google Scholar
• von Stengel B (2007) Equilibrium computation for two-player games in strategic and extensive form. Nisan N, Roughgarden T, Tardos E, Vazirani VV, eds. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 53–78.Crossref, Google Scholar
• Vorob’ev NN (1958) Equilibrium points in bimatrix games. Theory Probability Appl. 3(3):297–309.Crossref, Google Scholar
• Wheatley D, Gzara F, Jewkes E (2015) Logic-based Benders decomposition for an inventory-location problem with service constraints. Omega 55:10–23.Crossref, Google Scholar