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 algorithm of Claude (Anthropic), we show that for such sparse network games a single object, the equilibrium generating function, which records every pure Nash equilibrium together with its welfare, can be computed in time 2^{O(N/sqrt(log N))} for N players. From it one reads off, exactly, the number of pure equilibria, their existence and uniqueness, the best and worst equilibrium welfare (hence the price of anarchy and the price of stability), equilibrium-selection values, and the optimistic and pessimistic values of a Stackelberg leader with a polynomial list of commitments. We complement the algorithm with hardness results for games with two actions per player and payoffs that depend on at most two other players: beyond the known NP-completeness of existence and #P-completeness of counting, uniqueness, “PoS = 1”, “PoA = 1”, selection values and the optimal pessimistic commitment are NP- or coNP-hard even when an equilibrium is guaranteed to exist. The reductions are linear, so under the Stearns-Hunt hypothesis none of these problems can be solved in time 2^{N^{1-eps}}; conditional on the engine, the exponent is therefore N^{1-o(1)}. We illustrate the results on capacity procurement games in which buyers choose among nearby suppliers and delimit what the approach cannot do. All results are asymptotic.
Citation
Working paper, Monash University, November 2026