Exact Equilibrium Analysis of Sparse Network Games in Subexponential Time
In October 2026 two independent groups claimed deterministic algorithms that count the satisfying assignments of a k-CNF formula in time 2^{o(n)}, refuting the Exponential Time Hypothesis (ETH). We ask what these claims imply for the exact analysis of equilibria in games where each player interacts with a bounded number of others. Conditional on the claimed … Read more