Computer Science – Computer Science and Game Theory
Scientific paper
2002-05-28
In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, 2003
Computer Science
Computer Science and Game Theory
Scientific paper
Noncooperative game theory provides a normative framework for analyzing strategic interactions. However, for the toolbox to be operational, the solutions it defines will have to be computed. In this paper, we provide a single reduction that 1) demonstrates NP-hardness of determining whether Nash equilibria with certain natural properties exist, and 2) demonstrates the #P-hardness of counting Nash equilibria (or connected sets of Nash equilibria). We also show that 3) determining whether a pure-strategy Bayes-Nash equilibrium exists is NP-hard, and that 4) determining whether a pure-strategy Nash equilibrium exists in a stochastic (Markov) game is PSPACE-hard even if the game is invisible (this remains NP-hard if the game is finite). All of our hardness results hold even if there are only two players and the game is symmetric. Keywords: Nash equilibrium; game theory; computational complexity; noncooperative game theory; normal form game; stochastic game; Markov game; Bayes-Nash equilibrium; multiagent systems.
Conitzer Vincent
Sandholm Tuomas
No associations
LandOfFree
Complexity Results about Nash Equilibria 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 Complexity Results about Nash Equilibria, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity Results about Nash Equilibria will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-169539