Stochastic Games and Positional Games on Networks

Stochastic games represent an important class of models in game theory that extend Markov decision processes to competitive situations with more than one decision-maker. Such models may be with finite, countable, or continuum cardinality sets of states Kallenberg ((2011) Markov decision processes. Lecture Notes. University of Leiden, pp 2–5), Puterman ((2014) Markov decision processes: discrete stochastic dynamic programming. Wiley). In this chapter, we consider only stochastic games with finite state and action spaces. We mainly study two classes of games: stochastic games with average payoff optimization criteria and stochastic games with discounted payoff optimization criteria for the players. The main results presented in this chapter are concerned with the existence and determination of stationary Nash equilibria for different classes of stochastic games. By applying the concept of positional games for the Markov decision problems and stochastic control on networks, we formulate a class of stochastic positional games for which Nash equilibria in stationary strategies exist and for which efficient algorithms to determine the optimal stationary strategies of the players can be elaborated.