3. Existence of Nash Equilibria

Nash’s existence theorem

• Any n-player normal-form game with finite strategy sets S_i for all players has a (Nash) equilibrium in mixed strategies

• This existence theorem builds upon what is called a fixed-point theorem in Mathematics, the most simple of which is Brouwers

Brouwer’s Fixed Point Theorem

• If f (x) is a continuous function from the domain [0, 1] to itself then there exists at least one value x* ∈ [0, 1] for which f (x*) = x*

• Basically, in a continuous function, there has to be some value where the input value is equal to the output value

• Nash shows that the collection of Best Response Correspondences satisfies something like continuity, meaning there must be a Nash equilibrium at some point in the set of strategies

The collection of best response correspondences

• The collection of best-response correspondences, BR ≡ BR₁ × BR₂ × ... × BR_n, maps △S = △S₁ × ... × △S_n, the set of profiles of mixed strategies, onto itself

• That is, BR : △S →→ △S takes every element σ ∈ △S and converts it into a subset BR(σ′ ) ⊂ △S

How to derive NE’s from Best Responce Correspondences

• A mixed-strategy profile σ* ∈ △S is a Nash equilibrium iff is a fixed point of the collection of best-response correspondences, σ* ∈ BR(σ*)

• More simply, a strategy is a Nash equilibrium when the Best Response graphs of different players intersect

Kakutani’s fixed point theorem

• Required for finding NE because Brouwer’s theorem isn’t strong enough — it concerns functions but our Best Response Correspondences might not be functions

• Let C : X ⇒ X, with X being a non-empty, compact, convex subset of Rⁿ, C(x) is non empty and convex for all x, and it has a closed graph

• Then, C has a fixed point

• This theorem guarantees that the correspondence will cross the 45⁰ line

What is a convex set?

• A set is convex if the point in question lies on the straight line segment inbetween two points A and B

What is a closed set?

• A set is closed if it contains its boundary points

• In an infinite sequence, if all numbers in the sequence converge to another number and that number is included in the set, then the set is closed

• A closed graph is one whose graph is a closed set

What is a compact set?

• A set is compact if it is both closed and bounded

• Closed means it includes all its boundary points, and a bounded set is one whose elements don’t extend infinitely in any direction

Debreu-Glicksberg-Fan Existence Theorem

• This extends our definition to the case of infinite games

• Let G be an infinite game

• If each strategy set S_i is compact and convex and payoff functions u_i(s_i ,s_−i) are continuous in all inputs and concave in s_i, then there exists a pure strategy Nash equilibrium

• This added concavity assumption also means that the Nash Equilibrium identified will be a pure strategy Nash Equilibrium

  • This assumption is needed because it ensures a maximum (for maximising payoffs), doesn’t allow for local maxima traps and is continuous and all the other assumptions needed