Research Reports from the Department of Operations
Document Type
Report
Publication Date
8-1-1971
Abstract
There are two algorithms for the solution of two person zero sum stochastic games with a finite number of states or positions and where future payoffs are discounted. The first algorithm is on somewhat similar lines as that of Hoffman and Karp for the undiscounted case, and the second one is recently developed by Rao, Chandrasekaran and Nair. This paper presents computer programs for the two algorithms and computational experiments for comparing the efficiency of the algorithms. The results show that the second algorithm requires fewer iterations and moreover, the computation time for each iteration in this is significantly lower. Further the results show that the ratio of the computation time of the first algorithm to that of the second algorithm is nearly 2.3.
Keywords
Stochastic processes, Two-person zero-sum games, Algorithms, Game theory--Mathematical models, Mathematical optimization, Operations research
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 243
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Aggarwal, Vijaykumar V., "Algorithms for Discounted Stochastic Games: A Comparison of Efficiency" (1971). Research Reports from the Department of Operations. 13.
https://commons.case.edu/wsom-ops-reports/13