Michael S. Yang

DOI: https://doi.org/10.5281/zenodo.22146946

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.

Nash equilibrium; potential games; graphical games; incremental algorithms; sparse computation; exact equilibrium; HKD∞; exact cover.

Sparse dependence can change the computational shape of exact equilibrium dynamics even when it does not change the underlying game-theoretic solution concept. For bounded-degree exact-potential graphical games, a full rescan spends work on N players after each local move, whereas HKD∞ retains unaffected exact gains and refreshes only the changed dependency neighborhood. The resulting count N + (d +1)T versus N(T +1) yields a linear-in-N cycle reduction when d is bounded and T grows linearly with N. The reported benchmark verifies this scaling experimentally through 4000 players, culminating in a 408.81x reduction in unilateral-gain evaluations and a 289.68x measured wall-clock speedup on the author’s run. Exactness is stronger 4 thanendpointagreementalone: bothmethodsusethesamedeterministicrule,performthesamenumberofaccepted deviations,reachtheidenticalstrategyprofile,andindependentlysatisfyzeropositiveunilateralregret.Thepublic reproductionprogramexposes the theorem-level algorithmwhilewithholdingunrelatedprivateHKDandpaid exact-coverimplementationdetails.

[1] J. F. Nash, Jr., “Equilibrium Points in n-Person Games,” Proceedings of the National Academy of Sciences, vol. 36,
no. 1, pp. 48–49, 1950. doi:10.1073/pnas.36.1.48. https://doi.org/10.1073/pnas.36.1.48
[2] D. Monderer and L. S. Shapley, “Potential Games,” Games and Economic Behavior, vol. 14, no. 1, pp. 124–143,
1996. doi:10.1006/game.1996.0044. https://doi.org/10.1006/game.1996.0044
[3] M. Kearns, M. L. Littman, and S. Singh, “Graphical Models for Game Theory,” Proc. 17th UAI, pp. 253–260, 2001.
https://www.cis.upenn.edu/~mkearns/papers/old-graphgames.pdf
[4] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou, “The Complexity of Computing a Nash Equilibrium,”
SIAM Journal on Computing, vol. 39, no. 1, pp. 195–259, 2009. doi:10.1137/070699652. https://doi.org/10.113
7/070699652
[5] R. Savani and T. L. Turocy, “Gambit: The package for computation in game theory,” Version 16.1.0, 2023.
https://gambitproject.readthedocs.io/en/v16.1.0/

Michael S. Yang (2026). HKD∞ Incremental Nash: Exact Equilibrium Computation with Linear-in-N Cycle Reduction in Sparse Potential Games. International Journal of Computer Techniques, 13(4), 299–304. ISSN: 2394-2231. DOI: https://doi.org/10.5281/zenodo.22146946