A Survey on Optimality and Equilibria in Stochastic Games

In this paper we discuss the main existence results on optimality and equilibria in two-person stochastic games with finite state and action spaces. Several examples are provided to clarify the issues. 1 The Stochastic Game Model In this introductory section we give the necessary definitions and notations for the two-person case of the stochastic game model and we briefly present some basic results. In section 2 we discuss the main existence results for zero-sum stochastic games, while in section 3 we focus on general-sum stochastic games. In each section we discuss several examples to illustrate the most important phenomena. It all started with the fundamental paper by Von Neumann [1928] in which he proves the so called minimax theorem which says that for each finite matrix of reals A = [aij]m ni=1,j=1 there exist probability vectors x ̄ = (x̄1, x̄2,..., x̄m) and y ̄ = (ȳ1, ȳ2,..., ȳn) such that for all x and y it holds that2 xAy ̄ ≤ x̄Ay ̄ ≤ x̄Ay. In other words: maxx miny xAy = miny maxx xAy. This theorem can be interpreted to say that each matrix game has a value. A matrix game A is played as follows. Simultaneously, and independent from each other, player 1 chooses a row i and player 2 chooses a column j of A. Then player 2 has to pay the amount aij to player 1. Each player is allowed to randomize over his available actions and we assume that player 1 wants to maximize his expected payoff, while player 2 wants to minimiz