In a two-person zero sum game, each of the two players is given a choice between several prescribed strategies at each turn, and each player's loss is equal to the other player's gain.

The payoff matrix of a two-person zero sum game has rows labeled by the row player's strategies and columns labeled by the column player's strategies. The ij entry of the matrix is the payoff that accrues to the row player in the event that the row player uses strategy i and the column player uses strategy j.

Paper, Scissors, Rock
Rock beats (crushes) scissors; scissors beat (cut) paper, and paper beats (wraps) rock.
Each +1 entry indicates a win for the row player, -1 indicates a loss, and 0 indicates a tie.

Do you want to play? Click on a row strategy...

		Column Strategy
Row Strategy			0	1	1
			1	0	1
			1	1	0

.

When analyzing any game, we make the following assumptions about both players:

1. Each player makes the best possible move.
2. Each player knows that his or her opponent is also making the best possible move

Consider the following game.

		Column Strategy
			A	B	C
Row Strategy	1		0	1	1
	2		0	0	2
	3		1	2	3

If the row player follows Principle 1, (s)he should never play Strategy 1 since Strategy 2 gives better payoffs no matter what strategy the column player chooses. (The payoffs in Row 2 are all at least as high as the coresponding ones in Row 1.)

Further, following Principle 2, the row player expects that the column player will never play Strategy A, since Strategy B gives better payoffs as far as the column player is concerned. (The payoffs in Column B are all at least as low as the coresponding ones in Column A.)

A player uses a pure strategy if he or she uses the same strategy at each round of the game.

One pure strategy dominates another if all its payoffs are more advantageous to the player than the corresponding ones in the other strategy. In terms of the payoff matrix, we can say it this way:

1. Row r in the payoff matrix dominates row s if each payoff in row r is the corresponding payoff in row s.
2. Column r in the payoff matrix dominates column s if each payoff in row r is the corresponding payoff in columns.

Consider the above game once again.

		Column Strategy
			A	B	C
Row Strategy	1		0	1	1
	2		0	0	2
	3		1	2	3

Since the entries in Row 2 are the corresponding ones in Row 1, Row 2 dominates Row 1.

Since the entries in Column B are the corresponding ones in Column A, Column B dominates Column A.

If one pure strategy is dominated by another, the player can ignore the dominated strategy without losing any advantage. Removing dominated rows and columns makes the game smaller and easier to analyze.

The procedure for eliminating all dominated rows and columns is called reduction by dominance and is carried out as follows:

1. Check whether there is any row in the matrix that is dominated by another row. If there is one, delete it.
2. Check whether there is any column in the (remaining) matrix that is dominated by another column. If there is one, delete it.
3. Repeat steps (1) and (2) in any order until there are no dominated rows or columns left.

If you are using Netscape or Explorer 3 or better, press here to bring up a Javascipt utility that will automatically reduce any game (up to 55) by dominance.

In the game above, we saw that Row 2 dominates Row 1, so the first step is to eliminate Row 1, leaving the following smaller game.

		A	B	C
2		0	0	2
3		1	2	3

Since Column B now dominates both Columns A and C, we follow Step 2 and eliminate Columns A and C, leaving the following even smaller game.

		B
2		0
3		2

Step 3 now tells us to repeat the first two steps. Notice that Row 2 now dominates Row 3 (even though it did not in the original game) we eliminate Row 3, leaving the following little 11 game. This is as far as the reduction can go.

If the payoff matrix of a game can be reduced to a 1 x 1 matrix by dominance, then the strategies labeling the row and column that are left are the optimal pure strategies for that game. If the payoff matrix does not reduce to a 1 x 1 matrix, then the optimal pure strategy for each player is obtained as follows.

Row Player: Box the minimum payoffs in each row and select the row or rows whose boxed payoffs are the largest.

Column Player: Circle the maximum payoffs in each column and select the column or columns whose circled payoffs are the smallest.

Row Player: Here is the game we considered above with the row minima in bold. The largest of these is in color, showing that Strategy 2 is the optimal pure row strategy.

		A	B	C
1		0	1	1
2		0	0	2
3		1	2	3

Column Player: Here is the same game with the column maxima in bold. The smallest of these is in color, showing that Strategies A and B are both optimal pure column strategies.

		A	B	C
1		0	1	1
2		0	0	2
3		1	2	3

A saddle point is a payoff that is simultaneously a row minimum and a column maximum. To locate saddle points, circle the row minima and box the column maxima. The saddle points are those entries that are both circled and boxed.

A game is strictly determined if it has at least one saddle point. The following statements are true about strictly determined games.

1. All saddle points in a game have the same payoff value.
2. Choosing the row and column through any saddle point gives optimal strategies for both players.

The value of a strictly determined game is the value of the saddle point entry. A fair game has value of zero, otherwise it is unfair or biased.

Row Player:In the above game, there are two saddle points, shown in color.

		A	B	C
1		0	1	1
2		0	0	2
3		1	2	3

Since the saddle point entries are zero, this is a fair game.

A mixed strategy is a method of playing a game where the rows or columns are played at random so that each is used a given fraction of the time.

We represent a mixed strategy for the row player by a row matrix (probability vector)

S = [a   b   c  . . . ]

A mixed strategy for the column player is represented by a similar column matrix T.

The expected value of the game with payoff matrix P corresponding to the mixed strategies S and T is given by

e = SPT

Here is a variant of "paper, scissors, rock in which "paper/paper" and "rock/rock" is no longer a draw.

		2	1	1
		1	0	1
		1	1	2

Suppose the row player uses the mixed strategy

S = [0.75   0   0.25]

T =		0
		0.5
		0.5		.

e	= SPT
	= [0.75   0   0.25]		2	1	1			0
			1	0	1			0.5
			1	1	2			0.5
	= -0.125

An optimal mixed strategy for the row player is a mixed strategy for which the lowest expected payoff (over all possible column player mixed strategies) is as large as possible. An optimal mixed strategy for the column player is a mixed strategy for which the highest expected payoff (over all possible row player mixed strategies) is as small as possible.

The process of finding optimal mixed strategies for both players is called solving the game.

Here are some facts about optimal mixed strategies:

1. In a strictly determined game, the optimal mixed strategies are pure strategies, and are the optimal pure strategies (see "Saddle Point, Strictly Determined Game" above).
2. Every game has optimal mixed strategies for both players.
3. If there is more than one optimal mixed strategy for one or both players, then that player may select any one mixed strategy. The expected value of the game does not depend on which optimal mixed strategy is used.
4. The value of a game is its expected value if optimal mixed strategies are used.

A fair game has value of zero, otherwise it is unfair or biased.

Look at the game immediately above. If you solve the game using the on-line game theory utility you will find that the optimal mixed strategies are:

  Optimal Row Strategy: S = [0.6   0   0.4]

Optimal Column Strategy: T =		0
		0.6
		0.4		.

With these mixed strategies, the value of the game is

e = 0.2

Q: How does the utility solve a game?
A: With the simplex method -- see below.

A game may be solved using the simplex method as follows.

Before you start, check for saddle points. If you find one, you have already solved the game; the optimal strategies are the pure strategies passing through a saddle point. Otherwise, continue with the following steps.

1. Reduce the payoff matrix by dominance.
2. Add a fixed number k to each of the entries so that they all become non-negative.
3. Set up and solve the associated linear programming problem using the simplex method.
4. Obtain the optimal strategies and the expected value as follows.

   Column Strategy

   1. Express the solution to the linear programming problem as a column vector.
   2. Normalize by dividing each entry of the solution vector by the sum of the entries, or by the value of the objective variable p.
   3. Insert zeros in positions corresponding to the columns deleted during reduction.
   
   Row Strategy
   1. Write down the row vector whose entries are the numbers appearing in the bottom row of the final tableau underneath the slack variables.
   2. Normalize by dividing each entry of the solution vector by the sum of the entries.
   3. Insert zeros in positions corresponding to the rows deleted during reduction.
   
   Value of the Game

   e = ¹/_p k.