In this paper 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 St-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 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 he expressed by a graph G(G) or by a hypergraph I-I(G). Among other results, we show that if jC has small neighborhood and if I-I(G) has botmdecl hypertree width (or if G(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 _NC~ of highly parallelizable problems.
While it is of course easy to find pure Nash equilibria of normal form games, Gottlob et al. REF show that most versions of the problem of finding pure Nash equilibria are hard when the game is described succintly.
Pure Nash equilibria: hard and easy games
TARK '03
Mathematics Computer Science