Summary
In this paper two-person zero-sum stochastic games are considered with the average payoff as criterion. It is assumed that in each state one of the players governs the transitions. We will establish an algorithm, which yields in a finite number of iterations the solution of the game i.e. the value of the game and optimal stationary strategies for both players. An essential part of our algorithm is formed by the linear programming problem which solves a one player control stochastic game. Furthermore, our algorithm provides a constructive proof of the existence of the value and of optimal stationary strategies for both players. In addition, the finiteness of our algorithm proves also the ordered field property of the switching control stochastic game.
Zusammenfassung
Wir betrachten stochastische Zweipersonen-Nullsummenspiele mit der durchschnittlichen Auszahlung als Kriterium. Wir nehmen an, daß in jedem Zustand einer der Spieler das Übergangsgesetz kontrolliert und entwickeln einen Algorithmus, der nach endlichen vielen Iterationsschritten die Lösung des Spiels — d. h. den Spielwert und optimale stationäre Strategien für beide Spieler — liefert. Ein wesentlicher Teil unseres Algorithmus besteht aus dem linearen Programm, das ein stochastisches Spiel löst, bei dem ein Spieler das Übergangsgesetz bestimmt. Darüber hinaus geben wir mit unserem Algorithmus einen konstruktiven Beweis der Existenz des Spielwertes und optimaler stationärer Strategien für beide Spieler. Weiter zeigt die Endlichkeit unseres Algorithmus die “ordered field property” stochastischer Spiele mit wechselnder Kontrolle des Übergangsgesetzes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bewley T, Kohlberg E (1978) On stochastic games with stationary optimal strategies. Math Oper Res 3:104–125
Derman C (1970) Finite state Markovian decision processes. Academic Press, New York
Federgruen A (1978) Markovian control problems. Ph.D. Dissertation, Math. Centre, Amsterdam
Filar JA (1979) Algorithms for solving some undiscounted stochastic games. Ph.D. Dissertation, University of Illinois, Chicago
Filar JA (1981) Ordered field property for stochastic games when the player who controls transitions changes from state to state. JOTA 34:503–515
Filar JA, Raghavan TES (1979) An algorithm for solving an undiscounted stochastic game in which one player controls transitions. Research Memorandum, University of Illinois, Chicago
Filar JA, Raghavan TES (1980) Two remarks concerning two undiscounted stochastic games. Technical Report No. 329, Department of Mathematical Sciences, The Johns Hopkins University, Baltimore
Hordijk A, Kallenberg LCM (1981) Linear programming and Markov games I. In: Moeschlin O, Pallaschke D (eds) Game theory and mathematical economics, pp 291–305
Hordijk A, Kallenberg LCM (1981) Linear programming and Markov games II. In: Moeschlin O, Pallaschke D (eds) Game theory and mathematical economics, pp 307–320
Hordijk A, Vrieze OJ, Wanrooij GL (1982) Semi-Markov strageties in stochastic games. Int J Game Theory (in press)
Parthasarathy T, Raghavan TES (1981) An orderfield property for stochastic games where one player controls transition probabilities. JOTA 33:375–392
Shapley LS, Snow RN (1950) Basic solutions of discrete games. Annals of Mathematics Studies 24. Princeton University Press, Princeton, pp 27–35
Stern MA (1975) On stochastic games with limiting average payoff. Ph.D Dissertation, University of Illinois, Chicago
Vrieze OJ (1981) Linear programming and undiscounted stochastic games in which one player controls transitions. OR Spectrum 3:29–35
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Vrieze, O.J., Tijs, S.H., Raghavan, T.E.S. et al. A finite algorithm for the switching control stochastic game. OR Spektrum 5, 15–24 (1983). https://doi.org/10.1007/BF01720283
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF01720283