<<

. 26
( 59 .)



>>

f (x ) - for all + A and all 9 0. Hence f (x ) - 0 for all + A, contradic-
? ?
ting the hypothesis that f (x) - 0 has no solution in C. Thus the intersection
?
of the sets C is empty. Since C is compact, by Remark I.7.1 and Theorem
? C
I.7.3 there exists a ¬nite subcollection C , C ,...,C of +C , whose
? C ?‚ C‚ ?K CK ? C
intersection is empty. That is, the system f (x) 9 - 0, i : 1, . . . , m, has no
?G G
solution x in C. Therefore the system

f (x) 9 : 0, i : 1, . . . , m,
?G G
has no solution x in C. Therefore, by Theorem 4.1 and Remark 1, there exists
a vector p : (p , . . . , p ) with p " 0 and p . 0, i : 1, . . . , m, such that
 K G
K K
 p f (x) .  p 9 0 (8)
G ?G GG
G G
APPLICATION TO GAME THEORY 117


for all x in C. The function F de¬ned in (6) is continuous on the compact set
C and hence attains a minimum on C. From this and from (8) the conclusion
follows.

Remark 4.3. The reader who is familiar with the notion of semicontinuity will
see that the requirement that the functions f be continuous can be replaced
?
by the less restrictive requirement that they be lower semicontinuous.

Exercise 4.1. Verify that the set S in Theorem 4.1 is convex.

Exercise 4.2. Prove the following corollary to Theorem 4.1. Let f : ( f , . . . , f )
 K
be de¬ned and convex on RL. Let h : Ax 9 b be an af¬ne mapping from RL to
RI and let the rows of A be linearly independent. Then either

f(x) : 0, Ax 9 b : 0
I:

has a solution x in RL or

II: 1p, f(x)2 ; 1q, Ax 9 b2 . 0 all x + RL

has a solution (p, q) " 0, p + RK, p . 0, q + RI, but never both.


5. APPLICATION TO GAME THEORY

In this section we use Theorem 4.3 to prove the von Neumann minimax
theorem and then apply the minimax theorem to prove the existence of value
and saddle points in mixed strategies for matrix games. Our proof will require
the concept of uniform continuity and a suf¬cient condition for uniform
continuity.

De¬nition 5.1. A function f de¬ned on a set S in RL with range in RK is said
to be uniformly continuous on S if for each 9 0 there exists a 9 0 such that
if x and x are points in S satisfying #x 9 x# : , then #f(x) 9 f(x)# : .

T 5.1. L et S be a compact set in RL and let f be a mapping de¬ned and
continuous on S with range in RK. T hen f is uniformly continuous on S.

For a proof we refer the reader to Bartle and Sherbert [1999] or Rudin
[1976].

T 5.2 (V® Nµ®® M©®© T). L et X : RK and Y : RL be
compact convex sets. L et f : X ; Y ; R be continuous on X ; Y. For each x in
X let f (x, ) : Y ;R be convex and for each y + Y let f ( , y) : X ; R be concave.
118 CONVEX FUNCTIONS


T hen
max min f (x, y) : min max f (x, y), (1)
x+X y+Y y+Y x+X

and there exists a pair (x , y ) with x in X and y in Y such that for all x in
** * *
X and all y in Y

f (x, y ) - f (x , y ) - f (x , y). (2)
* ** *
Moreover, if v denotes the common value in (1), then f (x , y ) : v.
**
A pair (x , y ) as in (2) is called a saddle point of the function f.
**
The relation (1) is not true in general for continuous functions f de¬ned in
X ; Y, where X and Y are compact and convex. To see this, let X : [0, 1], let
Y : [0, 1], and let f (x, y) : (x 9 y). Then for ¬xed x, min+ f (x, y) : y + Y , is
achieved at y : x and equals zero. Hence in this example the left-hand side of
(1) equals zero. On the other hand, for ¬xed y in the interval [0, ]

max + f (x, y) : x + X, : (1 9 y),
V
and for ¬xed y in the interval [, 1]

max + f (x, y) : x + X, : y.
V
Hence in this example the right-hand side of (1) equals .

The concavity in X and convexity in Y is a suf¬cient condition but not a
necessary condition, as the example X : [0, 1], Y : [0, 1], and f (x, y) : eVeW
shows.
Before we take up the proof of Theorem 5.2, which will be carried out in
several steps, we observe the following. If A and B are arbitrary sets and g is
a real-valued bounded function de¬ned on A ; B, then the quantities

sup inf g(a, b) inf sup g(a, b)
and
a +A b + B b+B a+A

are well de¬ned, while the quantities

max min g(a, b) and min max g(a, b)
a+A b+B b+B a+A

need not be. For a simple example, take A : (0, 1), B : (0, 1), and g(a, b) : ab.
Thus, implicit in (1) is the statement, which must be proved, that the left- and
right-hand sides of (1) exist. The proof of this statement will constitute the
second step of our proof. The ¬rst step is the general observation given in
Lemma 5.1.
APPLICATION TO GAME THEORY 119


L 5.1. L et A and B be arbitrary sets and let g : A ; B ; R be bounded.
T hen
sup inf g(a, b) - inf sup g(a, b).
a +A b + B b+B a+A


Proof. Choose an element b + B. Then for each a + A,


g(a, b ) - sup g(a, b ).
 
a+A


Since the choice of b was arbitrary, this relationship holds for each a in A and

each b in B. Hence, for each a + A

inf g(a, b) - inf sup g(a, b).
b +B b+B a+A


The right-hand side is a ¬xed real number, so

sup inf g(a, b) - inf sup g(a, b).
a +A b + B b+B a+A


We now proceed to the second step of the proof and show that the left- and
right-hand sides of (1) exist.
For ¬xed x in X, the function f (x, ) : Y ;R de¬ned by f (x, y) is contin-
uous on the compact set Y. Hence

(x) : min f (x, y)
y+Y


is de¬ned for each x in X. We assert that the function is continuous on X.
To prove the assertion, let 9 0 be given. Since f is continuous on the compact
set X ; Y, it is uniformly continuous on X ; Y. Hence there exists a 9 0 such
that if #x 9 x # : , then
 

f (x , y) 9  : f (x , y) : f (x , y) ; 
 
  

for all y in Y. Upon taking the minimum over Y, we get that

(x ) 9  - (x ) - (x ) ;  ,
 
  

or " (x ) 9 (x )" : whenever #x 9 x # : . This proves the continuity
   
of .
120 CONVEX FUNCTIONS


is continuous on the compact set X, there exists and x in X such
Since
*
that

(x ) : max (x) : max min f (x, y) . (3)
* x+X x+X y+X


It follows from (3) that the left-hand side of (1) is well de¬ned.
From the de¬nition of we have

(x ) : min f (x , y). (4)
* *
y+Y


Similarly, for each y in Y we can set


(y) : max f (x, y)
x+X


and then obtain the existence of a y in Y such that
*


(y ) : min
(y) : min max f (x, y) (5)
* y+Y y+Y x+X


and


(y ) : max f (x, y ). (6)
* *
x+X


Thus the right-hand side of (1) is well de¬ned.
The third step in the proof is to establish the equality in (1). Let

: max min f (x, y), : min max f (x, y).
x+X y+Y y+Y x+X


By Lemma 5.1 with X : A, Y : B, f : g and by the second step, we have that
- . Hence to prove (1), we must show that . .
Let 9 0 be arbitrary. We assert that there does not exist a y in Y such

that for all x in X

f (x, y ) - 9 .

For if such a y did exist, we would have

: min max f (x, y) - max f (x, y ) - 9 ,

y+Y x+X x+X


which is not possible.
APPLICATION TO GAME THEORY 121


Let +gx,x + X be the family of functions de¬ned on Y by the formula

gx (y) : f (x, y), x + X.

Then for each x + X, the function gx is continuous and convex on Y. Moreover,
for arbitrary 9 0 the system

gx(y) 9 ; - 0, x + X, (7)

has no solution y in Y.
Since (7) has no solution, it follows from Theorem 4.3 that there exist points
x , . . . , x in X, a vector p + RI, p . 0, p " 0, and a 9 0 such that
 I
I
G(y) :  p [ f (x , y) 9 ; ] . 9 0 (8)
G G
G
for each y in Y. Since I p 9 0, we may divide through by this quantity in

<<

. 26
( 59 .)



>>