Department of Computer Science | Institute of Theoretical Computer Science
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 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 on Mondays, 9-12, in CAB
G51 by
Weekly on Mondays, 15-17, in CAB G56 (Abä - Fur), CAB G59 (Gal - Pfis), NO D11 (Que - Zür)
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:
There will be weekly exercise assignments. They will appear every Monday 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.
There will be one graded exercise sheet that will contribute with a weight of 15% towards the final grade. The graded exercise sheet will be in the middle of the semester.
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.
Your final grade will be calculated as the weighted average of the final written exam (weight 85%), and of the graded exercise sheet (weight 15%).
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 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 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.
| Date | Topic | Lecture Notes | Exercise Sheets |
| Sep 21 | Introduction; Congestion games, existence of pure Nash equilibria, Rosenthal's potential function; Quick convergence of best-response dynamics in singleton games | Motivation Congestion Games | Game Theory Basics Exercise Sheet 1 (Due Sep 28) |
| Sep 28 | Computing pure Nash equilibria in network congestion games; Search problems and complexity class PLS; Complexity of finding a pure Nash equilibrium in congestion games | Complexity of Pure Nash Equilibria in Congestion Games | Exercise Sheet 2 (Due Oct 5) |
| Oct 5 | Congestion games beyond pure Nash equilibria; No-regret learning dynamics, the multiplicative weights algorithm and external regret, black-box reduction from external to swap regret, coarse and correlated equilibria | No Regret Dynamics | Exercise Sheet 3 (Due Oct 12) |
| Oct 12 | Quantifying the (in)efficiency of equilibria; Definition of price of anarchy and price of stability, the smoothness framework; Tight bounds on the price of anarchy in atomic and non-atomic congestion games with affine cost functions | Price of Anarchy in Congestion Games | Exercise Sheet 4 (Due Oct 19) |
| Oct 19 | Price of stability, strong Nash equilibria, symmetric and asymmetric cost sharing games; Introduction to mechanism design, how to bid in a single-item auction, first-price auction, Vickrey auction, truthfulness and dominant strategy incentive compatibility | Price of Stability in Congestion Games Introduction to Mechanism Design | Exercise Sheet 5 (Due Oct 26) |
| Oct 26 + Nov 2 | Characterizing truthfulness; Truthful single-parameter mechanisms; single-parameter mechanism design problems, DSIC/truthful mechanisms, implementable outcome rules; Myerson's Lemma, the VCG Mechanism for single- parameter problems; Single-item auctions, sponsored search auctions, scheduling on parallel related machines | Truthful Single-Parameter Mechanisms | Exercise Sheet 6 (Due Nov 2) Exercise Sheet 7 (Due Nov 9) |
| Nov 9(Lecture will be in CAB G 11) | The tradeoff between incentives and computation; single-minded combinatorial auctions; hardness and hardness of approximation; the greedy mechanisms of LOS; Case study: Spectrum Auctions; Deferred- acceptance auctions, the locally highest bid mechanism | The Tradeoff between Incentives and Computation | Graded Problem Set (Due Nov 18) |
| Nov 16 | Multi-parameter mechanism design, the VCG mechanism, black-box reductions; the Lavi-Swamy reduction; discussion of truthful mechanism design, impossibility of a general black-box reduction, conjecture: black-box reduction for downward closed environments | Truthful Multi-Parameter Mechanisms and Black-Box Reductions | Exercise Sheet 9 (Due Nov 23) |
| Nov 23 | Non- truthful mechanisms and the smoothness framework; smooth mechanisms, extension theorem; greedy mechanisms for multi-minded combinatorial auctions, combinatorial auctions with item bidding | Non-Truthful Mechanisms and the Smoothness Framework | Exercise Sheet 10 (Due Nov 30) |
| Nov 30 | Non- truthful mechanisms beyond the worst-case, Price of stability and equilibrium refinements; Sponsored Search Auctions, the Generalized Second Price or GSP mechanism; Symmetric Nash equilibria and locally envy free equilibria, welfare and revenue guarantees for symmetric equilibria |
Non-Truthful Mechanisms Beyond the Worst Case
(Or: How Google Got so Incredibly Rich) |
Exercise Sheet 11 (Due Dec 7) |
| Dec 7 | Mechanism design without money; allocation problems; House allocation, Top Trading Cycles Algorithm; Kidney exchange, priority matching mechanism; Stable matching, stable marriage, Proposal Algorithm | Mechanism Design without Money I (House Allocation, Kidney Exchange, Stable Matching) | Exercise Sheet 12 (Due Dec 14) |
| Dec 14 | Mechanism design without money; Voting systems; Voting with two alternatives, majority voting; Voting with many alternatives, tournament voting, voting by pairwise majority, positional voting; Arrow's impossibility result, Gibbard- Satterthwaite Theorem | Mechanism Design without Money II (Voting Systems) | No problem set |