5.1 Introduction 5.2 Proof of Existence of Stochastic Nash Equilib- Rium in Any Game 5.2.1 Proof Outline
In this lecture we explore issues concerning the computability of Nash Equilibrium in any general game. First we prove any game has at least one Nash Equilibrium using Brouwer’s Fixed Point Theorem (The proof is presented at section 5.6 ). Then we discuss how to compute a Nash Equilibrium of a game and a Nash Equilibrium approximation called -Nash. We conclude by proving that the computation of most information concerning Nash Equilibrium is NP -hard.