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 [1]-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 >0, unless the Strong Exponential Time Hypothesis fails. Our lower bounds implicitly assume that ≥3; we show that for =2 the problem can be solved in polynomial time. Finally, we discuss the implication for computing pure Nash equilibria in graphical games (PNE-GG) of (log) treewidth, the existence of polynomial kernels for PNE-GG parameterized by treewidth, and the construction of a sample and maximum-payoff pure Nash equilibrium.ISSN:0178-4617ISSN:1432-054