Algorithmic Game Theory, Autumn Semester 2021

Instructor

Assistants

Andrei Ivanov
Lorenzo Laneve
Varun Maram

Short Course Description

Game theory provides a good model for the behavior and interaction of rational/selfish agents and programs in large-scale 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.

Some of the applications we shall discuss in the lectures or in the exercises include: BGP and TCP protocols, Google sponsored search, Generative Adversarial Networks, Reinforcement Learning approaches.

The ETHZ Course Catalogue information can be found here.

Time and Place (changed schedule!)

First lecture ~~27th September~~ 24th September, first Exercise Class 28th September (no exercise class first week).

Type	Time	Place
Lectures	~~Mon 10-13~~ Fri 10-13	~~CAB G51~~ CHN C14
Exercise Class (Group 1)	Tue 10-12	CAB G57
Exercise Class (Group 2)	Tue 10-12	CAB G59
Exercise Class (Group 3)	Tue 16-18	LFW B3

Note (exercise class groups):

Students are divided into the three groups according to the family name (groups will be announced soon).

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 Varun Maran.

Moodle

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

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.

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)
[PET] Game Theory, Hans Peters, Springer, 2000.
(Excellent source to understand basic concepts in this course - and others - via simple examples)

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 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 sheets (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 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 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.

A tentative program:

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 (Video Recording)	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 Finding a pure Nash equilibria may be hard	Price of anarchy and Hardness of equilibria - sect 2.2-2.3 next week (Video Recording)	Exercise Set 2
3	More general equilibria and computation More general equilibria (mixed and correlated equilibria) Price of anarchy for general equilibria via the smooth framework	Mixed and correlated equilibria (Video Recording)	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 (Video Recording)	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) VCG mechanisms	Price of Stability and Introduction to Mechanism Design - sect 2.4 next week (Video Recording)	Exercise Set 5
6	Two constructions of truthful mechanisms Longest path (impossibility result) One-parameter mechanisms (monotone algorithms, truthfulness) More of impossibility results	Truthful One-Parameter Mechanisms (Video Recording)	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 and Computation (Video Recording)	Exercise Set 7
8	Mechanisms without money Sequential-Dictator Mechanism House Allocation, Kidney Exchange, Stable Matching Stronger guarantees (coalitions, core, stability)	Mechanisms Without Money - Thm 8.6 and Thm 8.7 (truthfulness) next week (Video Recording)	Exercise Set 8
9	Best-response mechanisms Best-response in (asynchronous) distributed settings Instability of "BGP" and best-response. Convergence and incentive compatibility and more mechanisms without money (single-peaked domains)	Best response mechanisms - from Def 7 onwards next week, Single peaked domains - in AGT book (Video Recording)	Exercise Set 9 (Graded Set)
10	Best-response mechanisms II Convergence and incentive compatibility The real BGP and the TCP protocols More applications (stable-matching, interns-hospitals matching, single-item auction)	Best response mechanisms II (Video Recording)	Exercise Set 10
11	Sponsored search auctions Theory vs practice (truthful VCG versus GSP) Guarantees of GSP (equilibria characterizations, social welfare and revenue)	Sponsored search and (non-)truthful mechanisms (Video Recording)	Exercise Set 11
12	Very easy games (obviously strategyproof) Dominant and obviously dominant strategies Extensive form games (simple examples) Obviously strategyproof mechanisms (with and without money)	Very easy games: Obviously Strategyproof Mechanisms (Video Recording)	Exercise Set 12 (Graded Set)
13	Very hard games Generative adversarial networks Extensive form games, repeated games, reinforcement learning methods	Very hard games (Video Recording)