Papers › Geometric Structure and Polynomial-time Algorithm of Game Equilibria
Geometric Structure and Polynomial-time Algorithm of Game Equilibria
Hongbo Sun, Chongkun Xia, Junbo Tan, Bo Yuan, Xueqian Wang, Bin Liang
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Whether a PTAS (polynomial-time approximation scheme) exists for game equilibria has been an open question, and its absence has indications and consequences in three fields: the practicality of methods in algorithmic game theory, non-stationarity and curse of multiagency in MARL (multi-agent reinforcement learning), and the tractability of PPAD in computational complexity theory. In this paper, we formalize the game equilibrium problem as an optimization problem that splits into two subproblems with respect to policy and value function, which are solved respectively by interior point method and dynamic programming. Combining these two parts, we obtain an FPTAS (fully PTAS) for the weak approximation (approximating to an ϵ-equilibrium) of any perfect equilibrium of any dynamic game, implying PPAD=FP since the weak approximation problem is PPAD-complete. In addition, we introduce a geometric object called equilibrium bundle, regarding which, first, perfect equilibria of dynamic games are formalized as zero points of its canonical section, second, the hybrid iteration of dynamic programming and interior point method is formalized as a line search on it, third, it derives the existence and oddness theorems as an extension of those of Nash equilibria. In experiment, the line search process is animated, and the method is tested on 2000 randomly generated dynamic games where it converges to a perfect equilibrium in every single case.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections