Talks and Poster Presentations (with Proceedings-Entry):

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

English abstract:
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 ΣP2 -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 NC2 of highly parallalizable problems

Online library catalogue of the TU Vienna:

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