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

Dilip Abreu, Benjamin Brooks and Yuliy Sannikov
Additional contact information
Dilip Abreu: Princeton University
Yuliy Sannikov: Princeton University

Working Papers from Princeton University, Department of Economics, Econometric Research Program.

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.

JEL-codes: C63 C72 C73 D90 (search for similar items in EconPapers)
Date: 2016-02
New Economics Papers: this item is included in nep-gth, nep-hpe and nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://detc.princeton.edu/wp-content/uploads/2016/ ... pening-Algorithm.pdf
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://detc.princeton.edu/wp-content/uploads/2016/11/wp078_2016_Abreu_Brooks_Sannikov_A-Pencil-Sharpening-Algorithm.pdf [302 Found]--> https://detc.princeton.edu/wp-content/uploads/2016/11/wp078_2016_Abreu_Brooks_Sannikov_A-Pencil-Sharpening-Algorithm.pdf [301 Moved Permanently]--> https://economics.princeton.edu/the-william-s-dietrich-ii-economic-theory-center/wp-content/uploads/2016/11/wp078_2016_Abreu_Brooks_Sannikov_A-Pencil-Sharpening-Algorithm.pdf)

Related works:
Working Paper: A "Pencil-Sharpening" Algorithm for Two Player Stochastic Games with Perfect Monitoring (2016)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pri:metric:78_2016

Access Statistics for this paper

More papers in Working Papers from Princeton University, Department of Economics, Econometric Research Program. Contact information at EDIRC.
Bibliographic data for series maintained by Bobray Bordelon ().