Pure Nash Equilibria in Graphical Games and Treewidth

We treat PNE-GG, the problem of deciding the existence of a Pure Nash Equilibrium in a graphical game, and the role of treewidth in this problem. PNE-GG is known to be -complete in general, but polynomially solvable for graphical games of bounded treewidth. We prove that PNE-GG is -Hard when parameterized by treewidth. On the other hand, we give a dynamic programming approach that solves the problem in time, where is the cardinality of the largest strategy set and is the treewidth of the input graph (and hides polynomial factors). This proves that PNE-GG is in for the combined parameter . Moreover, we prove that there is no algorithm that solves PNE-GG in time for any , unless the Strong Exponential Time Hypothesis fails. Our lower bounds implicitly assume that ; we show that for the problem can be solved in polynomial time. Finally, we discuss the implication for computing pure Nash equilibria in graphical games (PNE-GG) of treewidth, the existence of polynomial kernels for PNE-GG parameterized by treewidth, and the construction of a sample and maximum-payoff pure Nash equilibrium.