Algorithmic Game Theory, Autumn Semester 2020
Instructors
Paolo Penna
Assistants
Stanislas Gal
Gabriela Malenova
Varun Maram
Short Course Description
Game theory
provides a good model for the behavior and interaction of rational/selfish agents and
programs in largescale distributed 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.
The ETHZ Course Catalogue information can be found here.
Time and Place
First lecture 21 Sept, first Exercise Class 22 Sept.
Type 
Time 
Place 
Lectures 
Mon 1013 
CAB G61 
Exercise Class (Group 1) 
Tue 1012 
CAB G56 
Exercise Class (Group 2) 
Tue 1012 
CAB G57 
Exercise Class (Group 3) 
Tue 1618 
LFW B3 
Starting from Nov 2, lectures and exercise classes are on Zoom (details in Piazza).
Lectures are
livestreamed
and
recorded.
Recordings will appear online after 24 hours.
Note (exercise class groups):
Students are divided into the three groups according to the
family name as follows:
Group 1 = AHe;
Group 2 = HiM;
Group 3 = NZ.
Moving to another group is only possible in special cases, after the instructor approval, and according to the current ETH measures/rules. Priority will be given to students who have conflicts with other lectures. Students who need to be moved to a different group should contact
Stanislas Gal. Due to restricted rooms occupancy, an
online exercise session may also be offered on Zoom (details in
Piazza).
Piazza website
link
Further Info
Some Slides (organization, grading and exercises, course intro)
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). Singleitem auctions, firstprice and Vickrey auction, characterizations of
truthful mechanisms, applications, and complexity. Mechanisms without money, limitations of general voting schemes, constructions of incentive compatible mechanisms.
Material and 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 book:
 [ROU] Twenty Lectures on Algorithmic Game Theory, Tim Roughgarden, Cambridge University Press, 2016.
(The book is available in the computer science library.)
Further books containing additional material:
 [AGT] Algorithmic Game Theory, edited by N.
Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge University Press,
2007.
 [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.
Exercises
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. 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), and the best 3 of them will determine your "excercise grade".
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 closedbook examination.
Your final grade will be calculated as the weighted average of the
final written exam (weight 70%) and of the graded exercise sheets (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.
Frequently Asked Questions
What is
the meaning of "sixth hour" and "seventh credit point" in
the Course Catalogue?
Apart from the three hours of regular lectures (V) and two hours of
exercises (U), this course comes with one extra 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.
A tentative program:
Lecture 
Topics 
Lecture Notes 
Exercise Sheet 
1 
Introduction and motivations
 Strategic games and existence of (pure Nash) equilibria.
 Bestresponse 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 (Sect. 2.22.4 next week) 
Exercise set 2 
3 
More general equilibria and computation
 Hardness of pure Nash equilibria (polynomial local search, PLSreductions, maxcut game, congestion games are PLScomplete)
 Mixed and (coarse) correlated equilibria.
 Price of anarchy for these equilibria via the smooth framework.

Mixed and correlated equilibria (plus Sect. 2.22.4 in lecture notes 2) 
Exercise set 3 (Graded Set) 
4 
Efficient computation of correlated equilibria.
 Regret minimization algorithm (multiplicative weights update).
 From regretminimization to correlated equilibria.

Regret minimization and correlated equilibria (Section 2 next week) 
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.1) 
Exercise set 5 
6 
Two constructions of truthful mechanisms
 VCG mechanisms.
 Oneparameter mechanisms (monotone algorithms, truthfulness).
 Examples of impossibility results.

Truthful oneparameter mechanisms (plus Sect 2.2  2.4 in lecture notes 5; Section 3 next week) 
Exercise set 6 (Graded Set) 
7 
Truthful mechanisms and approximation
 Combinatorial auction (general setting and single minded bidders).
 VCG mechanisms, oneparameter, monotonicity and threshold payments.
 Two simple optimal mechanisms (greedy for single minded).

Incentives vs Computation (plus Sect 3 in lecture notes 6) 
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, GibbardSatterthwaite Theorem.
 Singlepeaked preferences and median voting.

Voting Systems (for singlepeaked prefs: Chapter 10 in [AGT] or Chapter 23 of [NCM].) 
Exercise set 8 
9 
Mechanisms without money II
 Arrow's Theorem (proof).
 House Allocation (TTCA Algorithm, core allocation).

Mechanism Design Without Money II (proof Arrow's Theorem in previous lecture notes) 
Exercise set 9 (Graded Set) 
10 
Mechanisms without Money II (contd)
 Kidney Exchange (setting, TTCA vs Maximal Matching mechanism).
 Stable Matching.
 Instability of "BGP" and bestresponse (introduction).

Mechanism Design Without Money II 
Exercise set 10 
11 
Bestresponse mechanisms
 Asynchronous bestresponse for distributed settings.
 The BGP game.
 Sufficient conditions for convergence and incentive compatibility.
 The GaoRexford Model for BGP.

Best response mechanisms (Section 3.4 next week) 
Exercise set 11 
12 
Bestresponse mechanisms II
 Application to TCP.
 Stable matching mechanisms revisited (proposal mechanism for InternsHospitals matching and other restrictions).
 Reproving incentive compatibility via bestresponse mechanisms.
 Singleitem auction revisited.

BestResponse Mechanisms II
and
Sponsored Search
(Section 1  see also here for a nice introduction and motivation 
Exercise set 12 (Graded Set) 
13 
Sponsored search auctions
 Truthful VCG versus GSP used in practice.
 Guarantees of GSP (equilibria characterizations, symmetric equilibria, social welfare and revenue bounds).
Plus a bonus/fun topic (to be decided)

Sponsored Search 
