Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Settling Some Open Problems on 2-Player Symmetric Nash Equilibria
verfasst von : Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod
Erschienen in: Algorithmic Game Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Over the years, researchers have studied the complexity of several decision versions of Nash equilibrium in (symmetric) two-player games (bimatrix games). To the best of our knowledge, the last remaining open problem of this sort is the following; it was stated by Papadimitriou in 2007: find a non-symmetric Nash equilibrium (NE) in a symmetric game. We show that this problem is NP-complete and the problem of counting the number of non-symmetric NE in a symmetric game is #P-complete.
In 2005, Kannan and Theobald defined the rank of a bimatrix game represented by matrices (A, B) to be rank\((A+B)\) and asked whether a NE can be computed in rank 1 games in polynomial time. Observe that the rank 0 case is precisely the zero sum case, for which a polynomial time algorithm follows from von Neumann’s reduction of such games to linear programming. In 2011, Adsul et al. obtained an algorithm for rank 1 games; however, it does not guarantee symmetric NE in symmetric rank 1 game. We resolve this problem.