Becker Friedman Institute

Research Repository

Research. Insights. Impact. Advancing the Legacy of Chicago Economics.

A "Pencil Sharpening" Algorithm for Two Player Stochastic Games with Perfect Monitoring

We study the subgame perfect equilibria of two player stochastic games with perfect monitoring and geometric discounting. A novel algorithm is developed for calculating the discounted payoffs that can be attained in equilibrium. This algorithm generates a sequence of tuples of payoffs vectors, one payoff for each state, that move around the equilibrium payoff sets in a clockwise manner. The trajectory of these “pivot” payoffs asymptotically traces the boundary of the equilibrium payoff correspondence. We also provide an implementation of our algorithm, and preliminary simulations indicate that it is more efficient than existing methods. The theoretical results that underlie the algorithm also yield a bound on the number of extremal equilibrium payoffs.

Dilip J. Abreu, Princeton University
Benjamin Brooks, University of Chicago
Yuliy Sannikov, Princeton University
Publication Date: 
February, 2016
Publication Status: 
Document Number: 
Working Paper Series No. 2016-05