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
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.