Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
The Complexity of Games on Highly Regular Graphs
verfasst von : Konstantinos Daskalakis, Christos H. Papadimitriou
Erschienen in: Algorithms – ESA 2005
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
We present algorithms and complexity results for the problem of finding equilibria (mixed Nash equilibria, pure Nash equilibria and correlated equilibria) in games with extremely succinct description that are defined on highly regular graphs such as the
d
-dimensional grid; we argue that such games are of interest in the modelling of large systems of interacting agents. We show that mixed Nash equilibria can be found in time exponential in the succinct representation by quantifier elimination, while correlated equilibria can be found in polynomial time by taking advantage of the game’s symmetries. Finally, the complexity of determining whether such a game on the
d
-dimensional grid has a pure Nash equilibrium depends on
d
and the dichotomy is remarkably sharp: it is solvable in polynomial time (in fact
NL
-complete) when
d
= 1, but it is
NEXP
-complete for
d
≥ 2.