The Complexity of Nash Equilibria in Limit-Average Games

Details The Complexity of Nash Equilibria in Limit-Average Games The Complexity of Nash Equilibria in Limit-Average Games

2011-09-28

arxiv.org/abs/1109.6220v1

Computer Science

Computer Science and Game Theory

34 pages

Scientific paper

10.1007/978-3-642-23217-6_32

We study the computational complexity of Nash equilibria in concurrent games with limit-average objectives. In particular, we prove that the existence of a Nash equilibrium in randomised strategies is undecidable, while the existence of a Nash equilibrium in pure strategies is decidable, even if we put a constraint on the payoff of the equilibrium. Our undecidability result holds even for a restricted class of concurrent games, where nonzero rewards occur only on terminal states. Moreover, we show that the constrained existence problem is undecidable not only for concurrent games but for turn-based games with the same restriction on rewards. Finally, we prove that the constrained existence problem for Nash equilibria in (pure or randomised) stationary strategies is decidable and analyse its complexity.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Nash Equilibria in Limit-Average 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 The Complexity of Nash Equilibria in Limit-Average Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Nash Equilibria in Limit-Average Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-43789