Research / BFI Working PaperFeb 01, 2016

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

Dilip J. Abreau, Benjamin Brooks, Yuliy Sannikov

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.

More Research From These Scholars

BFI Working Paper Nov 1, 2015

First Price Auctions with General Information Structures: Implications for Bidding and Revenue

Benjamin Brooks, Stephen Morris, Dirk Bergemann
Topics:  Fiscal Studies
BFI Working Paper Mar 19, 2020

Search, Information, and Prices

Dirk Bergemann, Benjamin Brooks, Stephen Morris
Topics:  Uncategorized