Lampis and Lu refine Nash equilibrium complexity with improved parameterized algorithms

A new paper by Michael Lampis and Yiren Lu (arXiv:2607.07627) re-examines the fine-grained complexity of finding pure Nash equilibria (PNE) in graphical games, where each player's utility depends on at most Δ other players and the game graph has bounded treewidth (tw). The standard dynamic programming algorithm runs in time α^{(Δ+1)tw}, where α is the number of strategies per player. The authors first expose a fatal flaw in a 2015 algorithm by Thomas and van Leeuwen that claimed to improve this to α^{O(tw)}; they prove that such an improvement would imply FPT=W[1], a major complexity collapse. This correction is significant because researchers had relied on that result for subsequent work.

The core contribution is a set of new algorithms that achieve better parameterized dependencies: α^{⌊2Δ/3+1⌋ tw} for treewidth, α^{⌊Δ/2+1⌋ pw} for pathwidth, and α^{ctw} for cutwidth. The key algorithmic tool is a tightening of the relationship between the width of a graph G, its maximum degree, and the width of the square graph G^2, which may have independent applications. Complementing these positive results, the authors prove that their algorithms for pathwidth and cutwidth are optimal under the pw-SETH hypothesis, meaning further improvement would refute a standard complexity assumption. The work provides both a correction to the literature and a precise characterization of the problem's complexity.