An algorithm for two-player repeated games with perfect monitoring

• 成果类型: Article
• 署名作者: Abreu, Dilip; Sannikov, Yuliy
• 署名单位: Princeton University
• 刊物名称: THEORETICAL ECONOMICS
• ISSN/ISSBN: 1933-6837
• DOI: 10.3982/TE1302
• 发表日期: 2014-05-01
• 页码: 313-338
• 关键词: Repeated games; perfect monitoring; computation

摘要

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, vertical bar E vertical bar <= 3 vertical bar A vertical bar, where A is the set of action profiles of the stage game.