MS&E 334: Computation of equilibria
Amin Saberi

Time and location: Tuesday 4:15PM - 6:05PM, Hewlett Teaching Center 102

 

 

The course focuses on recent advances in resolving the computational complexity of solution concepts in game theory. The primary two examples of such concepts are Nash and market equilibria. It will consist of ten 2-hour lectures.

Topics

 

  1. Basic concepts: Sperner’s lemma, Brouwer’s fixed-point theorem, existence of Nash and price equilibria
  2. Nash equilibria: nonzero sum 2-person games, LCP formulation, Lemke Howson algorithm
  3. Price equilibria: Eisenberg-Gale convex program, convex programs for certain exchange markets
  4. Market dynamics: weak gross substitutability, tatonnement process, combinatorial algorithms, primal-dual framework
  5. Game dynamics: best-response dynamics and potential games, evolutionary dynamics, stable games and ``invasive’’ strategies
  6. Anonymous games: definition and motivation, a polynomial time approximation scheme
  7. Correlated equilibria: justification of concept via learning algorithms, computability
  8. PPAD class: PPAD-completeness of finding Nash equilibria and implications
  9. Nash bargaining solution: convex programs
  10. Solution concepts in cooperative game theory: fixed point theorems and fair division, core of a game, Scarf’s lemma

 

 

Lectures

 

 

 

 

 

 

 

 

 

Relevant references

            Algorithmic Game Theory, Chapters 1-7
            A survey by Roughgarden (written for economists)

            Population Games and Evolutionary Dynamics by Sandholm