Robert Samuel Simon
Value and Perfection in Stochastic Games
Preprint series: Mathematica Gottingensis

MSC:

90D15 Stochastic games, See also {93E05}

Abstract: A stochastic game is {\em valued} if for
every player $k$ there
is
a function $r^k:S\rightarrow {\bf R}$ from the state space $S$ to the
real numbers
such that for every $\epsilon>0$ there is an $\epsilon$
equilibrium such that with probability
at least $1-\epsilon$ no state $s$ is reached
where
the future expected payoff for any player $k$
differs from $r^k(s)$ by more than $\epsilon$.
We demonstrate an example of a recursive two-person non-zero-sum
stochastic game
with only three non-absorbing states and limit average payoffs
that is not valued, (but
does have $\epsilon$ equilibria for every positive
$\epsilon$). In this respect
two-person non-zero-sum stochastic games are
very different from their
zero-sum varieties. N. Vieille proved that
all such games with finitely
many states have an $\epsilon$ equilibrium
for every positive $\epsilon$, and our example shows that any proof of this
result
must be qualitatively
different from the existing proofs for zero-sum games.
To show that our example is not valued
we need that the existence of
$\epsilon$ equilibria for all positive $\epsilon$
implies
a ``perfection'' property. Should there exist a stochastic game
without an $\epsilon$ equilibrium for some $\epsilon >0$,
this perfection property
may be useful for demonstrating this fact. Furthermore our
example sows some doubt concerning the existence of
$\epsilon$ equilibria for two-person non-zero-sum stochastic games
with countably many states.

Keywords: Stochastic Games, Markov Chains, Rate of Martingale Convergence, Approximately Harmonic Functions