Computer Science – Computer Science and Game Theory
Scientific paper
2011-09-09
Journal Of Artificial Intelligence Research, Volume 24, pages 357-406, 2005
Computer Science
Computer Science and Game Theory
Scientific paper
10.1613/jair.1683
We investigate complexity issues related to pure Nash equilibria of strategic games. We show that, even in very restrictive settings, determining whether a game has a pure Nash Equilibrium is NP-hard, while deciding whether a game has a strong Nash equilibrium is SigmaP2-complete. We then study practically relevant restrictions that lower the complexity. In particular, we are interested in quantitative and qualitative restrictions of the way each players payoff depends on moves of other players. We say that a game has small neighborhood if the utility function for each player depends only on (the actions of) a logarithmically small number of other players. The dependency structure of a game G can be expressed by a graph DG(G) or by a hypergraph H(G). By relating Nash equilibrium problems to constraint satisfaction problems (CSPs), we show that if G has small neighborhood and if H(G) has bounded hypertree width (or if DG(G) has bounded treewidth), then finding pure Nash and Pareto equilibria is feasible in polynomial time. If the game is graphical, then these problems are LOGCFL-complete and thus in the class NC2 of highly parallelizable problems.
Gottlob Georg
Greco Gianluigi
Scarcello Francesco
No associations
LandOfFree
Pure Nash Equilibria: Hard and Easy 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 Pure Nash Equilibria: Hard and Easy Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pure Nash Equilibria: Hard and Easy Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-38158