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

Research Papers from Stanford University, Graduate School of Business

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-04
New Economics Papers: this item is included in nep-gth and nep-mic
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.gsb.stanford.edu/gsb-cmis/gsb-cmis-download-auth/417951
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://www.gsb.stanford.edu/gsb-cmis/gsb-cmis-download-auth/417951 [301 Moved Permanently]--> https://www.gsb.stanford.edu/gsb-cmis/gsb-cmis-download-auth/417951)

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:ecl:stabus:3428

Access Statistics for this paper

More papers in Research Papers from Stanford University, Graduate School of Business Contact information at EDIRC.
Bibliographic data for series maintained by ().