Algorithms for Computing Equilibrium Payoffs in Quitting Games

Catherine Rainer (Université de Brest)

November 24, 2022, 11:00–12:15


Room Auditorium 1

MAD-Stat. Seminar


Characterizing and explicitly computing equilibria of undiscounted dynamic games has been a challenge for many years. In this paper we look at quitting games, which are stopping games where the terminal payoff does not depend on the stage of termination. We develop several practical algorithms that compute different classes of subgame perfect equilibria. Our algorithms are based on the novel representation of strategy profiles through absorption paths, which was developed in Ashkenazi-Golan, Krasikov, Rainer, and Solan (2021). The baseline algorithm deals with absorption paths in which exactly one player randomizes between quitting and continuing at any point in time. Two additional algorithms extend the baseline algorithm by allowing for multiple players to randomize at the same time. Since quitting games are special case of both stopping games and stochastic games, our approach may be useful in studying more general classes of stopping games and stochastic games.