Economic and Game Theory
Forum

Editors: David K. Levine, Wolfgang Pesendorfer

top | general | research | classes | links | David

Rules Forum Contributors [For contributors only]

Topics

Applications
Auctions
Bargaining
Experimental Economics
Forum
General Equilibrium
Napster
other
Other Topics
Prisoners Dilemma
Zero Sum Games

Thread and Full Text View

There is a program to solve zero sum games on this site at http://levine.sscnet.ucla.edu/Games/zerosum.htm. This program uses the fact that finding the value of a zero sum game is equivalent to solving a linear programming problem. Unfortunately, I cannot release the source code for the program because it solves linear programs using the simplex method, and the source code for the simplex method is taken from Numerical Recipes. Their license agreement does not allow me to redistribute this source code.

The zerosum program does not provide all the information you want because it provides the strategies for the second player only, and it does not compute the value. However, you can easily get the remaining information you need from the program. For example, consider payoffs to the first player of

1	2
3	-4

Using the solver, we find the optimal player 2 strategy is .75, .25. These are the probabilities of columns. To find the value, calculate the payoff to rows when these are the column probabilities. The first row gives 1*.75+2*.25=1.25; the second row gives 3*.75-4*.25=1.25. The fact that both rows give the same payoff is typical of optimal player two strategies. The value of the game (to player 1) is the largest of these row payoffs, in this case 1.25.

To find the optimal player 1 strategies, we simply reverse the role of the players, plugging in the payoff matrix with rows and column interchanged and the negative of the original payoffs

-1	-3
-2	4

From this we find the optimal strategy for the original player 1 of .875, .125.

Your question asked not just about programs to find optimal strategies and the value, but also about a particular method of solution, called iterated play. This method, more commonly known as fictitious play, has each player start with an arbitrary play in the first period. In each subsequent period, the player believes that his opponent will play the average frequency used in past periods, and plays a best response to it. In zero-sum games this method converges to the optimal strategies. It need not for non-zero sum games, as shown by an example of Shapley [Shapley, L. [1964]: "Some Topics in Two-Person Games," Advances in Game Theory, M. Drescher, L.S. Shapley, and A.W. Tucker, Princeton University Press]. Convergence in the zero sum case was first shown by Brown [Brown, G. W. [1951]: "Iterative Solutions of Games by Fictitious Play," Activity Analysis of Production and Allocation, T.C. Koopmans,  Wiley].

To the best of my knowledge no one has implemented the fictitious play method on the computer to solve zero sum games. The reason for this is that the iterative method can be quite slow, so the simplex method is preferred.