Decision Problems for Nash Equilibria in Stochastic Games

Details Decision Problems for Nash Equilibria in Stochastic Games Decision Problems for Nash Equilibria in Stochastic Games

2009-04-21

arxiv.org/abs/0904.3325v3

Computer Science

Computer Science and Game Theory

22 pages, revised version

Scientific paper

10.1007/978-3-642-04027-6_37

We analyse the computational complexity of finding Nash equilibria in stochastic multiplayer games with $\omega$-regular objectives. While the existence of an equilibrium whose payoff falls into a certain interval may be undecidable, we single out several decidable restrictions of the problem. First, restricting the search space to stationary, or pure stationary, equilibria results in problems that are typically contained in PSPACE and NP, respectively. Second, we show that the existence of an equilibrium with a binary payoff (i.e. an equilibrium where each player either wins or loses with probability 1) is decidable. We also establish that the existence of a Nash equilibrium with a certain binary payoff entails the existence of an equilibrium with the same payoff in pure, finite-state strategies.

Affiliated with

Also associated with

No associations

Rating

Decision Problems for Nash Equilibria in Stochastic Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Decision Problems for Nash Equilibria in Stochastic Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decision Problems for Nash Equilibria in Stochastic Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-372113