Short course description

Game theory provides a good model for the behavior and interactionof the selfish users and programs in large-scale distributed computersystems without central control. The course discusses algorithmicaspects of game theory, such as a general introduction to game theory,auctions, mechanisms, the costs of a central control optimum versusthose of an equilibrium under selfish agents, and algorithms andcomplexity 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, peter.widmayer "A.T." inf.ethz.ch and
• Matúš Mihalák, matus.mihalak "A.T." inf.ethz.ch

Problem Classes

weekly on Mondays, 15-17, in CAB G59 and in CHN G42

Topics

• Sandro Montanari, sandro.montanari "A.T." inf.ethz.ch (in CAB G59)
• Matúš Mihalák, matus.mihalak "A.T." inf.ethz.ch (in CHN G42)

• 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)

The LaTeX references are as follows:

• The not so Short Introduction to LaTeX2e by Tobi Oetiker.
• The t tex file presented in the short tutorial during the exercise class.
• The Latex Introduction presentation.

Problem Classes

There will be weekly exercise assignments. They will appear every Tuesday morning 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. Note, however, that only the specially marked exercises (see below) will count towards your grade. Nevertheless we strongly recommend that you solve all weekly problems and attend the exercise classes.

Exam/Grades

Your final grade will be calculated as the the weighted average of:

• 70% final written exam. Written notes of any kind are not permitted. The exam takes place in the exam session. The exact date will be announced later by the examination office.
• 30% exercises. In week 3, 5, 8 and 11 of the term (roughly) we will hand out a specially marked exercise whose solution (typeset in LaTeX) is due two weeks later. These solutions will be graded, and your three best grades will each account for 10% of your final grade. You are welcome to discuss these exercises with your colleagues, but we expect you to hand in your own writeup.

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 (calculated as explained above) you 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 prerequisistes) on your own. Details will be announced at the beginning of the course the latest.

Schedule and Weekly Exercises