Solutions of stopping games for Markov chains.
by
Victor Domansky
St.Petersburg Institute of Economics and Mathematics, Russian Academy of Sciences, Tchaikovskogo 1, St.Petersburg, 191187 Russia

We consider a game theoretic formulation of stopping problem for Markov chain as it was introduced by E.Dynkin. Two players observe a Markov sequence x(n) with state space X and may stop it at any stage n. If the chain is stopped at state x Player 1 receives from Player 2 the amount depending on the state x and on the player who stopped the process. If the game continues infinitely Player 1 gets liminf c(x(n)) for a limit function c defined over X. Mixed behavior strategies for this game are randomized stopping moments for the chain. At any stage players should compare their gains in the case of stopping with their expected gains. Therefore, the value function v(x, c) of the game G(x, c), depending on the initial state x and on the limit function c, should be a solution of optimality equation - a fixed point of operator T acting over the measureable functions on X. The Dynkin paper and papers of his successors deal with the games for which optimality equations are solvable with use of pure strategies. We drop these assumptions and investigate optimality equation solvability by means of mixed strategies. We get sufficient conditions for existence of solutions for stopping games with use of randomized markovian stopping rules. We prove that if for any initial state the expectations of payoff suprema along the chain trajectory is finite, then the game has a value v(x, c) for all initial states x and for any limit function c. An iterative algorythm is developed for finding values and optimal randomized strategies of players. We indicate the procedure for constructing the initial approximation v(x, c, 0) of value and we prove that iterations of operator T applied to the function v(x, c, 0) converge to the value v(x, c). We consider a special class of stopping games. For these games the state space X is the set of positive integer numbers. The transition probability from the state n to the state n+1 is equal to p(n) and the chain terminates with probability 1-p(n). The explicit solutions are obtained for these games under certain hypotheses on payoffs.

Date received: May 14, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafc-46.