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 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 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 26 | Introduction and motivations; Strategic games and existence of (pure Nash) equilibria; Best-response dynamics (convergence in potential games); Congestion games (and the restriction to singleton congestion games). | Strategic games, equilibria, congestion games | Exercise Sheet 1 (due Oct 3) |
| Oct 3 | Efficiency of equilibria (price of anarchy, smooth framework, affine congestion games); Computation of equilibria (efficient algorithms for special cases, local search problems (PLS), PLS-completeness of congestion games). | Price of anarchy and hardness of computing equilibria | Exercise Sheet 2 (due Oct 10) |
| Oct 10 | Mixed and (coarse) correlated equilibria; Price of anarchy for these equilibria via the smooth framework; Regret minimization algorithm (towards efficient computation of correlated equilibria) | Mixed, correlated equilibria,
and regret minimization
(excluded Section 4 - will be explained next week) |
Exercise Sheet 3 (due Oct 17) |
| Oct 17 | Coarse Correlated Equilibria from Regret-Minimization. Price of Stability (fair cost-sharing games, another use of potential function). Mechanisms with Money (2nd price auction, VCG mechanisms, truthfulness) | Price of Stability, Introduction to Mechanism Design (and Section 4 in previous lecture notes for regret-minimization) |
Exercise Sheet 4 (due Oct 25) |
| Oct 24 | Truthful One-Parameter Mechanisms (characterizations and constructions via monotonicity). Mechanisms for minimizing the maximum cost (makespan in related and unrelated machines); Impossibility of exact or approximate truthful mechanisms (multi parameter problems); The voluntary participation condition. | Truthful One-Parameter Mechanisms | Exercise Sheet 5 (due Oct 31) |
| Oct 31 | Combinatorial auction (welfare maximization using VCG); Single-minded combinatorial auctions (hardness and hardness of approximation); Computationally efficient truthful mechanisms (two greedy mechanisms using the one-parameter setting, and their optimality). | Tradeoff Between Incentives and Computation | Exercise Sheet 6 (due Nov 7) |
| Nov 7 | 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; Single-peaked preferences and median voting. | Mechanism Design Without Money (see also Chapter 23 of [NCM] for single-peaked prefs) |
Graded Problem Set (due Nov 17) |
| Nov 14 | Mechanism design without money (three important restrictions): House Allocation (Top Trading Cycle Algorithm); Kidney Exchange (limitations of TTCA and matching algorithm); Stable Matching (proposal algorithm). | Mechanism Design Without Money II (House Allocation, Kidney Exchange, Stable Matching) |
Exercise Sheet 8 - in 2 parts (Ex 1 and 2 discussed and solved during exercise class; Ex 3 will be discussed directly in exercise class Nov 21) |
| Nov 21 | Introduction to Best-response Mechanisms: Asynchronous best-response for distributed settings; The BGP game; Sufficient conditions for convergence and incentive compatibility; The Gao-Rexford Model for BGP. | Best-Response Mechanisms and BGP (excluded section 3.4 - will be explained next week) |
Exercise Sheet 9 (due Nov 28) |
| Nov 28 | Best-Response Mechanisms II: Application to TCP; Stable Matching mechanisms revisited (proposal mechanism for Interns-Hospitals matching and other restrictions); Re-proving incentive compatibility via Best-response Mechanisms; Single-Item Auction revisited. | Best-Response Mechanisms II (TCP, Stable Matching revisited, 2nd-Price Auction) |
Exercise Sheet 10 (due Dec 6) |
| Dec 5 | Sponsored Search Auctions: truthful VCG versus GSP used in practice; Guarantees of GSP (equilibria characterizations, symmetric equilibria, social welfare and revenue bounds). | Sponsored Search and (Non-)Truthful Mechanisms | Exercise Sheet 11 (due Dec 12) |
| Dec 12 | Dominant and Obviously Dominat Strategies; Obviously Strategyproof Mechanisms (extensive form games, basic definitions). Examples of Obviously Strategyproof Mechanisms (Interns-Hospitals matching, ascending price auctions, cost-sharing). | Obviously Strategyproof Mechanisms | Exercise Sheet 12 |
| Dec 19 | Another construction of Obviously Strategyproof Mechanisms: Defferred-Acceptance Mechanisms; Application to Single-minded Combinatorial Auction; DA Mechanisms and Ascending Price Auctions. | Deferred-Acceptance Mechanisms | No problem set |