Title

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

Author(s)

Dilip Abreu Dilip Abreu (Princeton University)

Benjamin Brooks Benjamin Brooks (Becker Friedman Institute and Univ ersity of Chicago)

Yuliy Sannikov Yuliy Sannikov (Princeton University)

Abstract

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.

Creation Date

2016-02

Section URL ID

Paper Number

78_2016

URL

http://detc.princeton.edu/wp-content/uploads/2016/11/wp078_2016_Abreu_Brooks_Sannikov_A-Pencil-Sharpening-Algorithm.pdf

File Function

Jel

C63, C72, C73, D90

Keyword(s)

Suppress

false

Series

10