Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
On the Hardness and Existence of Quasi-Strict Equilibria
verfasst von : Felix Brandt, Felix Fischer
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
This paper investigates the computational properties of quasi-strict equilibrium, an attractive equilibrium refinement proposed by Harsanyi, which was recently shown to always exist in bimatrix games. We prove that deciding the existence of a quasi-strict equilibrium in games with more than two players is NP-complete. We further show that, in contrast to Nash equilibrium, the support of quasi-strict equilibrium in zero-sum games is unique and propose a linear program to compute quasi-strict equilibria in these games. Finally, we prove that every symmetric multi-player game where each player has two actions at his disposal contains an efficiently computable quasi-strict equilibrium which may itself be asymmetric.