Algorithms - ESA 2005 (13th annual European sympoisum, Palma de Mallorca, Sapin, October 3-6, 2005, proceedings)Lecture notes in computer science. :71-82
Copyright 2005 INIST-CNRS CC BY 4.0 Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Operational research. Management
Accession Number:
edscal.17246865
Database:
PASCAL Archive
Weitere Informationen
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.
