Loading...
Loading...

Go to the content (press return)

PSPACE suffices for deciding nash equilibria properties for extensive games with large trees

Author
Alvarez, C.; Gabarro, J.; Serna, M.
Type of activity
Report
Date
2005-09
Code
LSI-05-39-R
Repository
http://hdl.handle.net/2117/85635 Open in new window
Abstract
We study the computational complexity of deciding the existence of a Pure Nash Equilibrium or a subgame perfect equilibrium with a given payoff and other related problems in finite multi-player extensive games with perfect information. We first propose three way of representing a game with different degrees of succinctness for the components of the game. We show that when the number of moves of each player is large and the player function and the utilities are represented succinctly the consider...
Citation
Álvarez, C., Gabarró, J., Serna, M. "PSPACE suffices for deciding nash equilibria properties for extensive games with large trees". 2005.
Keywords
Extensive games, PSPACE, Pure Nash equilibria, Subgame perfect Nash equilibria
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Attachments