Geometric Structure and Polynomial-time Algorithm of Game Equilibria

This research paper proposes a polynomial-time approximation scheme (PTAS) for finding perfect equilibria in dynamic games. This is a significant contribution to game theory because it has long been an open question whether such an algorithm exists. The authors introduce a new geometric object called the "equilibrium bundle," which allows them to formalize perfect equilibria as zero points of its canonical section. The paper then presents a hybrid algorithm combining dynamic programming and an interior point method that iteratively searches for perfect equilibria on the equilibrium bundle. The algorithm achieves a weak approximation in fully polynomial time, meaning that it can find a policy that is close to an actual perfect equilibrium, and it also implies that the complexity class PPAD, previously believed to contain intractable problems, actually has efficient solutions.