An Algorithm for Two-Player Repeated Games With Perfect Monitoring

An Algorithm for Two-Player Repeated Games With Perfect Monitoring

By
Dilip Abreu, Yuliy Sannikov
Theoretical Economics.
2014, Vol. 9, Pages 313-338

Consider repeated two-player games with perfect monitoring and discounting. We provide an algorithm that computes the set V ∗ of payoff pairs of all pure strategy subgame-perfect equilibria with public randomization. The algorithm provides significant efficiency gains over the existing implementations of the algorithm from Abreu et al. (1990). These efficiency gains arise from a better understanding of the manner in which extreme points of the equilibrium payoff set are generated. An important theoretical implication of our algorithm is that the set of extreme points E of V ∗ is finite. Indeed, |E| ≤ 3|A|, where A is the set of action profiles of the stage game.