Notes on Modeling: Session X: Zero-Sum Games

Prepared by:

Joseph Malkevitch
Mathematics Department
York College (CUNY)
Jamaica, NY 11451

email: 

malkevitch@york.cuny.edu

web page: 

http://york.cuny.edu/~malk/


Consider the zero-sum game below:

	Column I	Column II
Row 1	12	-4
Row 2	-6	2

What spinner would Row use to get her best outcome?

Since we have proved that for games of this kind it makes no difference what column does, when Row plays optimally the payoff to Row is the same. We can do the following calculation. Let p be the optimum fraction of the time that Row plays Row 1.

We have:

12p -6(1-p) = -4(p) + 2(1-p)

12p - 6 + 6p = -4p +2 -2p

24p = 8

p = 1/3

So when Row plays optimally she plays Row 1 (1/3 ) of the time and Row 2 the remaining two-thirds of the time.

What is the payoff to Row? 12(1/3) - 6(1-1/3) = 12/3 - 6(2/3) = 4-4 = 0.

What is Column's optimal spinner?

Column's payoff will be the same if the Row player plays Row 1 all the time or Row 2 all of the time. So, if q is the percentage of the time that Column plays Column 1 in optimal play, we have:

12q -4 (1-q) = -6q + 2(1-q)
12q -4 +4q = -6q + 2 -2q
24q = 6
q = 1/4

Substituting this into the payoff for column:

12(1/4) - 4(1-1/4) = 12/4 - 4(3/4) = 12/4 - 12/4 = 0

This game is fair. Note that the determinant of the entries in the matrix is zero. However, if both of the players deviate from their optimal mixed strategies we will get payoffs other than 0 in the long run.

The reason we can apply the method above is that we are invoking a previously proved result that when when either player is playing his/her optimal mixed strategy in a two person zero-sum game without a saddle point that what the other player does makes no difference in the payoff to the two players. If both players play their optimal mixed strategy, the payoffs for the players are an "equilibrium." This means that if one of the two players holds fixed in his/her action the other player can only do worse by deviating from his/her optimal mixed strategy.

It turns out that the theory of zero-sum games which can be represented by mxn matrices of payoffs is closely related to Linear Programming. The optimal mixed strategy for these games can always be found by solving a linear programming problem. This observation is due to John Von Neumann. In linear programming one optimizes the value of a linear function over a bounded region which is a convex polyhedron. The optimal value of a linear program must occur at a "corner point" of the polyhedron which represents the feasible region.