A Tutorial on the Proof of the Existence of Nash Equilibria

In this tutorial we detail a proof of Nash’s famous theorem on the existence of Nash equilibria in finite games, first proving Sperner’s lemma and Brouwer’s fixed-point theorem. We begin with the definition of a finite game. Definition 1 (Normal-form game) A (finite, n-person) normal-form game is a tuple (N, A, O, µ, u), where • N is a finite set of n players, indexed by i; • A = (A1,...,An), where Ai is a finite set of actions (or pure strategies; we action, or pure strategy will use the terms interchangeably) available to player i. Each vector a = (a1,...,an) ∈ A is called an action profile (or pure strategy profile); • O is a set of outcomes; • µ: A → O determines the outcome as a function of the action profile; and • u = (u1,...,un) where ui: O →R is a real-valued utility (or payoff) function for player i. action profil