The Asymptotic Solution of a Recursion Equation Occurring in Stochastic Games

We show that there exists a Laurent series in a fractional power of n which approximates V_n up to log n, where V_n is the value of an n-stage two person zero sum stochastic game. We prove this result by showing that the Laurent series is an approximate solution of the dynamical programming equation for Vn, V_n+1 = f(V_n). It seems that our methods could be used to find approximate solutions to other difference equations. Our proof makes repeated use of Tarski's principle for real closed fields.