Algorithms for Stochastic Games With Perfect Monitoring

Dilip Abreu, Benjamin Brooks, Yuliy Sannikov

    Research output: Contribution to journalArticlepeer-review

    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.

    Original languageEnglish (US)
    Pages (from-to)1661-1695
    Number of pages35
    JournalEconometrica
    Volume88
    Issue number4
    DOIs
    StatePublished - Jul 1 2020

    Keywords

    • algorithm
    • computation
    • perfect monitoring
    • Stochastic game

    ASJC Scopus subject areas

    • Economics and Econometrics

    Fingerprint Dive into the research topics of 'Algorithms for Stochastic Games With Perfect Monitoring'. Together they form a unique fingerprint.

    Cite this