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

Amin Dehghanian (), Yujia Xie () and Nicoleta Serban ()
Additional contact information
Amin Dehghanian: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Yujia Xie: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Nicoleta Serban: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

INFORMS Journal on Computing, 2024, vol. 36, issue 5, 1261-1286

Abstract: Nash equilibrium is arguably the most fundamental concept in game theory, which is used to analyze and predict the behavior of the players. In many games, there exist multiple equilibria, with different expected payoffs for the players, which in turn raises the question of equilibrium selection. In this paper, we study the N P -hard problem of identifying a socially optimal Nash equilibrium in two-player normal-form games (called bimatrix games), which may be represented by a mixed integer linear program (MILP). We characterize the properties of the equilibria and develop several classes of valid inequalities accordingly. We use these theoretical results to provide a decomposition-based reformulation of the MILP, which we solve by a branch-and-cut algorithm. Our extensive computational experiments demonstrate superiority of our approach over solving the MILP formulation through feeding it into a commercial solver or through the “traditional” Benders’ decomposition. Of note, our proposed approach can find provably optimal solutions for many instances.

Keywords: bimatrix game; socially optimal equilibrium; support of a strategy profile; branch-and-cut; minimally infeasible subsystem; Benders’ decomposition (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0072 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:5:p:1261-1286

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().