Short course description

Game theory provides a good model for the behavior and interaction of the selfish users and programs in large-scale distributed computer systems without central control. The course discusses algorithmic aspects of game theory, such as a general introduction to game theory, auctions, mechanisms, the costs of a central control optimum versus those of an equilibrium under selfish agents, and algorithms and complexity of computing equilibria.

You can also have a look at the course page in the ETHZ Vorlesungsverzeichnis.

Weekly schedule

Lectures take place weekly on Thursdays, 08.15-10.00, in CAB G11, by

• Peter Widmayer, widmayerinf.ethz.ch, CAB H15
• Matú&scaron Mihaľák, matus.mihalakinf.ethz.ch, CAB H33.3

• Elias Vicari, vicarielinf.ethz.ch, CAB H31.2
• Davide Bilò, davide.biloinf.ethz.ch, CAB J21.2

Topics

• Introduction (algorithmic game theory basics)
• Basic Concepts of Game Theory (games in strategic form, games in extensive form, pure strategies and mixed strategies in games, solution concepts of games, important games)
• Computational issues of game solutions
• Algorithmic Mechanism Design (basic ideas of mechanism design, social welfare and social choice, voting systems, Vickrey's second price auction, VCG mechanisms, dominant strategies and the revelation principle, computational issues, applications)
• Inefficiency of Equilibria (fundamental network examples, routing games, price of anarchy, price of stability, network creation games)

Literature

• There are no lecture notes for the course. Taking your own notes is advisable.
• [AGT] Algorithmic Game Theory, edited by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge University Press (to appear in November 2007)
• Game Theory and Strategy, Philip D. Straffin, The Mathematical Association of America, fifth printing, 2004
  (this book was used in the last year course and is available in the computer science library; its first few chapters cover some of the material of the first few weeks)

Advised Reading

• The papers that follow are particularly relevant for some topics of the lecture.
• [1] Vincent Conitzer, Tuomas Sandholm. Complexity Results about Nash Equilibria. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), 2003.
• [2] Noam Nisan, Amir Ronen. Algorithmic Mechanism Design. In Proceedings of the 31st ACM Symposium on Theory of Computing, pages 129-140, 1999.
• [3] Aaron Archer, Eva Tardos. Truthful Mechanisms for One-Parameter Agents. In Proceedings of the IEEE Symposium on Foundations of Computer Science, pages 482-491, 2001.
• [4] Daniel Lehmann, Liadan Ita O'Callaghan, Yoav Shoham. Truth revelation in approximately efficient combinatorial auctions. In Journal of the ACM. Volume 49, Issue 5, pages 577-602, 2002.

Schedule

Exercises

Exam