Zero Sum Two Person Games

by

Elmer G. Wiens

Egwald's popular web pages are provided without cost to users.
Please show your support by joining Egwald Web Services as a Facebook Fan:
Follow Elmer Wiens on Twitter:

Linear programming example | Zero sum two person game | Solve your own l.p. problem | Simplex method algorithm

Want to play a few games before you get at the theory? Click to play two person zero sum games.

Two person zero sum games can be solved using linear programming. I will solve the game by G. Hadley in Linear Programming. (427) to show, step by step, how to use this linear programming package to solve a two person zero sum game.

Call our players, player 1 and player 2. Suppose player 1 has r strategies and player 2 has s strategies. Let A(i, j) be the payoff if player 1 chooses strategy i and player 2 chooses strategy j. The matrix A is called the payoff matrix. To illustrate, suppose that player 1 has 3 strategies, player 2 has 5 strategies, and the payoff matrix A is given by:

If player 1 plays strategy 2, his payoff depends on which strategy player 2 has chosen to play. If player 2 knows player 1 is playing strategy 2, she should play her 4th strategy, because then she only pays him 1 unit. But if player 1 plays strategy 1 instead, she must pay him 9 units. I assume that players know the payoff matrix A, but that players 'announce' their strategies simultaneously. Player 1 wants to maximize the payoff; player 2 wants to minimize the payoff.

It is known that each player should determine the choice of strategy on the basis of a probability distribution over the player's list of strategies. That is, player 1 chooses row 1, 2, or 3 with probabilities X1, X2,and X3. Player 2 chooses the columns with probabilities Y1,Y2,Y3,Y4, and Y5. Note that the X's and Y's must be non-negative and each set must add to one.

To turn this into a linear programming problem write:

I have added an extra variable, X4, the expected payoff (the value) of the game.

The first equation is the objective function. Player 1 wants to maximize the objective function, the expected payoff.

Then there is an equation for each column of A. Why? Suppose player 2 plays her 1st strategy. Then the expected payoff to player 1 is:

As in my first example, we need to set some parameters for my program. n = 4 (the number of independent variables) m = 6 (the number of constraints) m1 = 0 (the number of <= constraints) m2 = 5 (the number of >= constraints) m3 = 1 (the number of = constraints)

From my first example, you now know what to do. You add slack variables to each constraint (if it is not already an equation) and then reduce it to 'restricted normal form'.

An observant person might notice that our Yj terms are doing double duty: first, as representing the strategy of player 2; second, as being slack variables. That is correct. The 'magic' of the L.P. algorithm is that the dual problem is solved simultaneously with the primal. When you solve the converted two person game, the Yj's that appear will be the optimal strategy for player 2.

You must convert your zero sum two person problem to the above form.

Recall the restrictions that apply to the parameters:
m = m1 + m2 + m3;   n <= 8;   m <= 15;   n > 0;
m > 0;   m1 >= 0;   m2 >= 0;   m3 >= 0.

Once you fill in the table below, another table will be displayed where you will be able to enter the data of your table.

Give your problem a name and enter it with the parameters into the table. Then click 'submit parameters'.

You can also solve a small linear programming problem with the Dual Simplex Method, using a user friendly interface.

Return to the Linear Programming entry page.

Return to egwald.com

References

• Hadley G., Linear Programming. Reading, Mass.: Addison-Wesley, 1962.