  Whether a PTAS (polynomial-time approximation scheme) exists for equilibriums
of games has been an open question, which relates to questions in three fields,
the practicality of methods in algorithmic game theory, the equation PPAD=FP
about the two complexity classes in computational complexity theory, and
non-stationarity and curse of multiagency in MARL (multi-agent reinforcement
learning). This paper introduces our discovery of the sufficient and necessary
conditions for iterations based on dynamic programming and line search to
approximate perfect equilibriums of dynamic games, out of which we construct a
method proved to be a FPTAS (fully PTAS) for non-singular perfect equilibriums
of dynamic games, where for almost any given dynamic game, all its perfect
equilibriums are non-singular, indicating that
FP$\subseteq$PPAD$\subseteq$Almost-FP. Our discovery consists of cone interior
dynamic programming and primal-dual unbiased regret minimization, which fit
into existing theories by degeneration in a structure-preserving manner. The
former enables a dynamic programming operator to iteratively converge to a
perfect equilibrium based on a concept called policy cone. The latter enables
an interior-point line search to approximate a Nash equilibrium based on two
concepts called primal-dual bias and unbiased central variety, solving a
subproblem of the former. Validity of our discovery is cross-corroborated by a
combination of theorem proofs, graphs of the three main concepts, and
experimental results.
