Spring 2005: Computing Equilibria in Markets and Games

22c:196, Sec 003

Time and Place: 3.55--5.10, TTh, 217 MLH

The notion of equilibria in markets and in games is a distinguished and well-studied concept. We will introduce these notions along with the required background and study the classical proofs of existence and computational procedures (Lemke-Howson, Scarf, etc.) for computing these equilibria. We will also study some applications of solution concepts for cooperative games and of mechanism design.

Since these classical algorithms may take exponential time in the worst case, computer scientists have recently begun to investigate the situations under which polynomial-time algorithms are possible. We will study several recent methods that have been developed in this context. These include methods based on convex programming, as well as combinatorial methods. We will also review some applications, developed by computer scientists, of the concept of equilibrium.

The classical material (a third of the course) will be drawn from textbooks, and the more recent algorithms (two-thirds of the course) from research papers. The course is aimed at computer science students, so the main prerequisite is the graduate/undergraduate algorithms course.
References:

For basic concepts in game theory -- noncooperative games, Nash equilibria, correlated equilibria, coalitional game theory -- we will refer to the text by Osborne and Rubinstein: A course in game theory.
Selfish Load balancing and Atomic Congestion Games , by Suri, Toth, And Zhou.
How bad is selfish routing? , by Roughgarden and Tardos.
On the core of the multicommodity flow game, by Markakis and Saberi, in EC 03.
Minimum cost spanning tree games, by Granot and Huberman, in Mathematical Programming, 1991.

For an introduction to mechanism design, chapter 23 of Mas-Colell, Whinston, Green: Microeconomic theory
Algorithmic mechanism design , Nisan and Ronen.
Competitive auctions and digital goods , by Goldberg, Hartline, and Wright.

For the Lemke-Howson algorithm, which not only computes an equilibrium for a 2-person game but also shows its existence, Bernhard von Stengel's survey: Computing equilibria for two-person games
On the complexity of pure Nash equilibria , by Fabrikant, Papadimitriou, and Talwar.
On complexity as bounded rationality, Papadimitriou and Yannakakis, STOC 1994.
Computing correlated equilibria in multiplayer games , by Papadimitriou.
On the value of private information , by Kleinberg, Papadimitriou, and Raghavan.

Truth revelation in approximately efficient combinatorial auctions , Lehmann, O'Callaghan, and Shoham.
Sharing the cost of multicast transmissions , Feigenbaum, Papadimitriou, and Shenker.
Applications of approximation algorithms to cooperative games , Jain and Vazirani.

Handouts

The firstday handout , which includes a slightly broader view of the course.
Homework 1 , due September 13.
Homework 2 , due October 11.
Homework 3 , due November 2.