Iterative algorithms for two-person zero-sum games
Loading...
Authors
Limsakul, Piya
Subjects
Advisors
Eagle, James N.
Washburn, Alan R.
Date of Issue
1999-03
Date
March, 1999
Publisher
Monterey, California ; Naval Postgraduate School
Language
en_US
Abstract
In 1951, G.W. Brown proposed an iterative algorithm called fictitious play for solving two-person zero-sum games. Although it is an effective method, the fictitious play algorithm converges slowly to the value of the game. Recently, Gass, Zafra, and Qiu proposed a modification that applies to symmetric games, i.e., games with skew-symmetric payoff matrices. To solve non-symmetric games via their modification, the games must be made symmetric via a transformation. Gass, Zafra, and Qiu reported that their modified algorithm converges faster than the original fictitious play on a collection of randomly generated games. However, their results on non-symmetric games only apply to games whose values are near zero. When game values are far away from zero, this thesis empirically shows that the original fictitious play algorithm can outperform the modified one. Gass, Zafra, and Qiu's method is static, in that the symmetric transformation is done once prior to the start of their modified algorithm. However, they suggested the exploration of dynamic methods where the transformation is periodically revised. This thesis proposes and investigates the convergence behavior of one dynamic transformation technique for solving general two-person zero-sum games.
Type
Thesis
Description
Series/Report No
Department
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
vii, 50 p.;28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.