Research Reports from the Department of Operations
Document Type
Report
Publication Date
1-1-1971
Abstract
In this paper a two person zero sum nonterminating stochastic game with a finite number of positions or states is considered. The movement of the game from state to state is jointly controlled by the two players depending on their choices of strategies from a finite number of alternatives in each state available to each player, respectively. Considering an infinite number of transitions, Hoffman and Karp have provided a convergent algorithm for the solution of this game. This paper presents a new convergent algorithm for the solution of the above game. The proof of convergence shows also the existence of a unique value for the stochastic game. Further, bounds on the errors in the calculated value of the game are derived. Computational experiment shows that this algorithm is considerably faster than that of Hoffman and Karp. For the same accuracy of solution, this algorithm takes lesser number of iterations, each iteration requiring less time than that of Hoffman and Karp, if both the algorithms start from the same point. In general, the computation times for the new algorithm and that of Hoffman and Karp are nearly in the proportion 1:2.6. Finally, a possible extension of this faster algorithm for solving non zero-sum stochastic game is indicated.
Keywords
Stochastic processes, Operations research, Game theory, Algorithms, Computational complexity, Two-person zero-sum games
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 215
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Nair, K.P. K.; Subba Rao, S.; and Chandrasekaran, R., "A Faster Algorithm for Nonterminating Stochastic Games" (1971). Research Reports from the Department of Operations. 203.
https://commons.case.edu/wsom-ops-reports/203