On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games
By: Kristoffer Arnsfelt Hansen, Xinhao Nie
Potential Business Impact:
Finds fair outcomes in complex games.
We study the problem of computing stationary Nash equilibria in discounted perfect information stochastic games from the viewpoint of computational complexity. For two-player games we prove the problem to be in PPAD, which together with a previous PPAD-hardness result precisely classifies the problem as PPAD-complete. In addition to this we give an improved and simpler PPAD-hardness proof for computing a stationary epsilon-Nash equilibrium. For 3-player games we construct games showing that rational-valued stationary Nash equilibria are not guaranteed to exist, and we use these to prove SqrtSum-hardness of computing a stationary Nash equilibrium in 4-player games.
Similar Papers
Spatial Branch-and-Bound for Computing Multiplayer Nash Equilibrium
CS and Game Theory
Finds fair outcomes in complex games.
Spatial Branch-and-Bound for Computing Multiplayer Nash Equilibrium
CS and Game Theory
Finds fair outcomes in complex games.
ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games
CS and Game Theory
Finds near-perfect game strategies when perfect ones are too hard.