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; 06-20-2003 - 06-22-2003; in: "Proceedings of the 9", (2003), 215 - 229.^{th}conference on Theoretical Aspects of Rationality and Knowledge

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}_{2}-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_{2}of highly parallalizable problems

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

Created from the Publication Database of the Vienna University of Technology.