6.896: Topics in Algorithmic Game Theory

Spring 2010

As Computer Science struggles to understand the Internet and its capabilities, computer scientists are incorporating concepts and methodologies from Economics and Game Theory into their discipline. In the past decade, there has been a tremendous growth in research, centering around the following questions: what game-theoretic tools are applicable to computer systems? How far is the performance of a system from optimality due to the conflict of interests of its users and administrators? And how can we design a system whose performance is robust with respect to the potential conflict of interests inside the system?

This class aims to tackle some of the fundamental problems at the interface of Computer Science and Game theory, with an emphasis on algorithms and computational complexity. Our main focus will be on algorithms for equilibria, the complexity of equilibria and fixed points, algorithmic tools in mechanism design, learning in games, and the price of anarchy.

Another Class of Potential Interest: 6.254 --- Game Theory with Engineering Applications

Course Information

Course Outline

There is a significant dynamic component to the course, as topics drop in and out, or get longer or shorter treatment, depending on audience interest/reaction/resistence. We consider this a feature. Given this, here is a rough outline of the course material:

Lectures (Scribe Sheet)

Please us the scribe template to produce your notes. The template contains commands for Theorem, Lemma, Corollary, Proposition, Claim, Definition, Construction, Remark etc. An example file where this template is used is here .

Online Resources

Different incarnations of the class at other universities: