A decomposition approach for undiscounted two-person zero-sum stochastic games

Zeynep Müge Avsar, Melike Baykal-Gürsoy

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

Two-person zero-sum stochastic games are considered under the long-run average expected payoff criterion. State and action spaces are assumed finite. By making use of the concept of maximal communicating classes, the following decomposition algorithm is introduced for solving two-person zero-sum stochastic games: First, the state space is decomposed into maximal communicating classes. Then, these classes are organized in an hierarchical order where each level may contain more than one maximal communicating class. Best stationary strategies for the states in a maximal communicating class at a level are determined by using the best stationary strategies of the states in the previous levels that are accessible from that class. At the initial level, a restricted game is defined for each closed maximal communicating class and these restricted games are solved independently. It is shown that the proposed decomposition algorithm is exact in the sense that the solution obtained from the decomposition procedure gives the best stationary strategies for the original stochastic game.

Original languageEnglish (US)
Pages (from-to)483-500
Number of pages18
JournalMathematical Methods of Operations Research
Volume49
Issue number3
DOIs
StatePublished - Jun 1999

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Management Science and Operations Research

Keywords

  • Decomposition
  • Undiscounted stochastic games

Fingerprint Dive into the research topics of 'A decomposition approach for undiscounted two-person zero-sum stochastic games'. Together they form a unique fingerprint.

  • Cite this