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

• Paolo Penna, paolo.penna "A.T" inf.ethz.ch

Problem Classes

Weekly on Mondays, 15-17 in CAB G 56 (names A - G), CAB G 59 (names H - O), IFW C 33 (names P - Z)

• Stefano Leucci, stefano.leucci "A.T" inf.ethz.ch
• Paolo Penna, paolo.penna "A.T" inf.ethz.ch
• Ye Wang, wangye "A.T" student.ethz.ch

Topics

• Games in strategic form and equilibrium concepts (pure, mixed, dominant strategies,...).
• Existence and computation of equilibria (potential games, complexity of computing Nash equilibria, regret minimization algorithm,...). Inefficiency of equilibria (Price of Anarchy, Price of Stability, analysis via the smoothness framework,...).
• Mechanism design (with and without money). Single-item auctions, first-price and Vickrey auction, characterizations of truthful mechanisms, applications, and complexity. Mechanisms without money, limitations of general voting schemes, constructions of incentive compatible mechanisms.

Literature

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:

• [ROU] Twenty Lectures on Algorithmic Game Theory, Tim Roughgarden, Cambridge University Press, 2016.
(The book is available in the computer science library - currently online version only.)
• [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.
  (A gentle introduction to the basic concepts of game theory. The book is available in the computer science library.)
• [NCM] Networks, Crowds, and Markets, David Easley and Jon Kleinberg, Cambridge University Press, 2010.
  (An online draft is available)
• ... more will be added.

Problem Classes

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

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 and will be a closed-book 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 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.

Frequently Asked Questions

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.

The following is a tentative program (errata on lecture notes):

Lecture	Topics	Lecture Notes	Exercise Sheet
1	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 set 1
2	Efficiency and computation of equilibria Price of anarchy, smooth framework, affine congestion games. An efficient algorithm for symmetric network congestion games.	Price of anarchy and hardness of equilibria (until Section 2.2 excluded)	Exercise set 2
3	More general equilibria and computation Hardness of pure Nash equilibria (polynomial local search, PLS-reductions, max-cut game, congestion games are PLS-complete) Mixed and (coarse) correlated equilibria. Price of anarchy for these equilibria via the smooth framework.	Mixed and correlated equilibria (plus Sections 2.2-2.4 in lecture notes 2)	Exercise set 3 (Graded Set)
4	Efficient computation of correlated equilibria. Regret minimization algorithm (multiplicative weights update). From regret-minimization to 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 (fair cost sharing games, tight bound). Truthful mechanisms (2nd price auction, shortest path, truthfulness).	Price of Stability and Introduction to Mechanism Design (until Section 2.2 included)	Exercise set 5
6	Two constructions of truthful mechanisms VCG mechanisms. One-parameter mechanisms (monotone algorithms, truthfulness). Examples of impossibility results.	Truthful one-parameter mechanisms	Exercise set 6 (Graded Set)
7	Truthful mechanisms and approximation Combinatorial auction (general setting and single minded bidders). VCG mechanisms, one-parameter, monotonicity and threshold payments. Two simple optimal mechanisms (greedy for single minded).	Incentives vs Computation	Exercise set 7
8	Mechanisms without money Voting systems, basic definitions (social welfare functions, social choice functions). Two alternatives vs many alternatives (tournament voting, majority, positional voting). Arrow's impossibility result, Gibbard-Satterthwaite Theorem. Single-peaked preferences and median voting.	Voting Systems (for single-peaked prefs: Chapter 23 of [NCM], Chapter 10 in [AGT])	Exercise set 8
9	Mechanisms without money II House Allocation (TTCA Algorithm, core allocation). Kidney Exchange (setting, TCCA vs Maximal Matching mechanism). Stable Matching.	Mechanism Design Without Money II (excluded: uniqueness of core allocation, proof of Thm 8.2 second part - truthfulness)	Exercise set 9 (Graded Set)
10	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 (excluded Section 3.3 - next lecture)	Exercise set 10
11	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	Exercise set 11
12	Sponsored search auctions Truthful VCG versus GSP used in practice. Guarantees of GSP (equilibria characterizations, symmetric equilibria, social welfare and revenue bounds).	Sponsored Search (see also here for a nice introduction and motivation)	Exercise set 12 (Graded Set)
13	Simple mechanisms (obviously truthful) Dominant vs 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