Theoretical Economics 9 (2014), 313–338
An algorithm for two-player repeated games with perfect monitoring
Dilip Abreu, Yuliy Sannikov
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 signiï¬cant eï¬ƒciency gains over the existing implementations of the algorithm from Abreu, Pearce and Stacchetti (1990). These eï¬ƒciency gains arise from a better understanding of the manner in which extreme points of the equilibrium payoï¬€ 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 proï¬les of the stage game.
Keywords: Repeated games, perfect monitoring, computation
JEL classification: C63, C72, C73
Full Text: PRINT VIEW Supplementary appendix