NATIONAL BUREAU OF STANDARDS REPORT

210**

MINIMAX THEOKEMS

by

Ky Fan

<NBS>

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE

Charles Sawyer, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. Astin, Director THE NATIONAL BUREAU OF STANDARDS

* The scope of activities of the National Bureau of Standards is suggested in the following listing of

the divisions and sections engaged in technical work. In general, each section is engaged in specialized research, development, and engineering in the field indicated by its title. A brief description

of the activities, and of the resultant reports and publications, appears on the inside of the back

cover of this report.

Electricity. Resistance Measurements. Inductance and Capacitance. Electrical Instruments. Magnetic Measurements. Applied Electricity. Electrochemistry.

Optics and Metrology. Photometry and Colorimetry. Optical Instruments. Photographic

Technology. Length. Gage.

Heat and Power. Temperature Measurements. Thermodynamics. Cryogenics. Engines and

Lubrication. Engine Fuels. Cryogenic Engineering.

Atomic and Radiation Physics. Spectroscopy. Radiometry. Mass Spectrometry. Solid State

Physics. Electron Physics. Atomic Physics. Neutron Measurements. Infrared Spectroscopy.

Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation. Radiological Equipment. Atomic Energy Commission Instruments Branch.

Chemistry. Organic Coatings. Surface Chemistry. Organic Chemistry. Analytical Chemistry.

Inorganic Chemistry. Electrodeposition. Gas Chemistry. Physical Chemistry. Thermochemistry. Spectrochemistry. Pure Substances.

Mechanics. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydraulics. Mass. Capacity, Density, and Fluid Meters. Organic and Fibrous Materials. Rubber. Textiles. Paper. Leather. Testing and Specifications. Polymer Structure. Organic Plastics. Dental Research.

Metallurgy. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy. Corrosion.

Mineral Products. Porcelain and Pottery. Glass. Refractories. Enameled Metals. Concreting Materials. Constitution and Microstructure. Chemistry of Mineral Products.

Building Technology. Structural Engineering. Fire Protection. Heating and Air Conditioning. Floor, Roof, and Wall Coverings. Codes and Specifications.

Applied Mathematics. Numerical Analysis. Computation. Statistical Engineering. Machine

Development.

Electronics. Engineering Electronics. Electron Tubes. Electronic Computers. Electronic

Instrumentation.

Radio Propagation. Upper Atmosphere Research. Ionospheric Research. Regular Propagation Services. Frequency Utilization Research. Tropospheric Propagation Research. High

Frequency Standards. Microwave Standards.

Ordnance Development. These three divisions are engaged in a broad program of research

Electromechanical Ordnance, and development in advanced ordnance. Activities include

Electronic Ordnance. basic and applied research, engineering, pilot production, field testing, and evaluation of a wide variety of ordnance materiel. Special skills and facilities of other

NBS divisions also contribute to this program. The activity is sponsored by the Department of

Defense.

Missile Development. Missile research and development: engineering, dynamics, intelligence,

instrumentation, evaluation. Combustion in jet engines. These activities are sponsored by the

Department of Defense.

© Office of Basic Instrumentation • Office of Weights and Measures.
NATIONAL BUREAU OF STANDARDS REPORT

KBS PROJECT

- KBS REPORT

1 1 02-20-1 1 04 December 10, 1952 2104

MINIMAX THEOREMS

by

Ky Fan

University of Notre Dame

American University

The publication, reprinting Approved for public release by the

unless permission is obtains Director of the National Institute of

25, d, c, Such permission Standards and Technology (NIST)

cally prepared If that agen on October 9, 2015

t, Is prohibited

ds, Washington

as been speclfior its own use.
>
MINIMAX THEOREMS*

by

Ky Fan

Department of Mathematics, University of Notre Dame

Various generalizations of von Neumann’s minimax theorem^

2 2 have been given by several authors (J. Ville , A, Wald , 2 ^ h- S» Karlin , H. Kneser , K. Fan ). In all these theorems, the

structure of linear spaces is always present. This Note contains some new minimax theorems involving no linear space.

1Let f be a real-valued function defined on the product

set X X Y of two arbitrary sets X,Y (not necessarily topologized)

f is said to be convex on X , if for any two elements x^ ,x 2 £ X

and two numbers :>, 0, f

2 > 0 with f

^ + ?2 = 1 » there exists

an element x

q £ X such that f(xQ ,y) < ?1 f(x1 ,y) + *? 2f(x2

,y)

for all y £ Y. Similarly f is said to be concave on Y , if for

1

Von Neumann, J. , "Zur Theorie der Gesellschaf tsspiele" , Math.

Annalen . 100, 295-320 (1928); von Neumann, J. , and Morgens tern, 0.

,

Theory of Games and Economic Behavior , Princeton Univ. Press,

Princeton, 19^» pp« 1 53-1 55

2. For the references concerning minimax theorems of J. Ville,

A. Wald and S. Karlin, see the Bibliography in Contributions to

the Theory of Games , edited by H.W.Kuhn and A. W. Tucker, Princeton Univ. Press, Prince^on^ 1950.

3. Kneser, H., "Sur un theoreme fondamental de la theorie des

jeux", C.R.Acad.Sci, Paris , 23^, 24l 8-24-20 (1952).

4. Fan, K. , "Fixed-point and minimax theorems in locally convex

topological linear spaces", Proc. Nat. Acad , Sci , , 38 , 121-126

(1952).

This work was perforated in' part under the sponsorship of toe Pi

of Naval Research, and in part under a National Bureau of Standard

contrac t .with American University w.V'H the sponsorship of the Air

Research and Development Command, ’.]• . . . .
2

any two elements ,y 2 Y and two numbers ^0, ^ ^ 0 with

*?1 + ^

= 1 , there exists an y Q

€, Y such that f(x,y

o

> > ^

f ( x >y-|)

+ 72f ( x >y2^ * or x € X,

THEOREM 1 . Let X,Y be two compact Hausdorff spaces and f

a real-valued function defined on X x Y. Suppose that, for every

y€Y9 f(x,y) is lower semi-continuous (l.s.c.) on X; and for

every x €. X,f(x,y) is upper semi-continuous (u.s.c.) on Y»

Then ;

(i) The equality

min max f(x,y) = max min f(x,y) (1)

x€X y £ Y y <=Y x € X

holds, if and only if the following condition is satisfied ; For any two finite sets (x^ , x

2

, . * . ,x n

) C X and

{y1 ,y 2

, • • • »ymi C Y, there exist x

Q £ X and y Q

€. Y such that

f ^ x

o

,y k^ «

f ( x i»y0

)» (1 < i < n, 1 < k < ra) (2)

(ii) In particular, if f is convex on X and concave on Y,

then (1 ) holds . Proof ; Observe first that, regardless of the condition

stated in (i) , the expressions on both sides of (1) are meaningful. In fact, for each x €. X, f(x,y) is u.s.c. on the

compact space Y, so that max f(x,y) exists. As maximum of a y€ Y

family of l.s.c. functions on X, max f(x,y) is a .L , s . c . f unc tion

y € Y

on the compact space X and therefore min max f(x,y) exists.

x€X ye Y

(i) The necessity of the condition being trivial, we only

prove its sufficiency. According to this condition,
3

min max f(x,y.) < max min f(x.,y)

xeX 1<k<m K 'yfeY 1<i<n 1

hold for any two finite sets {x^ , X

2 >... ? x

n } C X and

{y 1 ^ Yo Th en any real number or satisfies at least

one of the two inequalities

min max f(x,y.) < Of, max min f(x.,y) > 0( x€X 1<k<m = y € Y 1<i^n 1

Let L(y; a ) = {x £ X I f(x,y) £ aj , U(x; (X) = {y£Y I f(x,y)

which are closed subsets of X,Y respectively. Then for any real

Of and any two finite sets {x

1 ,x 2

) • . • ,x

n

} C X,

{y -1 c Y, the two intersections L( y k

; 0() and

n

iQ1 U(x^; (X) are never both empty. As X,Y are compact, it

follows that for any real Of, at least one of the two intersections Qy

L(y; Of ) and U( x 5 °f) is not empty. That is,

either there exists x

Q Q X such that f(x

Q ,y) £ Of for all y£Y,

or there exists y Q

E Y such that f(x,y

Q

) £ Of for all x £ X.

In other words, any real Of satisfies at least one of the two

inequalities

rain max f(x,y) < Of , max min f(x,y) >. <x, x £ X y£Y y£Y x£X

Hence min max f(x,y) < max min f(x,y) and therefore (1).

x€X y£Y "y€Y x£X

(ii) Assume now that f is convex on X and concave on Y.

In order to prove (1), it suffices to verify the condition stated

in (i). Let{x

1 ,x 2

, . . . ,x

n

) C x and [y 1 ,y 2

> • • • >ym ] C Y be

1

’ given. By von Nuemann's minimax theorem , there exist two sets
ii Ms

’ m

k= 1 \ = 1

j o£ nonnegative numbers with

such that

max

1 <k<m

f(x. ,y k ) < min

'1<i<n £ ^k f ^ x

i

,y k^

k=i

( 3 )

Since f is convex on X and concave on Y,7 there exist x 6X, y 6Y o

7 o such that

*(x

0 ,yk

> < ,2» ^ f(xi ,y k

) , ( 1 <k^m)

m

f( x i>y0

) £ ZI *?

k f(xi} y k

)o ( 1 <i<n)

k— 1

( 5 )

Then (2)follows from ( 3 )> (*+) , ( 5 )»

In (ii) of Theorem 1 , we have an easily applicable sufficient

condition for equality (1). It can be used to provide simple

proofs for minimax theorems for infinite games (for instance,

the generalized Ville's minimax theorem as stated in our earlier

Lj. Note is a special case of part (ii) of Theorem 1). Since the

proof of (ii) is based on von Neumann's minimax theorem, its

application in proving a minimax theorem for infinite games

amounts essentially to a reduction of the latter to von Neumann's

theorem for finite games.

2. Theorem 2 below generalizes Kneser's minimax theorem*'

by eliminating the structure of linear spaces. Theorem 2 also

improves (ii) of Theorem 1. Our proof of Theorem 2 is a modification of Kneser's proof of his theorem.
5

THEOREM 2 . Let X be a compact Hausdorff space and ¥ an arbitrary set (not topoloqized) . Let f be a real-valued function on

XX Y such that, for every y£Y, f(x,y) is l.s.c. on X. If f is

convex on X and concave on Y, then

rain sup f(x,y) - sup rain f(x,y) (6)

x€X y€Y y e Y x€X

ProofObserve first that the expressions on both sides of

(6) have meaning, although their values may be + oo , We divide

the proof of (6) into four steps:

(i) Let yo€ Y be such that X

Q = {x6 X | f (x ,yQ

) < o} is not

empty o If we replace X by X

Q

, and restrict f on X

Q X Y , then the

hypothesis of Theorem 2 remains fulfilled . We need only to verify that f restricted on XQ X Y is convex

on X

Q

o Let x^ ,X 2 £ Xq) and ^ 9 > 0 , £j + £2 = 1 be given.

By convexity of f on X, there exists x

Q

€ X such that

f(x

Q ,y) < €1 f(x.,,y) + £ 2

f ^ x

2

>y) for a11 y eY» (7)

Since f (x^ ,y Q

) < 0, f(x2

>y o

) < 0, the case y = y Q

of (7) implies

f ( x

o’ yo> = °» iee ° x

o € Xo°

(ii) If [y 1 ,y 2 ]

C Y is such that

max f(x,y. ) > 0 for all xSX, (8)

k=1,2 K

—then there ——— exists— y_6.Y * such that

o

f(x,y

o

) > 0 for all x£X. (9)
6

Let Xj, = ;jx €. X I i(x,y^) < Oj , (k=1,2), which aro disjoint

closed sets in X. We assume that none of them is empty (otherwise

(ii) is trivial). We have -f(x,y|) > 0 and f(x,y2

) > 0 for

x £ X. , so that ,y 1 ^ is u.s.c. and > 0 on X. . Let x. £ X.

1 T - 1 11

and /fj 0 be such that

max

x£X1

-*(x,y.,) -f(x

1 ,y^

f (x ,y 2

) " f (x

1 ,y2

) " # ( 10 )

Similarly, let x

2 £X2 and /<2 ^

0 be such that

-f(x,y2

) -f(x2

,y2

)

*eL = /V ( 11 )

We claim that ^ /^ 2 <1. To verify this, we may assume

j*

1 j*2 ^ 0. Since f(x

1 ,y^) 1 0, f(x2

,y 1 > > 0, we can find

? 1 ^

2 ^ ^ such that + £2

= 1 and

£<1 f(x

1 ,y 1 ) + ?

2 f(x2

,y 1 ) = 0. (12)

f being convex on X, there exists x

Q € X such that

f(x0

,y) < ?1 f(x

1 ,y) + ^

2 f(x2

,y) for all y £ Y. (13)

From (12), (13),we have f(x

Q ,y^) <0 and therefore, by (8),

f(x

o »y2

) > 0, so that

0 < f(x

1 ,y2

) + ?

2 f(x2

,y 2

).

Using (10), (11) and the fact > 0, the last inequality may be

written

5 1 f(x

1 ,y 1 ) + ^ H2^2 f(x2

sy 1^ < 0 ’

which compared with (12) yields /^j /^

2 < 1*
Take 2^ , V

2

such that ^

> /^ , > /t,, 2^ >

2 = 1 * Let

~-1-^2 >9 _ ^1 _ 1 mL

T+TT

=

T +V

2

’ '2 TT^- ~ T+ir • Then

171 fUjy-j) + ^2 f(x,y2

) > 0 for all x £ X. (1*0

In fact, if x is not in X

1 U X

2

, (1^) is trivial. If x € X

1

, we have 0 < f(x,y.,) + f(x,y2

) < f(x,y.,) +

2^ f(x,y

2

> =

(1+^)C f ( x , y 1 ) + V

)

f ( x >y 2

^J» Similarly one verifies (14)

for x £ X

2

» Finally the existence of y Q € Y with property (9)

follows from (l4) and the concavity of f on Y,

(iii) If a finite set |y-j ,y 2

,

• • • >ym j C Y is such that

max f(x,y,.) > 0 for all x £, X, 0 5)

1<;k<m

K "

then there exists y Q

6. Y satisfying (9).

We prove this by induction on m. Let X = x £ xl f(x,y ) < 0

We assume that X is not empty (otherwise we take y = y ). By

(i), we can apply our induction-assumption to f restricted on

X X Y. Since max f(x,y. ) > 0 for all x X , there exists

111 1<klm-1 K 111

^m+1 ^ ^ suc ^ that f(x,y

m+ ^) > 0 for all x € Xm

» Then

max f(x,y. ) > 0 for all x 6. X. By (ii), there exists

k=ra,ni+1

y 0

e Y satisfying (9).

(iv) For any real number Ct , either there exists an

x

Q

X such that f (x

o ,y) < oc for all y Y, or there exists an

y Q

6. Y such that f (x ,y o

) > & for all x 6 X. (Therefore the

right side of (6) is not less than the left side, and consequently the two are equal.)
8

Suppose the first alternative is not true. Then y^y L(y;cx)

is empty, where L(y;0() = jx £ X | f(x,y) ^

Of] 0 As X is compact,

there exists a finite set {y^ ,y^ > * * • >yra } C Y such that ^ L(y^;Of)

is empty. That is, max f(x,y. ) > 0( for sll x £ X. Then an appli1 <^klm

cation of (iii) to the’function f-or shows that the second alternative is true.

3. The next theorem is free of topological structures. This

is made possible by generalizing von Neumann's almost periodic

functions on a group s A real-valued function f defined on the

product set X X Y of two arbitrary sets X,Y (rtot topologized) is

said to be right almost periodic , if f is bounded on X X Y and if,

i ra

’ for any £> 0, there exists a finite covering Y = Y^ of Y

such that If (x , y

' ) - f(x,y")| < € for all x £ X, whenever y' ,y"

belong to the same Y^. Left almost periodic functions are defined similarly. However, every right almost periodic function

5. Von Neumann, J„, "Almost periodic functions in a group, I",

Trans. Amer. Math. Soc ., 36, 445-492 (193*0; Maak, W.

,

"Eine neue Definition der f as t-periodischen Funktionen",

Abhandl. Math. Sem. Hans. Univ . , 11, 240-244 (1936).
on X ;< Y is also left almost periodic and vice versa. Thus we

simply use the term almost periodic , THEOREL 3c / Let f be a real-valued almost periodic function

on the product set X X Y of two arbitrary sets X, Y ( not topoloqized ) » . Then s (i) The equality

inf sup f(x,y) = sup inf f(x,y) (16)

x£X y£Y y£Y x6X

holds, if and only if the following condition is satisfied ; For

any £ > 0 , any two finite sets [x^ ,x 2

j » ® <• ,x

a

} C X and

{y 1 ,y2

, » o o ? yra} CY, there exist x

Q € X, y Q € Y such that

f(x

o ,y k

) “ f(xi

,y0

) 3 £ o (1 < i ^

n, 1 < k < ra). (17)

6o Let f be right almost periodic. Given £ > 0 , let Y - jJJ

Y^ be

a finite covering of Y with the property corresponding*^! t/s

required in the definition of right almost periodicity,. Let

s a hounded function on X,

X^k' 0 f x such that

If (x Jyk )“f (x*1 ?y k

)l < § whenever x',x" £ X^*^ f or gome i. Then

the common refinement of these m finite coverings of X has th

property corresponding to £ required in the definition of lef

almost periodicity,,

7° It should be said that the absence of topological structures

in Theorem 3 is more apparent than real. In fact, the almost

periodicity of f is a necessary and sufficient condition in

order that X,Y can be made iffto two precompact (in the sense

of Bourbaki, but not necessarily separated) uniform spaces in

such \v:v/ %i:£ f is uniformly continuous on the product uniform spaca XX Y»

y k S Y

k (1^k<m) , For each k,f(x,y

k

) there is a finite covering X =
10

(ii) In particular, if f is convex on X and concave on Y,

then (1 6) holds . Proof ; We only prove the sufficiency part of (i). Consider

an arbitrary £ > 0. Let X = ^ X^ be a finite covering of X

with the property corresponding to £ required in the definition

m

of left almost periodicity. Let Y = ^ Y^ be a finite covering

of Y with the property corresponding to £ required in the definition of right almost periodicity. Let x^ £ X^(1<i<n),

y. £ Y. (1<k<ra). Then sup f(x,y) < max fCx^y,,) + £ holds for

k ' y£Y *1<k<ra

all x £ X; and inf f(x,y) > rain f(x.,y) -£ holds for all

x £ X ~1^i<n 1

y £ Y.

8 Hence

inf sup f(x,y) < inf max f(x,y

k

) + £ , (18)

x£X y£Y xeX 1 ^k<ra

sup inf f(x,y) > sup min f (xi ,y) - £ . (19)

y£Y x6X y Y 1 <i<n TZ- S

Using our condition, there exist x

Q

£. X, yQ £ Y satisfying (IV).

From (17)> (18), (19)> we get

0 < inf sup f(x,y) - sup inf f(x,y) < 3£ > ” xex y£ Y y£Yx£X

which holds for any £> 0. Thus (16) is proved.

8. Here we see that the hypothesis in Theorem 3 on almost period

icity of f can be considerably weakened.
THE NATIONAL BUREAU OF STANDARDS

Functions and Activities

The functions of the National Bureau of Standards are set forth in the Act

of Congress, March 3, 1901, as amended by Congress in Public Law 619, 1950.

These include the development and maintenance of the national standards of

measurement and the provision of means and methods for making measurements

consistent with these standards; the determination of physical constants and

properties of materials; the development of methods and instruments for testing

materials, devices, and structures; advisory services to Government Agencies on

scientific and technical problems; invention and development of devices to serve

special needs of the Government; and the development of standard practices,

codes, and specifications. The work includes basic and applied research, development, engineering, instrumentation, testing, evaluation, calibration services

and various consultation and information services. A major portion of the

Bureau’s work is performed for other Government Agencies, particularly the

Department of Defense and the Atomic Energy Commission. The scope of activities is suggested by the listing of divisions and sections on the inside of the

front cover. Reports and Publications

The results of the Bureau’s work take the form of either actual equipment and

devices or published papers and reports. Reports are issued to the sponsoring

agency of a particular project or program. Published papers appear either in the

Bureau’s own series of publications or in the journals of professional and scientific

societies. The Bureau itself publishes three monthly periodicals, available from

the Government Printing Office: The Journal of Research, which presents complete papers reporting technical investigations; the Technical News Bulletin, which

presents summary and preliminary reports on work in progress; and Basic Radio

Propagation Predictions, which provides data for determining the best frequencies

to use for radio communications throughout the world. There are also five series

of nonperiodical publications: The Applied Mathematics Series, Circulars, Handbooks, Building Materials and Structures Reports, and Miscellaneous Publications.

Information on the Bureau’s publications can be found in NBS Circular 460,

Publications of the National Bureau of Standards ($1.00). Information on cali- bration services and fees can be found in NBS Circular 483, Testing by the National

Bureau of Standards (25 cents). Both are available from the Government Printing Office. Inquiries regarding the Bureau’s reports and publications should he

addressed to the Office of Scientific Publications, National Bureau of Standards,

Washington 25, D. C.
NBS