Department of Computer Science  Institute of Theoretical Computer Science
Game theory provides a good model for the behavior and interaction of the selfish users and programs in largescale 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 on Mondays, 912, in CAB
G51
Weekly on Mondays, 1517 in CAB G 56 (names A  G), CAB G 59 (names H  O), IFW C 33 (names P  Z)
There will be 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:
Weekly exercise assignments will be published on this web page (shortly after each lecture). 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.
There will be four graded exercise sheets that will contribute with a weight of 30% towards the final grade. The graded exercise sheets will be every third lecture (weeks 3, 6, 9, 12).
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 and will be a closedbook examination.
Your final grade will be calculated as the weighted average of the final written exam (weight 70%) and of the graded exercise sheet (weight 30%).
Following the new DINFK 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 is the meaning of "sixth hour" and "seventh credit point" in the Course Catalogue?
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 Aunit 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.
Lecture  Topics  Lecture Notes  Exercise Sheet  

1  Introduction and motivations

Strategic games, equilibria, congestion games  Exercise set 1  
2  Efficiency and computation of equilibria

Price of anarchy and hardness of equilibria (until Section 2.2 excluded) 
Exercise set 2  
3  More general equilibria and computation

Mixed and correlated equilibria (plus Sections 2.22.4 in lecture notes 2) 
Exercise set 3 (Graded Set) 

4  Efficient computation of correlated equilibria.

Regret minimization and correlated equilibria (proof of Proposition 8 in next lecture) 
Exercise set 4  
5  Price of Stability. Mechanisms with money

Price of Stability and Introduction to Mechanism Design (until Section 2.2 included) 
Exercise set 5  
6  Two constructions of truthful mechanisms

Truthful oneparameter mechanisms  Exercise set 6 (Graded Set) 

7  Truthful mechanisms and approximation

Incentives vs Computation  Exercise set 7  
8  Mechanisms without money

Voting Systems (for singlepeaked prefs: Chapter 23 of [NCM], Chapter 10 in [AGT]) 
Exercise set 8  
9  Mechanisms without money II

Mechanism Design Without Money II (excluded: uniqueness of core allocation, proof of Thm 8.2 second part  truthfulness) 
Exercise set 9 (Graded Set) 

10  Bestresponse mechanisms

BestResponse Mechanisms (excluded Section 3.3  next lecture) 
Exercise set 10  
11  Bestresponse mechanisms II

BestResponse Mechanisms II  Exercise set 11  
12  Sponsored search auctions

Sponsored Search (see also here for a nice introduction and motivation) 
Exercise set 12 (Graded Set) 

13  Simple mechanisms (obviously truthful)

Obviously Strategyproof Mechanisms 