Tech Report CS-05-07

A Direct Proof of the Existense of Correlated Equilibrium Policies in General-Sum Markov Games

Amy Greenwald and Martin Zinkevich

July 2005

Abstract:

In this report, we establish the existence of stationary correlated equilibrium policies in Markov games. In fact, the existence of stationary correlated equilibrium policies in Markov games is implied by the existence of stationary Nash equilibrium policies in Markov games (see, for example, Filar and Vrieze (1996). Nonetheless, we prove existence directly because our existence proof, a fixed point argument, motivates our algorithmic search for just such a fixed point in a companion paper (Greenwald et al., 2005). Analogously, a classic proof of existence of an optimal policy in Markov decision processes, based on Banach's fixed point theorem, motivates the design of value iteration (see, for example, Puterman (1994)and Q-learning Watkins (1989).

(complete text in pdf)