# Geometric Structure and Polynomial-time Algorithm of Game Equilibria

arXiv: https://arxiv.org/abs/2401.00747 · HTML: https://mlsanity.com/paper/2401.00747/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 1 of its 28 references that are in the map.
- First posted on arXiv 1 Jan 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 1 of 1)

- [Inapproximability of Nash Equilibrium](https://mlsanity.com/paper/1405.3322/) (2014)

## Abstract (arXiv)

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.