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

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.