1/11/00 10:30 am WASHBURN: GameTheory.

doc

point we would have computed in a 2×2 game where II had only the strategies corresponding

6 3

PAYOFF 2 4
4

3 3
v

1
0 0
0 x* 1
x

Figure 6-2

to lines 3 and 4. Consequently, we can solve this game by solving the game (a,b,c,d) =
(0,4,6,0): the solution is v = 2.4, x* = .6, and y* = .4. To verify that the original game has in
fact been solved, we construct Figure 6-3.

0 0 .4 .6
.6 9 3 0 4 2.4
.4 1 3 6 0 2.4
5.8 3 2.4 2.4

Figure 6-3

Note that:
• The only use of Figure 6-2 is to reveal which 2×2 game to solve.

14
1/11/00 10:30 am WASHBURN: GameTheory.doc

• As long as Player I uses (.6, .4), the payoff will be 2.4 if II uses (0, 0, y, 1 – y) for
any y. Nonetheless, the unique optimal strategy for II is (0, 0, .4, .6).
To solve an m×2 game, we follow a similar procedure except that (y*, v) is the lowest
point on the upper envelope of the m lines. There will always be some lowest point that is at
the intersection of a non-decreasing line and a non-increasing line. Player I can safely use
only these two lines, and the value of the game is the same as the value of the resulting 2×2
game. For example,
1
4 4

3 3
4 0
The game: 3 1 The graph: 2 v
0 4
1

0 0
y*

Figure 6-4

Since all 3 lines go through the minimum point on the upper envelope, we can “cross out”
either row 1 or row 2 (but not row 3!) from the original game. If row 1 is crossed out, the
solution is x* = (0, 2/3, 1/3), y* = (.5, .5), and v = 2. If row 2 is crossed out the solution is
x* = (.5, 0, .5), y* = (.5, .5), and v = 2. The optimal strategy for Player I is not unique (any
average of (0, 2/3, 1/3) and (.5, 0, .5) is also optimal), but v and y* are. Of course, similar
things can happen in 2×n games, except that the non-uniqueness is in y*.

7. Dominance
Compare columns 1 and 4 in Figure 6-3. Each element of column 4 is smaller than the
corresponding element of column 1, so II prefers column 4 to column 1 no matter what row
is chosen by Player I. Column 4 dominates column 1, so column 1 can be “crossed out” — II

15
1/11/00 10:30 am WASHBURN: GameTheory.doc

will use it with probability 0 in his optimal strategy. More generally, column j dominates
column k if aij ≤ aik for all i. Similarly, Player I will not use row k if it is uniformly smaller
than row i; row i dominates row k if aij ≥ akj for all j. Roughly speaking, large columns and
small rows can be safely removed from the payoff matrix. There is no instance of row
dominance in Figure 6-3, but consider Figure 7-1. In diagram a, column 4 dominates column
2, and row 2 dominates row 3. If column 2 and row 3 are crossed out, diagram b results.
Notice that column 3 dominates columns 1 and 4 in diagram b, even though it did not in
diagram a. Crossing out these two columns results in diagram c. There is no further
dominance in diagram c, but the game can now be solved using the procedures of Section 6.
The value of the game is 3.8; the optimal solution and a verification of that solution are
shown in diagram d.
The principal value of the dominance idea is to reduce the effective size of the game.
Actually, if any linear combination of rows dominates row k, where the weights in the linear
combination form a probability distribution, then row k can be eliminated. Similarly for
columns. For example, column 2 in Figure 6-3 is not dominated by any other column, but it
is dominated by .5 of the third column plus .5 of the fourth; with this observation, that game
can be solved directly as a 2×2 game.
Exercises

1. Solve all of the games in Figure 3-2.

2. There are two contested areas, and the attacker (I) and defender (II) must each secretly
divide their units between the two areas. The attacker captures an area if and only if he
assigns (strictly) more units than the defender. The payoff is the number of areas captured
by the attacker. The attacker has 3 units and the defender has 4. Construct the payoff
matrix (it should have 4 rows and 5 columns), and solve the game. This is an example of
a “Blotto” game.

16
1/11/00 10:30 am WASHBURN: GameTheory.doc

1 4 0 2 9
3 6 2 2 8
a)
1 1 2 0 3
7 6 5 6 1

1 0 2 9
3 2 2 8
b)

7 5 6 1

0 9
2 8
c)

5 1

0 0 .7 0 .3
0 1 4 0 2 9 2.7
.4 3 6 2 2 8 3.8
d)
0 1 1 2 0 3 2.3
.6 7 6 5 6 1 3.8
5.4 6.0 3.8 4.4 3.8

Figure 7-1

3. Modify Figure 3-2d to reflect the idea that Player II has an intelligence network that will
be successful in discovering I’s strategy choice with probability .5. A typical strategy for

17
1/11/00 10:30 am WASHBURN: GameTheory.doc

II is now “choose column j if intelligence fails, else choose the best reaction to I’s row
choice.” The new game should still be a 3×3. Solve it.
4. The same as Exercise 3 except use 3-2c.

8. Completely Mixed Square Games

It sometimes happens that it is clear from the description of a game that every strategy
will be used with positive probability. In this case, we say that the game is completely mixed.
Obtaining the solution of such a game amounts to solving some simultaneous linear
equations. For example, consider the game in Figure 8-1.

1/2 0 0
0 2/3 0
0 0 3/4

Figure 8-1

One interpretation of this game is a hide-and-seek situation where Player I must guess which
of 3 cells II is hidden in, and where the probability of detection is not 1 even if Player I
guesses correctly (before reading further, make a guess at which row will be used most often
by Player I). There is no dominance, so the game cannot be reduced. Suppose Player I were
to use any mixed strategy that avoids some row entirely, and announce it (as he can safely do
if the strategy is optimal) to II. Then II would play that column always, and the resulting
probability of detection would be 0, which is clearly less than the value of the game.
Therefore, Player I will not avoid any row entirely; that is, x1* > 0 , x2* > 0 , and x3* > 0 . Let
vi = ∑ j aij y *j for i = 1,2,3, and let v be the value of the game. vi is the probability of
detection when Player I uses row i against II’s optimal mixed strategy. We must have vi ≤ v
and also ∑i xi*vi = v . Since xi* > 0 , the only way this can be true is if vi = v for all i (the only
way a positively weighted average of several numbers can be v when none of them is larger

18