PERTURBATIONS OFMARKOVCHAINSWITH APPLICATIONS TO STOCHASTIC GAMES

Abstract. In this chapter we will review several topics that are used ex-tensively in the study of n-player stochastic games. These tools were used in the proof of several results on non-zero-sum stochastic games. Most of the results presented here appeared in [17],[16], and a few ap-peared in [12],[13]. The first main issue is Markov chains where the transition rule is a Puiseux probability distribution. We define the notion of communicating sets and construct a hierarchy on the collection of these sets. We then relate these concepts to stochastic games, and show several conditions that enable the players to control the exit distribution from communicating sets. 1. Markov Chains A Markov chain is a pair (K, p) where K is a finite set of states, and p: K → ∆(K) is a transition rule, where ∆(K) is the set of probability distributions over K. The transition rule p, together with an initial state k ∈ K, defines a process on the states. Denote by kn the state of the process at stage n, n = 1, 2,.... Let Pk,p be the probability distribution induced by p and the initial state k over the space of infinite histories. A subset C ⊆ K is recurrent if for every k ∈