(8) and assume that p + P . Therefore, since X is convex, I p x is in X.

G G G

I

Using (8) and the concavity of f ( , y) for each ¬xed y, we may write

I I

f p x , y . p f (x , y) 9 9

GG G G

G G

for each y in Y. Therefore,

I

: max min f (x, y) . min f p x ,y

GG

x+X y+Y y+Y

G

I

. min p f (x , y) 9 9 .

G G

y+Y

G

Since 9 0 is arbitrary, we get that . , and (1) is established.

The ¬nal step in the proof is to show that v : f (x , y ) and that (2) holds.

**

It follows from (1), (3), and (5) that

(x ) :

(y ) : v.

*

*

It now follows from (4) and (6) that

f (x, y ) - v - f (x , y) (9)

* *

for all x in X and y in Y. In particular, (9) holds for x : x and y : y , so that

* *

v : f (x , y ). The relation (2) now follows from (9).

**

122 CONVEX FUNCTIONS

The simplest two-person zero-sum games are matrix games. These games

are played by two players that we shall call Blue and Red. Blue selects a

positive integer i from a ¬nite set I of positive integers +1, . . . , m,. Red,

simultaneously and in ignorance of Blue™s choice, selects a positive integer j

from a ¬nite set J of positive integers +1, . . . , n,. The ˜˜payoff™™ or ˜˜reward™™ to

Blue in the event that he chooses i and Red chooses j is a predetermined real

number a(i, j). The payoff to Red is 9a(i, j). Hence the name zero-sum game.

A strategy for Blue is a rule which tells Blue which positive integer i in I to

select. A strategy for Red is a rule which tells Red which positive integer j in J

to select. Blue™s objective is to choose i in I so as to maximize a(i, j). Red™s

objective is to choose j in J so as to minimize a(i, j), that is, to maximize

9a(i, j). If the strategy for Blue is to choose the number i in I, then we call

the strategy a pure strategy for Blue. Similarly, if the strategy for Red is to

choose the number j in J, then we call the strategy a pure strategy for Red.

Later we shall consider strategies that are not pure.

Another way of describing a matrix game is as follows. An m ; n matrix A

with entries a(i, j), i : 1, . . . , m, j : 1, . . . , n, is given. Blue selects a row i and

Red selects a column j. The choices are made simultaneously and without

knowledge of the opponent™s choice. If Blue selects row i and Red selects

column j, then the payoff to Blue is a(i, j) and the payoff to Red is 9a(i, j).

Blue™s objective is to maximize the payoff, while Red™s objective is to minimize

the payoff.

At this point, the formulation of a matrix game may strike the reader as

rather arti¬cial and uninteresting. It turns out, however, that many decision

problems in con¬‚ict situations can be modeled as matrix games. As an

example, we shall formulate a tactical naval problem as a matrix game. The

reader will ¬nd many additional interesting examples elsewhere [Dresher,

1961]. The naval game appears there as a land con¬‚ict game called Colonel

Blotto.

Two Red cargo ships are protected by three escort frigates under the

command of Captain Pluto. The entire convoy is subject to attack by a pack

of four Blue submarines under the command of Captain Nemo. The ships carry

a hazardous cargo and thus maintain a separation such that one submarine

cannot attack both ships. Captain Nemo™s problem is to allocate his submar-

ines to attack the two ships. Thus, he may allocate all four of his submarines

to attack one of the ships and none to attack the second ship. Or, he may

allocate three submarines to attack one ship and one submarine to attack the

second ship. Or, he may allocate two submarines to attack each of the ships.

We may summarize the choices, or strategies, available to Captain Nemo by

¬ve ordered pairs, (4, 0), (0, 4), (3, 1), (1, 3), (2, 2), where ( , ) indicates that he

has allocated submarines to attack ship 1 and submarines to attack ship 2.

Captain Pluto™s problem is to allocate his frigates to defend the ships. He has

four choices, or strategies, each of which can be denoted by an ordered pair

( , ), 0 - - 3, 0 - - 3, ; : 3, where frigates are allocated to defend

ship 1 and frigates are allocated to defend ship 2. We assume that conditions

APPLICATION TO GAME THEORY 123

are such that when Captain Nemo allocates his submarines, he cannot

determine the disposition of the escort frigates, and that when Captain Pluto

allocates his escort frigates, he cannot determine the disposition of the

attacking submarines.

If at a given ship the number of attacking submarines exceeds the number

of defending frigates, then the payoff to Blue at that ship equals the number of

Red frigates at that ship plus 1. The ˜˜plus 1™™ is awarded for the cargo ship that

is assumed to be sunk. If at a given ship the number of attacking submarines

is less than the number of defending frigates, then the payoff to Blue at the

ship is

9(Number of attacking submarines ; 1).

The ˜˜plus 1™™ is deducted for allowing the cargo ship to proceed to its

destination. If at a given ship the number of attacking submarines equals the

number of defending ships, then the encounter is a draw, and the payoff to Blue

at that ship is zero. The total payoff to Blue resulting from given choices by

the two antagonists is the sum of the payoffs at each ship. The payoff to Red

is the negative of the payoff to Blue.

The game just described can be cast as a matrix game with payoff matrix

Captain Pluto™s strategies

(3, 0) (0, 3) (2, 1) (1, 2)

(4, 0) 4 0 2 1

Captain Nemo™s (0, 4) 0 4 1 2

.

(3, 1) 91

strategies 1 3 0

(1, 3) 91 1 0 3

(2, 2) 92 92 2 2

A strategy for Blue (Captain Nemo) is a choice of row; a strategy for Red

(Captain Pluto) is a choice of column.

If Captain Nemo chooses row i, he is guaranteed a payoff of at least

min+a(i, j) : j : 1, . . . , 4,.

If he picks the row that will give the payoff

v\ Y max min a(i, j),

G H

then he will be guaranteed to obtain v\. Captain Nemo can thus pick either

row 1 or row 2 and be guaranteed a payoff of at least zero. Thus v\ : 0.

On the other hand, if Captain Pluto chooses column j, he will lose at most

124 CONVEX FUNCTIONS

max+a(i, j) : i : 1, . . . , 5,. If Captain Pluto picks the column that gives Blue the

payoff

v> : min max a(i, j),

H G

then he is guaranteed to lose no more than v>. Captain Pluto can thus pick

either column 3 or 4 and be guaranteed to lose no more than three. Thus

v> : 3.

Note that if Captain Nemo knows beforehand that Captain Pluto will pick

column 3, then he can pick row 3 and obtain a payoff of 3, which is greater

than v\ : 0. On the other hand, if Captain Pluto knows beforehand that

Captain Nemo will pick row 2, then he can pick column 1 and lose zero units,

which is less of a loss than three units (v> : 3). An examination of the payoff

matrix shows that if one of the commander™s choice is known in advance by

the second commander, than the second commander can usually improve his

payoff if he bases his choice on this information. Thus, in the submarine”

convoy game secrecy of choice is essential. The open question, however, in the

submarine”convoy game is, ˜˜What is the best strategy for each player?™™

In contrast to the submarine”convoy game, consider the game with payoff

matrix

3 743

13 10 7 8

.

10 4 1 9

3 567

Here

max min a(i, j) : min max a(i, j) : 7.

G H H G

The strategies i : i , where i : 2, and j : j , where j : 3, have the

* * * *

properties that a(i , j ) : 7 and

**

a(i, j ) - a(i , j ) - a(i , j)

* ** *

for all i : 1, . . . , 4 and j : 1, . . . , 4. We say that the value of the game is 7, that

i : 2 is an optimal (pure) strategy for Blue, and that j : 3 is an optimal

* *

(pure) strategy for Red. If Blue chooses his optimal strategy i : 2, then the

*

best that Red can do is to also choose his optimal strategy j : 3. Also, if Red

*

chooses his optimal strategy j : 3, then the best that Blue can do is to choose

*

his optimal strategy i : 2. Thus, if either player announces beforehand that

*

he will choose an optimal strategy, the opponent cannot take advantage of this

information, other than to choose an optimal strategy.

APPLICATION TO GAME THEORY 125

We now consider the general matrix game with m ; n payoff matrix A with

entries a(i, j), i : 1, . . . , m, j : 1, . . . , n. We always have

v\ : max min a(i, j) - min max a(i, j) Y v>.

G H H G

If the reverse inequality v> . v\ holds, then we set

v : min max a(i, j) : max min a(i, j)

H G G H

and say that the matrix game has a value v in pure strategies. It is easy to show

that if the matrix game has a value v in pure strategies, then there exists a pair

(i , j ) such that

**

v : a(i , j ), (10)

**

and for all i : 1, . . . , m, j : 1, . . . , n,

a(i, j ) - a(i , j ) - a(i , j). (11)

* ** *

The strategies i and j are called optimal (pure) strategies. We point out that

* *

optimal strategies need not be unique. A pair of strategies (i , j ) such that (11)

**

holds is called a saddle point in pure strategies. It is also easy to show that if

a matrix game has a saddle point in pure strategies, then the game has value

v and (10) holds.

If the matrix game has a value, then each player should use an optimal

strategy. For then, Blue, the maximizer, is guaranteed a payoff of v and Red,

the minimizer, is guaranteed to lose at most 9v. If one player, say Blue, uses

an optimal strategy and Red does not, then the payoff to Blue, who plays

optimally, will, in general, be more favorable than it would be had Red played

optimally. This is the content of (11).

The question that still thrusts itself upon us is, ˜˜How does one play if the

game does not have a saddle point, as in the submarine”convoy game?™™ To

answer this question, we introduce the notion of mixed strategy.

De¬nition 5.2. A mixed strategy for Blue in the game with m ; n payoff matrix

A is a probability distribution on the rows of A. Thus, a mixed strategy is a

vector x : (x , . . . , x ) with x . 0, i : 1, . . . , m, and K x : 1.

G G

K G

A mixed strategy for Red is a probability distribution on the columns of A.

Thus, a mixed strategy for Red is a vector y : (y , . . . , y ) with y . 0, i :

L G

1, . . . , n, and L y : 1.

G G

The set of pure strategies for a player is a subset of the set of mixed

strategies. For example, the pure strategy for Blue in which row i is always

126 CONVEX FUNCTIONS

chosen is also the mixed strategy in which row i is chosen with probability 1,

that is, the vector e : (0, . . . , 0, 1, 0, . . . , 0), where the ith entry is 1 and all

G

other entries are zero.

In actual play, Blue will select his row using a random device which

produces the value i with probability x , i : 1, . . . , m. Blue chooses row i if the

G

random device produces the value i. Red chooses column j in similar fashion.

If mixed strategies are used, neither player tries to outguess his opponent and

both trust to luck. Moreover, if Blue uses a mixed strategy, Red cannot

determine Blue™s choice beforehand and take advantage of this information. A

similar statement holds if Red uses a mixed strategy.

If mixed strategies are allowed, then it is appropriate to de¬ne the payoff of

the matrix game with mixed strategies as the expected value of the payoff. Thus,

if we denote the payoff resulting from the choice of strategies (x, y) by P(x, y),

we have

P(x, y) : xRAy : 1x, Ay2. (12)

We de¬ne the matrix game with matrix A in which mixed strategies are used

as follows. Blue selects a vector x in P , and Red selects a vector y in P . The

K L

payoff to Blue is given by (12), and the payoff to Red is 9P(x, y). We say that

the matrix game with mixed strategies has a value if

max min P(x, y) : min max P(x, y). (13)

x+P y+P y+P x+P