Spring 2005: Computing Equilibria in Markets and Games

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.