Algorithms for Stochastic Games With Perfect Monitoring

Dilip Abreu, Benjamin Brooks and Yuliy Sannikov

Econometrica, 2020, vol. 88, issue 4, 1661-1695

Abstract: We study the pure‐strategy subgame‐perfect Nash equilibria of stochastic games with perfect monitoring, geometric discounting, and public randomization. We develop novel algorithms for computing equilibrium payoffs, in which we combine policy iteration when incentive constraints are slack with value iteration when incentive constraints bind. We also provide software implementations of our algorithms. Preliminary simulations indicate that they are significantly more efficient than existing methods. The theoretical results that underlie the algorithms also imply bounds on the computational complexity of equilibrium payoffs when there are two players. When there are more than two players, we show by example that the number of extreme equilibrium payoffs may be countably infinite.

Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.3982/ECTA14357

Related works:
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:wly:emetrp:v:88:y:2020:i:4:p:1661-1695

Ordering information: This journal article can be ordered from
https://www.economet ... ordering-back-issues

Access Statistics for this article

Econometrica is currently edited by Guido W. Imbens

More articles in Econometrica from Econometric Society Contact information at EDIRC.
Bibliographic data for series maintained by Wiley Content Delivery ().