? ?

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‚ ?KCK ?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