Pure Nash Equilibria in Graphical Games and Treewidth

Abstract

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.