Premium
Modified fictitious play
Author(s) -
Gass Saul I.,
Zafra Pablo M. R.,
Qiu Ziming
Publication year - 1996
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199610)43:7<955::aid-nav2>3.0.co;2-c
Subject(s) - combinatorial game theory , mathematics , symmetric game , fictitious play , normal form game , matrix (chemical analysis) , skew , repeated game , skew symmetric matrix , sequential game , zero (linguistics) , example of a game without a value , game theory , mathematical optimization , combinatorics , mathematical economics , symmetric matrix , computer science , physics , telecommunications , linguistics , eigenvalues and eigenvectors , materials science , philosophy , quantum mechanics , square matrix , composite material
We 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. We 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 100 × 100 matrix (symmetric game), with coefficients | a ij | ≤ 100, it took RFP 2,652,227 iterations to reach a gap of 0.03118 between the lower and upper bounds for the game value in 70.71 s, whereas it took MFP 50,000 iterations to reach a gap of 0.03116 in 1.70 s. Improved results were also obtained for general games in which the MFP solves a much larger equivalent symmetric game. © 1996 John Wiley & Sons, Inc.