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

• Lecture 1:  Sperner’s lemma, Brouwer’s fixed point theorem, and existence of Nash equilibria
  The proof of Sperner’s lemma and Brouwer’s fixed point theorem was from Fixed Point Theorems and Applications
  The simple proof for the existence of Nash and Walrasian equilibria was from Nash and Walras Equilibrium by John Geanakoplos
  Lecture notes (scribed by Qi Qi)

• Lecture 2: Existence of Walrasian Equibria via Brouwer’s fixed point theorem and the other way around!
  Convex programs for computing market equilibria (slides)
  Lecture notes (scribed by Leo Kung)

• Lecture 3: Gross-substitutability and market stability
  See the following two papers by Arrow et al. (1, 2)
  Lecture notes (scribed by Vahideh Manshadi)

• Lecture 4: Lemke-Howson Algorithm
  See Chapter 3 of Algorithmic Game Theory. Also the following talk by von Stengel and paper by Savani and von Stengel
  Lecture notes (scribed by Yu Wu)

• Lecture 5: The PPAD complexity class and PPAD completeness
  See Chapter 2 of Algorithmic Game Theory. Here is the full proof of the complexity result for Nash, here is a simplified exposition.
  For the PPAD completeness of Leontief exchange markets see this paper
  Lecture notes (scribed by Boyu Wang)

• Lecture 6: Correlated equilibria
  See the paper on computing correlated equilibria for multi-player games
  Lecture notes (scribed by Alex Shkolnik)

• Lecture 7: fair division
  paper on fair allocation of indivisible goods (and slides)
  Asadpour-Saberi’s paper on max-min fair allocation

• Lecture 8: Nash bargaining solution
  Vazirani’s paper (and the slides of his talk)
  paper on balanced outcomes on social exchange network (by Kleinberg-Tardos)

Relevant references

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

Population Games and Evolutionary Dynamics by Sandholm