The Fundamental Theorem of Games

Yana Peysakhovich
September 23, 2007
1
1 Introduction
Two men are walking down the street. As they part company, police ocers
surround each man, arresting them separately, and they are brought in two
separate cars to two separate police stations. Each man is seated in an
interrogation room and immediately told the following by a detective:
Look, we know it was you two who robbed the bank yesterday, but we
want the charges to stick. We need you to cooperate with us. If you both
confess, youll get 5 years in prison. If you confess and your partner denies,
youll get 1 year, hell get 10. If you both deny the crime, youll both do 2
years. Ill be back in ve minutes, and you better have a decision. Oh, and
just so you know, your partner is getting the same oer.
The prisoners begin to get nervous.
What would you do? Maybe it depends on how much the prisoners trust
one another, and maybe it depends on how much they hate jail. Well, if you
are worried enough about jail, and dont care about what happens to your
partner, you might make the perfect player. If you seek to maximize your
gain and minimize your loss, if you are rational and intelligent, and if your
rationality leads you to the conclusion that your opponent is rational also,
you might draw yourself this picture:
Then think: If the other prisoner confesses, I would be better o con-
fessing (5 > 10), and if he denies the crime, I would still be better o
confessing (1 > 2). So you confess. But the game is symmetric, so the
other guy decides, similarly, to confess. You both confess and are sent to
prison for 5 years. Too bad, certainly you would both have preferred the
(Deny, Deny) outcome. So why could this outcome never be the result of
this game, nitely played? Because if you know (or believe) that the other
player will Deny, you will be very tempted to deviate from the (Deny, Deny)
strategy. So would the other player. This makes you nervous. You decide
2
to play it safe and confess. So does he. The strategy (Deny, Deny) is not
stable, while the strategy (confess, confess) is stable. Neither player would
prefer to change his response, given the strategy of the other player. In other
words, at the point (Confess, Confess), player 1 says, given player 2 is playing
Confess, I would be only worse o playing Deny, so I will stay where I
am.
You have just played through a rather famous scenario in the eld of game
theoryThe Prisoners Dilemma, originally formulated by Merrill Flood and
Melvin Dresher in 1950 [1]. Since then, Game Theory has come very far.
This paper, however, will return to the basics, ultimately chronicling the
evolution of the proof of the Fundamental Theorem of Games: every game
has a solution.
2 The Beginning
One class of games is zero-sum. These are simply 2-player games in which
the sum of all payos between the players is 0, in particular, a gain of $2 for
one player is the loss of exactly $2 for his opponent. The study of this class
is quite fruitful, but limited in application to parlor games and extremely
simplied international relations. However, it is precisely these games that
gained the attention of the leading mathematicians and economists formu-
lating the Theory of Games. Noting their denition, zero sum games can be
intuitively represented in the form of an m n matrix, where the payo to
payer one only is listed for every possible combination of strategies. Then,
clearly, 0 a
ij
represents the payo to player 2. Lets consider the game of
Matching Pennies. Simultaneously, player 1 (P
1
) and payer 2 (P
2
) choose
either heads or tails. Each is in total ignorance of the others decision.
After the choices are made, they compare decisions, and P
2
pays P
1
$1.00 if
they matchif both chose heads or both chose tails. If they do not match, P
1
must pay P
2
$1.00. But of course, this situation can easily be represented by
the following simple 2 2 matrix:

1 1
1 1

This is P
1
s payo matrix, where the rst row and column both represent
the choice of heads, while the second row and column represent the choice of
tails. Entry a
11
represents the outcome (Heads, Heads), entry a
12
represents
P
1
playing Heads and P
2
playing Tails. So, where P
1
has m possible moves
and P
2
has n possible moves, we have the following matrix, in general:
3

a
11
a
12
. . . a
1n
a
21
a
22
. . . a
2n
.
.
.
.
.
.
.
.
.
.
.
.
a
m1
a
m2
. . . a
mn

A few denitions will be useful:

Denition 2.1 A matrix game is given by any m n matrix A = (a
ij
)
in which the entries a
ij
are real numbers.
Denition 2.2 A mixed strategy for P
1
is an ordered m-tuple x = (x
1
, x
2
, ..., x
m
)
for non-negative real numbers x
i
such that x
1
+ ... + x
m
= 1 Similarly,
a mixed strategy for P
2
is an ordered n-tuple y = (y
1
, y
2
, ..., y
n
) for non-
negative real numbers y
j
such that y
1
+ ... + y
n
= 1
It is useful to note that in any game, players can only choose one strategy
(ie, P
1
can only choose one of the m rows of the matrix (a
ij
) and P
2
can
only choose one of the n columns of the same matrix). A mixed strategy,
however, is like creating a weighted die which, for P
1
, has m sides and the
weights on each side are dictated by the real numbers x
i
. P
1
chooses a row
by rolling his weighted die. Similarly, P
2
s die has n sides, with the weight
y
j
corresponding to side j, and a roll of his die determines which column he
chooses.
Denition 2.3 A pure strategy for P
1
is the mixed strategy which is 1 in
the i
th
component and 0 everywhere else for i = 1, ..., m, and will be referred
to as the i
th
pure strategy for P
1
.
A similar denition holds for the j
th
pure strategy of P
2
.
Denition 2.4 The payo function for is dened to be
E(x, y) =

i,j
x
i
a
ij
y
j
where x = (x
1
, x
2
, ..., x
m
) and y = (y
1
, y
2
, ..., y
n
) are mixed strategies.
Denition 2.5 A solution of is a pair of mixed strategies x = (x
1
, x
2
, ..., x
m
), y =
(y
1
, y
2
, ..., y
n
), and a real number v such that E(x, j) v for the pure strate-
gies j = 1, ..., n and E(i, y) v for the pure strategies i = 1, ..., m. Then x
and y are called optimal strategies and the number v is called the value of
the game .
In fact, the amount v (the value of the game) is the expectation that
P
1
can assure himself no matter what P
2
does, while P
2
can protect himself
against expectations higher than v no matter what P
1
does.
At last, we can begin our investigation of a remarkable fact which was
proven by John von Neumann (arguably, the father of Game Theory) in the
late 1920s: Every matrix game has a solution[2].
4
3 The Fundamentals of Matrix Games
Before we prove this fact, however, we will briey investigate the case for a
2 2 zero-sum game (matrix game)
3.1 The 2x2 Case
Theorem 1 Given the 2 2 matrix
A =

a
11
a
12
a
21
a
22

there exist vectors x = (x

1
, x
2
), where x
1
, x
2
0 and x
1
+ x
2
= 1, and
y = (y
1
, y
2
), where y
1
, y
2
0 and y
1
+ y
2
= 1, and a real number v such
that:
(1)
x
1
a
11
+ x
2
a
21
v
x
1
a
12
+ x
2
a
22
v
(2)
a
11
y
1
+ a
12
y
2
v
a
21
y
1
+ a
22
y
2
v
Proof 1 If P
2
plays the mixed strategy y = (y
1
, y
2
), he can expect to pay
E(1, y) = a
11
y
1
+a
12
y
2
against 1 by P
1
and E(2, y) = a
21
y
1
+a
22
y
2
against 2
by P
1
. Plotting (E(1, y), E(2, y)) in the case where y
1
= 1 and y
2
= 0, then
in the case where y
1
= 0, y
2
= 1, we obtain the points (a
11
, a
21
) and (a
12
, a
22
)
both in R
2
. The line connecting these points creates P
2
s expectation space,
since this gives all expectations under mixed strategies (where y
1
, y
2
0,
y
1
+ y
2
= 1). We can notice that P
2
is assured of paying no more than the
expectation e his expectation point lies in the set S
e
of all points with
both coordinates less than or equal to e. Since P
2
is playing optimally when
we choose a strategy y with the smallest possible e, we translate S
e
until it
is just in contact with P
2
s expectation space. We will call this translated
set S
v
. It is clear that condition (2) of the theorem is satised.
Suppose we have found a mixed strategy x = (x
1
, x
2
) satisfying (1) for
this v. Then, the line x
1
t
1
+x
2
t
2
= v, separates P
2
s expectation space from
the the set S
v
, because we have x
1
t
1
+ x
2
t
2
v for all points (t
1
, t
2
) in P
2
s
expectation space by (1) and we have x
1
t
1
+ x
2
t
2
x
1
v + x
2
v = v points
(t
1
, t
2
) S
v
(by denition).
5
Now we have found that any optimal x, if it exists, denes a separating
line. Let us assume that at
1
+bt
2
= c separates P
2
s expectation space from
S
v
, that is,
(3) aa
11
+ ba
12
c
(4) aa
12
+ ba
22
c
(5) at
1
+ bt
2
c (t
1
, t
2
) S
v
.
Since (v 1, v) and (v, v 1) are in S
v
, we have
(6) a(v 1) + bv c
(7) av + b(v 1) c
and, because (v, v) lies on any separating line,
(8) av + bv = c
By subtracting (8) from (6) we see that a 0, and by subtracting (8)
from (7) we see that b 0. But a and b cannot both be 0, since they dene
a separating line, so we dene x
1
=
a
a+b
, x
2
=
b
a+b
, so x
1
, x
2
0, x
1
+x
2
= 1.
Then, (3) and (4) give
x
1
a
11
+ x
2
a
21

c
a+b
and
x
1
a
12
+ x
2
a
22

c
a+b
,
which, combined with (8) give the desired inequalities (1).
3.2 Convex Sets
The remainder of this section will assume basic knowledge of linear algebra.
We will be working in the Euclidean vector space R
m
. The norm in our
space will be characterized by |t| =

t t, Where the dot product t u =

m
i=1
t
i
u
i
.
Denition 3.1 A hyperplane H(x, a) in R
m
is the set of all vectors t such
that x t = a for a given vector x ,= 0 and a real number a.
Naturally, we can refer to
H
+
(x, a) = t[x t a
H

(x, a) = t[x t a, as the upper and lower hyperplane, respectively.

Denition 3.2 A subset C of R
n
is called convex if whenever t
1
, ..., t
m

C and b
1
, ..., b
m
are non-negative real numbers summing to 1, t = b
1
t
1
+... +
b
m
t
m
C. The vector t is called a convex combination of t
1
, ..., t
m
.
We can notice that, geometrically, a convex set contains all line segments
joining two points in the set.
Denition 3.3 The convex hull C(S) of a given set S is the set of all con-
vex combinations of sets of points from S, or, it is the minimal convex set
containing S.
6
Theorem 2 Given a closed convex set C R
n
and a vector u , C, there
exists a hyperplane H such that:
1) C H
+
2) u H

but u , H.
Proof 2 Because we have a distance function, |t u|, which is continuous
on a closed and bounded set of t C for which |t u| |t
0
u| for some
xed t
0
in C, the distance attains its minimum in C, so we can choose the
point v C which is closest to u. To simplify our notation, we will assume
v = 0.
We now consider the hyperplane H(u, 0). It is clear that condition (2)
of the theorem is met, since u u < 0 (we know u ,= 0).
Suppose that (1) does not hold. Then there is a vector t C for which
ut < 0, so for which ut > 0. Certainly, either ut tt, or 0 < ut < tt.
We will call this Case 1 and Case 2, respectively.
Case 1:
u t t t |t u|
2
= t t 2u t +u u = u u (u t t t) u t <
u u = |u|
2
|t u| < |u| = |0 u|,
But this contradicts the fact that 0 is the point of C closest to u.
Case 2:
0 <
ut
tt
< 1 (
ut
tt
)t C, and
|(
ut
tt
)t u|
2
= u u (
ut
tt
)(u t) < |u|
2
|(
ut
tt
)t u| < |u|
So (
ut
tt
)t C, and again is closer to u than 0, a contradiction.
Both possible cases have led to a contradiction, thus our assumption is
incorrect and (1) holds.
Denition 3.4 If H is a hyperplane and C is a convex set such that C is
contained in H
+
, then H is called a supporting hyperplane for C and H
+
is
called a support for C.
Theorem 3 Any closed convex set is the intersection of its supports.
Proof 3 Let

H
+
denote the intersection of all the supports for C. Clearly,
C

H
+
. However, for any u , C, there is a support H
+
for C which does
not contain u, by Theorem 2. Thus, C

H
+
and so we see that C =

H
+
.
Corollary 1 Given a closed convex set C such that C ,= R
n
, there exists a
support for C which contains a vector in C.
7
This corollary follows immediately from Theorem 2.
Denition 3.5 The point u is an interior point of a set S R
n
if there
exists > 0 such that if |v u| < then v S
Theorem 4 Given a set S R
n
consisting of the vector 0 and n LI vectors
t
1
, ..., t
n
, C(S) contains an interior point.
Proof 4 We can note that in fact C(S) is the intersection of its extreme
supportsthose which contain n points from the set S. We simply modify
Theorem 3 to see that the result holds.
Theorem 5 Every convex set C R
n
either contains an interior point or
is contained in a hyperplane.
Proof 5 We can assume that 0 C, for simplicity. Then, we can chose a
system of LI vectors t
1
, ..., t
m
from C such that every set of m + 1 vectors
from C is LD. Then, either:
Case 1:
If m = n, then we are done by the previous theorem.
Case 2:
If m < n, then the subspace R
m
generated by t
1
, ..., t
m
is R
n
and we
can choose a non-zero vector x such that x t
k
= 0 k = 1, ..., m. But, for
any t C, we have t =
1
t
1
+ ... +
m
t
m
, since any set of m + 1 vectors
from C is LD, while t
1
, ..., t
m
is not. Then x t = 0 C H(x, 0).
Theorem 6 Given any convex set C with C ,= R
n
, there exists a support
for C.
Proof 6 Consider D, the smallest closed set containing C, that is, D :=
C. Omitting details, it is easy to show that if there exists a sequence
u
1
, u
2
, u
3
, ... u and a sequence v
1
, v
2
, v
3
, ... v, so that u and v
are limit points, as u
k
u and v
k
v, au
k
+ bv
k
au + bv, for a, b
R. So D is convex. By Theorem 2, we only need to see that D is not all
of R
n
. By Theorem 5, however, we can note that if C H, a hyperplane,
then D must also be in H. If C has an interior point u and there exists v ,
C, then for some > 0, all points x B(2v u, ) , C, thus, 2v u , D.
At this time we can note an intuitive denition, given what we have seen
so far:
Denition 3.6 The Hyperplane H(x, a) is said to separate the set C from
the set D if C H
+
and D H

.
8
Theorem 7 Let two convex sets C and D be such that:
(1) 0 C,D;
(2) D has an interior point w;
(3) no point of C is interior to D.
Then there exists H(x, 0) which separates C from D.
Proof 7 Let E = at bu [ a, b 0, t C, u D. E is, by denition, a
convex set. We can also notice that any supporting H(x, 0) for E separates
C from D. Finally, we must see that w , E.
Suppose w = at bu, a, b 0, t C, u D. Then
1
1+b
w +
b
1+b
u =
a
1+b
t.
If
a
1+b
1, then the R.H.S. of the equation above is a convex combination of
0 and t, hence is in C, while the L.H.S. is a convex combination of u D
and w, which is interior to D, hence the L.H.S. itself is interior to D. But
this is a contradiction to the fact that no point of C is interior to D.
If
a
1+b
1, then, since t C, and in this case, is also a convex combination
of 0 and
a
1+b
t, which is interior to D by the previous argument. So we have
that t is also interior to D. Obviously, this is a contradiction. So, w , E.
Then, since E is a convex set, w , E, and by Theorem 6, a supporting
hyperplane H(x, a) for E. But then it must be true that H(x, 0) also supports
E:
Suppose not, then x v < 0 and x v a for some v in E. Then for some
c > 0, c(x v) + x v < a. Then x (cv + v) < a and cv + v = (c + 1)v
E, which is a contradiction.
Thus, H(x, 0) separates C from D
3.3 The Fundamental Theorem for Matrix Games
Theorem 8 Every matrix game has a solution. In other words:
Given any mn matrix A = (a
ij
), there exist vectors
x = (x
1
, ..., x
m
), x
i
0 i, x
1
+ + x
m
= 1,
y = (y
1
, ..., y
n
), y
j
0 j, y
1
+ + y
n
= 1
and a real number v s.t.
(1)
x
1
a
1j
+ + x
m
a
mj
v for j = 1, ..., n
(2)
a
i1
y
1
+ + a
in
y
n
v for i = 1...., m
9
Proof 8 Again, we will consider P
2
s expectation space in R
m
and consider
the set C of all vectors t = y
1
t
1
+ +y
n
t
n
where t
j
= (a
1j
, ..., a
mj
), all y
i
0,
y
1
+ + y
n
= 1.
This set C is the convex hull of the points t
1
, ..., t
n
. If z = (z
1
, ..., z
m
) is
a point in C, we can consider the function (z) = max
i=1,...,m
z
i
. (z) is a
continuous function dened on the compact set C R
m
and hence attains
its minimum at some point t = y
1
t
1
+ + y
n
t
n
C. Let v = (t). It is
clear that (2) is satised for this choice of y and v.
Now we dene D to be the set of all t = (t
1
, ..., t
m
) such that t
i

v for i = 1, ..., m. The set D intersects C at t and has interior points
(clearly). However, no point of C is interior to D by our choice of v. But
these are exactly the conditions we need to employ Theorem 7, so we know
a hyperplane H(x, a) which separates C from D.
In fact, the point v = (v, ..., v) lies in H. To see that this is true, suppose
not, then
x v < a = x (2t v) = 2x t x v < 2a a = a
This contradicts the fact that 2t v D. It is true from the denition of
D that x v ,> a. Now we have that x v = a and v H.
We let v
i
be the vector which is v in every component except at the
i
th
coordinate, where it is v 1, for i = 1, ..., m. Then v
i
D and so
x v
i
= (x v) x
i
a. Therefore, x
i
0 for i = 1, ..., m. Since x ,= 0, we
can dene x = (x
1
, ..., x
m
) where
x
i
=
x
i
x
1
++x
m
for i = 1, ..., m.
Then all x
i
0, x
1
+ + x
m
= 1. Since C H
+
,
x t
j
=
1
x
1
++x
m
x t
j

a
x
1
++x
m
= v
for j = 1, ..., n, which is condition (1) of the Theorem.
4 A Fixed Point Theorem
Before we are able to prove John Nashs remarkable generalization of the
previous result, we must familiarize ourselves with a new topic. We will rst
prove two lemmas, and from these the Brouwer Fixed Point Theorem will
follow.
Denition 4.1 Let x
1
, x
2
, ..., x
n+1
be n + 1 points in R
k
where k n and
any n of the points are linearly independent. Then the n-simplex dened by
10
x
1
, x
2
, ..., x
n+1
is the set S of convex combinations of x
1
, x
2
, ..., x
n+1
:
S = x [ x =
n+1

i=1

i
x
i
,
i
0,
n+1

i=1

i
= 1
Denition 4.2 For x S, we dene
i
(as above) to be the i
th
barycentric
coordinate of x.
Denition 4.3 The points x
1
, x
2
, ..., x
n+1
are the vertices of S. We will
label the vertex x
i
with the number i.
Denition 4.4 For a given x S, the set x
i
[
i
> 0 will be called the
carrier of x.
Denition 4.5 A face, F, of the simplex S is dened as
F = x [ x =

n+1
i=1

i
x
i
,
k
= 0 for one k,
i
0,

n+1
i=1

i
= 1.
Denition 4.6 A triangulation, or, simplicial subdivision of S is a nite
family of S
j
so that
(i) The elements of S
j
have disjoint interiors
(ii) If a vertex x
i
of S
j
is an element of S
k
, then x
i
is also a vertex of S
k
.
(iii)

S
k
= S.
Denition 4.7 Let S
j
be a simplicial subdivision of S. We label each
vertex of each subsimplex with one of the numbers 1, 2, ..., n + 1. A labeling
is said to be admissible if each vertex is labeled with the index of one of the
elements of its carrier.
Theorem 9 (Sperners Lemma) Let S
j
be a simplicial subdivision of
the n-simplex S. If S
j
is labeled admissibly, then there exists S
0
S
j

such that S
0
is completely labeled, i.e. with labels of each number 1, 2, ..., n+1.
Proof 9 We will, in fact, prove that the number of completely labeled sub-
simplices is odd. We proceed by induction.
Consider n=1: Each vertex of our simplicial subdivision is labeled 1 or 2
(our simplex is a line segment). Let a be the number of subsegments whose
end points are both labeled 1 and let b be the number of subsegments whose
end points are completely labeled, so one end point is labeled 1 and the other
is labeled 2. We will now count the number of endpoints labeled 1, where
each endpoint is counted once for each subsegment of which it is an element.
Obviously, this number is 2a + b. Now, we will count again. We have one
exterior endpoint labeled 1, the endpoint of the original line segment, and,
11
if we let c be the number of interior endpoints labeled 1, we see that the total
number of endpoints labeled 1 is 1 + 2c. So, 1 + 2c = 2a +b. Since 1 + 2c is
odd, b must be odd.
For the remainder of the proof, it may be useful to refer to the gure
below, an admissibly labeled simplicial subdivision of a simplex.
Now, suppose for an (n 1)-simplex, any admissibly labeled simplicial
subdivision contains an odd number of completely labeled subsimplices.
Consider an admissibly labeled subdivision of an n-simplex. An argument
similar to the case for n = 1 holds here. We let a be the number of sub-
simplices labeled with 1, ..., n but not n + 1. For each of these subsimplices,
there are two faces with the labels 1, ..., n. Let b be the number of com-
pletely labeled subsimplices. Each of these completely labeled subsimplices
has exactly one face with the labels 1, ..., n. So the total number of faces
with the labels 1, ..., n = 2a + b. Now we count again. Let c be the number
of interior faces carrying the labels 1, ..., n. Again, each interior face must
be a face of precisely 2 adjacent subsimplices. Exterior faces can be dened
as those not shared by two adjacent subsimplices, so clearly, each exterior
face labeled 1, ..., n will be counted once. The number of such faces, however,
must be odd, by the inductive hypothesis, since a face of an n-simplex is an
12
(n 1)-simplex. Thus, if we let d be the number of exterior faces carrying
the labels 1, ..., n, we see that 2a + b = 2c + d. Because d is odd, b is odd.
Thus, by induction, the number of completely labeled subsimplices is odd.
Since 0 is not odd, the theorem is proven
Theorem 10 (Knaster-Kuratowski-Mazurkewicz (KKM) Theorem)
Let S be an n-simplex. Consider the sets C
1
, C
2
, ..., C
n+1
S where C
j
is
closed, and where vertex j = x
j
C
j
. For all x in S, let x C
i
for some i
s.t. x
i
is a carrier of x. Then

n+1
j=1
C
j
,=
Proof 10 We can choose a sequence of simplicial subdivisions
v
= S
k
v
[
k = 1, 2, ... for v = 1, 2, .... Then k indexes the subsimplices within each
subdivision
v
. We construct the sequence
1
,
2
,
3
, ... such that for v < u,
the minimal -Ball which contains S
k
u
has smaller radius that the minimal
-Ball which contains S
j
v
for all reasonable values of j, k. In other words, the
mesh of our sequence
v
will become progressively ner and arbitrarily ne
as v increases. We can now label the vertices of S
k
v
by the number j, where
the vertex is an element of C
j
for some j s.t. x
j
is an element of the carrier
of the vertex.
By Sperners Lemma, we know that there exists some S
0
v

v
, so that S
0
v
is completely labeled. Let x
i
v
be the vertex of S
0
v
with the label i. Then x
i
v
C
i
for all v. But S is compact, so there exists a convergent subsequence of
x
i
v

v=
v=1
for each i. But because the diameter of our subsimplex goes to zero,
these subsequences must converge to a common point, x
0
, for all i. Since C
i
is closed, x
i
v
x
0
= x
0
C
i
for all i. Thus x
0

n+1
j=1
C
j
,=
[3]
Theorem 11 (Brouwer Fixed-Point Theorem) Let S be an n-simplex
and let f : S S, f continuous. Then there exists x

S s.t. f(x

) = x

Proof 11 Let
j
(x) be the j
th
barycentric coordinate of x. Dene
C
j
= x [
j
(f(x))
j
(x)
In fact, C
j
satises the assumptions of the KKM theorem above by the
continuity of f (this is easy to check).
Then, applying the KKM theorem to these C
j
s, there exists x

S s.t.
x

n+1
j=1
C
j
. We have, then, by our denition, that

j
(f(x

))
j
(x

) for all j.
However, since

j
(x

) =

j
(f(x

)) = 1, it must be that
j
(x

) =

j
(f(x

)) for all j, or, in other words, x

= f(x

).
[3]
13
5 The Triviality
It is reported that when young John Nash came to von Neumann with his
proof of the Fundamental Theorem for Non-Zero Sum games, the envious
von Neumann dismissed his result with the phrase, but its a triviality [5].
So it may seem to us today. Nonetheless, Nash accomplished what no one
else had, and his contribution to the eld of Game Theory certainly rivals
that of von Neumann.
We will adopt John Nashs notation for elements of games [6]:
Denition 5.1 An n-person game is a set of n players, or, positions each
with an associated nite set of pure strategies, and for each player i, there
is a payo function p
i
: n-tuples of pure strategies R
Denition 5.2 A mixed strategy for player i will be a collection of non-
negative numbers c
i

so that
s
i
=

c
i

, c
i
0,

c
i

= 1
where s
i
is the mixed strategy of player i and
i

is the
th
pure strategy of
player i
We can think of the s
i
s as points in a simplex with vertices
i

. This simplex
is a convex subset of a real vector space.
The symbols i, j, k will refer to players i, j, k
The symbols , , will indicate various pure strategies of a player
The symbols s
i
, t
i
, r
i
will indicate mixed strategies
We now extend the denition of p
i
above to the function p
i
: n-tuples of
mixed strategies R, so that p
i
(s
1
, s
2
, ..., s
n
) will represent the payo to
player i under the mixed strategies s
1
for player 1, s
2
for player 2, ..., s
n
for
player n.
And of course, as in the zero-sum version, a pure strategy for player i =

is simply a mixed strategy s

i
= 0
i
1
+0
i
2
+ +1
i

+0
i
+1
+ +0
i
n
.
We will want to be sure that any mixed strategy is stable, in order to nd
an equilibrium, so it will be helpful to introduce the following notation:
Where o = (s
1
, s
2
, ..., s
n
), substitutions will be represented by (o; t
i
) =
(s
1
, s
2
, ..., s
i1
, t
i
, s
i+1
, ..., s
n
). Successive substitutions, ((o; t
i
); r
j
) will be
indicated by (o; t
i
; r
j
), etc.
Denition 5.3 An n-tuple o is an equilibrium point if and only if:
i, p
i
(o) = max
allr

i
s
p
i
(o; r
i
)
So that in equilibrium, each players strategy is optimal against all others.
14
Denition 5.4 A mixed strategy s
i
uses a pure strategy
i

if s
i
=

c
i

and c
i
> 0. If o = (s
1
, ..., s
n
) and s
i
uses
i

, we say that o also uses

i

Denition 5.5 From the linearity of p

i
(s
1
, ..., s
n
) in s
i
,
max
allr

i
s
p
i
(o; r
i
) = max

p
i
(o;
i

)
We dene p
i

(o) = p
i
(o;
i

). Then we obtain the following necessary and

sucient condition for o to be an equilibrium point:
p
i
(o) = max

p
i

(o)
We can note that the above denition requires that c
i

= 0 whenever p
i

(o) <
max

p
i

(o), which means that o does not use

i

unless it is an optimal pure

strategy for player i. Thus,
Denition 5.6 If
i

is used in o then
p
i

(o) = max

p
i

(o)
is another sucient and necessary condition for an equilibrium point.
Again, Denitions 5.3, 5.5, and 5.6 all describe an equilibrium point.
Theorem 12 (The Fundamental Theorem) Every nite game has an
equilibrium point.
Proof 12 We consider our denitions as above, so that p
i

(o) is the payo

to player i if he changes to his
th
pure strategy
i

and the others continue

to use the mixed strategies from o. We dene a set of continuous functions
of o by

(o) = max(0, p
i

(o) p
i
(o))
we consider the mapping T : o o

which modies each component of o,

s
i
, so that
s
i
s

i
=
s
i
+

(o)
i

1 +

(o)
So we call o

the n-tuple (s

1
, s

2
, ..., s

n
).
We must now show that the xed points of the mapping T : o o

are
the equilibrium points.
We consider any n-tuple o. In o the i
th
players mixed strategy s
i
will
use certain pure strategies. Some of these strategies must be least protable,
say
i

is such, then p
i

(o) p
i
(o). This will make
i

(o) = 0.
15
If, however, the n-tuple o is xed under T, the proportion of
i

used
in s
i
must not be decreased under T. Thus, s,
i

(o) must be zero to

prevent the denominator in our modication from exceeding 1.
We see that if o is xed under T, for any i and for any ,
i

(o) = 0.
Then, no player can improve his payo by moving to a pure strategy
i

. By
denition 5.5, this is exactly the criterion for an equilibrium point.
It is clear that if, conversely, o is an equilibrium point, then all the s
become 0, making o a xed point under T.
Finally, we can note that the n-tuple o lies in the space which is a product
of the simplices with vertices
i

(each player has his own simplex). This

space has dimension d
1
+ d
2
+ ... + d
n
where d
i
represents the dimension of
player is simplex. But this space is homeomorphic to a ball of dimension
d
1
+d
2
+... +d
n
, where it is clear that Brouwers xed point theorem applies.
Hence, T has at least one xed point o, which we have shown to be an
equilibrium point.
References
[1] Prisoners Dilemma. Available at http://en.wikipedia.org/wiki/Prisoner
[2] Kuhn, Harold W. Lectures on the Theory of Games. Annals of Mathe-
matics Studies. Princeton: Princeton University Press, 2003.
[3] Starr, Ross M. General Equilibrium Theory. Cambridge: Cambridge Uni-
versity Press, 1997.
[4] Taylor, Larry. Sperners Lemma, Brouwers Fixed Point Theorem.
Available at http://www.cs.csubak.edu/ larry/sperner.pdf.
[5] The Mathematics of Strategy. Available at
http://www.pnas.org/misc/classics5.shtml
[6] Nash, John. Non-Cooperative Games. Annals of Mathematics. Vol. 54,
No. 2 (September, 1951) pp. 286-295 .
[7] Tardos, Eva. Randomized Nash Equilibrium. Available at
http://www.cs.cornell.edu/courses/cs684/2005fa/10-26.pdf
16