Research Reports from the Department of Operations
Document Type
Report
Publication Date
7-1-1971
Abstract
In this paper, a two person zero sum stochastic game with a finite state space is considered. The movement of the game from state to state is jointly controlled by the two players depending on their choice of strategies from a finite number of alternatives available to each player in each of the states. Considering an infinite number of transitions, Hoffman and Karp provided a convergent algorithm for the solution of this game when the future payoffs are not discounted. Subsequently, the authors presented a proof for a faster algorithm available in literature for solving the same problem. This paper introduces discounting of future payoffs in the above stochastic game and presents two convergent algorithms for arriving at the optimal strategies for the players and the value of the game. Algorithm I is somewhat similar to the one developed by Hoffman and Karp for the undiscounted case while Algorithm II is based on an entirely different approach. From intuitive considerations it is seen that Algorithm II is significantly faster and this property is established by a well designed computational experiment. Finally, a possible extension to non-zero sum stochastic game is suggested.
Keywords
Stochastic processes, Two-person zero-sum games, Algorithms, Mathematical optimization, Decision making--Mathematical models, Game theory--Mathematical models, Operations research
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 236
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Subba Rao, S.; Chandrasekaran, R.; and Nair, K.P. K., "Algorithms for Discounted Stochastic Games" (1971). Research Reports from the Department of Operations. 11.
https://commons.case.edu/wsom-ops-reports/11