Stationary Markov Equilibrium Strategies in Stochastic Games: Existence and Computation

Abstract We show here that a stationary Markov equilibrium can be computed for an n -person stochastic game by using an iterative procedure often used in machine learning when the state space is finite and the action sets of the players are finite. The iterative procedure involves computing the equilibrium of the constituent game (possibly mixed) after each iteration. The constituent game in each iteration is the game in which the payoff of a player consists of two terms. One is the payoff of the player from the underlying single-period game and the second is the discounted equilibrium payoff of the player from the constituent game of the previous iteration. We show that the equilibrium payoffs of the constituent games converge, and lead to a constituent game in the limit, whose equilibrium payoffs are the same as those from the previous iteration. The equilibrium payoffs from the iterative procedure thus converge to stationary equilibrium payoffs. These equilibrium payoffs are then the payoffs of a stationary Markov perfect equilibrium of the infinite horizon stochastic game. We provide an algorithm based on this result to compute the stationary Markov perfect equilibrium of the infinite horizon stochastic game. To evaluate our proposed algorithm, we conduct several experiments to derive their stationary Markov perfect equilibrium, including a version of the cybersecurity game analyzed in Lye and Wing and a version of the price-setting dynamic game of market competition analyzed in Besanko, Daralzeski, Kryukov, and Satterthwaite.