Iterative algorithms for two-person zero-sum games

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.