<<

. 27
( 59 .)



>>

G G
(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

<<

. 27
( 59 .)



>>