Algorithmic Game Theory

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.

Alternatively, you can also have a look at the course page in the ETH course catalog (VVZ)

Weekly schedule

Lectures

weekly on Mondays, 9-12, in CAB G51 by

• Peter Widmayer "ATT." inf.ethz.ch  and
  
• Matúš Mihalák, matus.mihalak "ATT" maastrichtuniversity.nl

Problem Classes

weekly on Mondays, 15-17, in CAB G59 and in CAB G56

• Matúš Mihalák, matus.mihalak "ATT" maastrichtuniversity.nl
• Andreas Bärtschi, andreas.baertschi "A.T." inf.ethz.ch

Topics

• 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 solving (strategic) games
• 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. Some of the material presented in the lecture can be found in the following books:

• [AGT] Algorithmic Game Theory, edited by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani,
  Cambridge University Press, 2007.
  (An online copy of the book is available, requiring: username=agt1user, password=camb2agt. There are also errata available.)
• [GTS] Game Theory and Strategy, Philip D. Straffin,
  The Mathematical Association of America, fifth printing, 2004.
  (this book was used in the course three years ago and is available in the computer science library;
  its first few chapters cover some of the material of the first few weeks)

Problem Classes

There will be weekly exercise assignments. They will appear every Tuesday noon on this web page. You are encouraged to hand in solutions to the problems on Monday during the (following) lecture or at the beginning of the (same day) problem class. The (handed in) solutions will be looked at and returned with comments in the subsequent week.

Exam/Grades

There will be a written exam in the exam session. The exact date will be announced later by the examination office. It will take 3 hours. It will be a closed-book examination.

Following the new D-INFK guidelines for doctoral studies, PhD students get credit points according to the same rules that apply for Bachelor or Master students. That is, with a final grade of at least 4
doctoral students will receive 7KE, and 0KE otherwise.

What are the "sixth hour" in the Course Catalogue and the seventh credit point supposed to mean?

Apart from three regular lecture (V) hours and two hour of exercises (U), this course comes with one extra sixth hour of independent work (A); this makes 7 credit points. You will deserve the credits for the A-unit by independent work, i.e. studying and learning material (also prerequisites) on your own. Details will be announced at the beginning of the course the latest.

Schedule and Weekly Exercises