Amin Saberi

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.

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

**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 divisionpaper 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)

Algorithmic
Game Theory, Chapters 1-7

A survey by
Roughgarden (written for economists)

Population Games and
Evolutionary Dynamics by Sandholm