Lecture 3 - Nash Equilibrium Calculation

03.04

Instructor: Yaodong Yang

Topics Covered

1. Mixed Strategy
   • 1.1 Matching Pennies
   • 1.2 Definition
   • 1.3 Payoffs and Expected Payoffs
   • 1.4 Payoff Calculation
2. Mixed Strategy Nash Equilibrium
   • 2.1 Example: Coin-Guessing Game
   • 2.2 Definition
   • 2.3 Best Mixed Strategy
   • 2.4 Equivalent Method
3. Solving Mixed Strategy Nash Equilibria
   • 3.1 Support Solution
     • 3.1.1 Basic Idea
     • 3.1.2 Shortcomings
     • 3.1.3 Complexity
   • 3.2 Computational Solution
     • 3.2.1 Two-Player Finite Static Games: Linear Complementarity Problem (LCP)
     • 3.2.2 Multi-Player Finite Static Games: Non-Linear Complementarity Problem (NLCP)
   • 3.3 Lemke–Howson Algorithm
     • 3.3.1 Application to LCP
     • 3.3.2 Finds Only One Nash Equilibrium
     • 3.3.3 Proof
     • 3.3.4 Lemke–Howson vs. Linear Programming (LP)
4. Zero-Sum Games
   • 4.1 Definition
   • 4.2 Computational Solution