[Back]

G. Gottlob, G. Greco, F. Scarcello:
"Pure Nash Equilibria: Hard and Easy Games";
Talk: 9^th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 03), Bloomington, USA; 2003-06-20 - 2003-06-22; in: "Proceedings of the 9^th conference on Theoretical Aspects of Rationality and Knowledge", (2003), 215 - 229.

In this paper we investigate complexity issues related to pure Nash equilibria of strategic games. We show that, even in very restricted settings, determining whether a game has a pure Nash Equilibrium is NP-hard, while deciding whther a game has a strong Nash Equilibrium is Σ^P₂ -complete. WE then study practically relevant restrictions that lower the complexity. In particular, we are interested in quatitative and qualitative restrictions of the way each player´s move 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 G or by a hypograph H. Among other results, we show that if G has small neighborhood and if H has bounded hypertree width (or if G has bounded treewidth), then finding pure Nash and Pareto equilibria is feasable inpolynomial time. If the game is graphical, the these problems are LOGGFL-complete and thus in the class NC₂ of highly parallalizable problems

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04404479