A Polynomial-time Nash Equilibrium Algorithm for Repeated Stochastic Games

Understand

We present a polynomial-time algorithm that always finds an (approximate) Nash equilibrium for repeated two-player stochastic games.

• The algorithm exploits the folk theorem to derive a strategy profile that forms an equilibrium by buttressing mutually beneficial behavior with threats, where possible.
• One component of our algorithm efficiently searches for an approximation of the egalitarian point, the fairest pareto-efficient solution.
• The paper concludes by applying the algorithm to a set of grid games to illustrate typical solutions the algorithm finds.