Article ID: | iaor1997982 |
Country: | United States |
Volume: | 43 |
Issue: | 7 |
Start Page Number: | 955 |
End Page Number: | 970 |
Publication Date: | Oct 1996 |
Journal: | Naval Research Logistics |
Authors: | Gass Saul I., Zafra Pablo M.R., Qiu Ziming |
The authors describe a modification of Brown’s fictitious play method for solving matrix (zero-sum two-person) games and apply it to both symmetric and general games. If the original game is not symmetric, the basic idea is to transform the given matrix game into an equivalent symmetric game (a game with a skew-symmetric matrix) and use the solution properties of symmetric games (the game value is zero and both players have the same optimal strategies). The fictitious play method is then applied to the enlarged skew-symmetric matrix with a modification that calls for the periodic restarting of the process. At restart, both players’ strategies are made equal based on the following considerations: Select the maximizing or minimizing player’s strategy that has a game value closest to zero. The authors show for both symmetric and general games, and for problems of varying sizes, that the modified fictitious play (MFP) procedure approximates the value of the game and optimal strategies in a greatly reduced number of iterations and in less computational time when compared to Brown’s regular fictitious play (RFP) method. For example, for a randomly generated 50% dense skew-symmetric 10×100 matrix (symmetric game), with coefficients ℝ