In the previous Theory Lunch talk we introduced the notion of Nash equilibrium for games in normal form. Today, we went through the proof of Nash’s theorem of existence of mixed strategy Nash equilibria for finite games in normal form.
Let us recall the basic notions. In a game in normal form we have:
- A set
of players.
- A set
of strategies for each player.
- A collection of utility functions
which associate to each strategic profile
a real number, such that
is the utility player
gets from the strategic profile
.
A Nash equilibrium for a game in normal form is a strategic profile such that, for every player
and every strategy
feasible for player
, it is the case that
. We had seen that not every finite game in normal form admits a pure strategy Nash equilibrium: so, we introduced randomization.
A mixed strategy for player is a probability distribution
. If
is finite, this is the same as assigning values
for
. A mixed strategy profile is a collection
of mixed strategies for each player. A mixed strategy Nash equilibrium is a mixed strategy profile
such that, for every player
and every mixed strategy
feasible for player
,
.
The idea behind Nash’s proof goes as follows. If the game is finite, then a mixed strategy for player is identified with a point of
therefore, mixed strategy profiles can be identified with points of
which is compact and convex as all of its components are. Mixed strategy Nash equilibria are those points of where each pure strategy
,
,
, is used in the most efficient way: by relaxing the condition and allowing a small “slack” with respect to such most efficient way, it is possible to define a continuous transformation of mixed strategy profiles into mixed strategy profiles, which will have a fixed point because of the Brouwer fixed-point theorem. By gradually reducing the slack, a mixed strategy Nash equilibrium is found as a limit point of such approximations.
Suppose player has available the pure strategies
for
. Let
be an arbitrary mixed strategy profile and
be an arbitrary integer. Consider the following quantities:
.
.
.
.
Given , the sum
is bounded from below by
, hence the functions
are continuous and nonnegative and satisfy whatever
and
are. As a consequence, the functions
that is,
are continuous transformations of into itself. Let
be a fixed point of
, whose existence is ensured by the Brouwer fixed-point theorem: as
is compact, the sequence
has a limit point
.
Suppose, for the sake of contradiction, that is not a mixed strategy Nash equilibrium. Then there must be a player
and a mixed strategy
such that
. The only way this may happen, is that some pure strategy
is used suboptimally by
, that is,
Choose and
so that:
belongs to a subsequence converging to
.
.
.
.
Points 2 and 3 tells us that is strictly smaller than
: this, together with point 4, yields
, thus
. But
is a fixed point for
, so
:
and as may be taken arbitrarily large and
be made arbitrarily small, we must conclude that
too. This is a contradiction.