HKD∞ Incremental Nash: Exact Equilibrium Computation with Linear-in-N Cycle Reduction in Sparse Potential Games

Abstract

This paper studies exact pure Nash-equilibrium computation in sparse binary-action exact-potential graphical games. A conventional deterministic best-improvement implementation recomputes every player's unilateral deviation gain after every accepted move. The HKD∞ incremental formulation instead maintains exact regret values and invalidates only the deviating player and its graph neighbors. For bounded interaction degree d and T accepted deviations, the resulting gain-evaluation count is N + (d + 1)T, compared with N(T + 1) for a full-rescan implementation. Thus, when d = O(1) and T = Θ(N), the operation-count reduction grows linearly with N while preserving the identical deterministic equilibrium trajectory. A reproducible Python benchmark over N = 250,500,1000,2000, and 4000 players verifies zero positive unilateral regret at termination, identical final strategy profiles, identical flip counts, and cycle-count reductions from 26.23× to 408.81×. On the author's reported Python 3.10 run, wall-clock speedup rises from 20.46× to 289.68×, with the 4000-player case decreasing from 4.026344s to 0.013899s. We additionally describe an exact-cover layer for selecting compatible profitable deviations in parallel; this layer is not included in the reported timing table and therefore does not affect the measured claims. The public reproduction code contains no private or paid HKD implementation details and independently checks exact equilibrium conditions.