Robert Samuel Simon
A Proof of the Vieille Result using a Kind of Discount Factor
Preprint series: Mathematica Gottingensis

MSC:

90D15 Stochastic games

Abstract:
We give an alternative proof that
every two-person
non-zero-sum absorbing positive recursive
stochastic game with finitely many states
has approximate equilibria, a result proven
by Nicolas Vieille.
Our proof uses
a state specific discount factor which is similar to the
conventional discount factor only when there is only one non-absorbing
state. Additionally we show
that if the players engage in time homogeneous Markovian
behavior relative to some finite state space of size $n$ then
for the existence of an $\ep$-equilibrium it
suffices that one-stage deviation brings no more than
an $\ep^3/(nM)$ gain to a player,
where $M$ is a bound on the maximal difference between
any two payoffs.
Keywords: Stochastic Games, Markov Chains