Iterative algorithms for two-person zero-sum games
Eagle, James N.
Washburn, Alan R.
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Dimitrov, Nedialko B.; Jordanov, Valentin T. (2012);Seeded Localized Averaging (SLA) is a spectrum acquisition method that averages pulse-heights in dynamic windows. SLA sharpens peaks in the acquired spectra. This work investigates the transformation of the original ...
McNelley, T.R.; Swisher, D.L.; Pérez-Prado, M.T. (Elsevier, 2002);Superplastic aluminum alloys are often classified according to the mechanism of microstructural transformation during annealing after deformation processing. In Al-Cu-Zr materials, such as Supral 2004, the presence of ...
Kanayama, Yutaka; Onishi, Masanori (IEEE, 1991-04);A few fundamental concepts useful for building a high-level mobile robot language are discussed. The method of describing a vehicle path by a sequence of configurations, the use of coordination transformation (or composition ...