Algorithmic Game Theory, Mechanism Design and Computational Economics (AGT-CE)
(Winter Semester 2017--2018, Max-Planck-Institut für Informatik)

Basic Information

OFFICIAL Course Webpage: CLICK HERE. In my opinion, the template there is not good (I was forced to use it), so I make this cleaner version of unofficial course webpage. All updates after 27 February, 2018 will be made to this cleaner webpage ONLY.

We welcome feedback about the lecture notes of this course. The feedback can be pointing out mistakes or typos in the lecture notes, or proposing some important materials about the topics which we have missed, or suggesting how the current materials might be better organized. Please send your feedback to ycheung [AT] mpi-inf [DOT] mpg [DOT] de

Lecturer: Yun Kuen Cheung, Marco
Tutor (also holding two lectures for this course): Bhaskar Ray Chaudhury
Course Time: Basically, weekly lecture on Monday (4-6pm), biweekly exercise session on Tuesday (2-4pm). But there are exceptions; please see the precise schedule below.

Course Description

Games and markets arise wherever there are two or more agents competing for selfish benefits. In their enormous applications, "agents" can refer to humans, animals, computers, bacterias or even molecules.

In the past 20 years, the algorithmic/computational aspects of game/market/auction theory have grown to become a popular topic in (theoretical) computer science, economics, operations research, dynamical system, and more. In this course, we will discuss the very core of this exciting new research direction. This course is divided into three parts.

In the first part, we cover some basic concepts in games, including Zero-sum Game and General-sum Game, Nash Equilibrium, Market Equilibrium, Correlated Equilibrium and Regret Minimization. Algorithms for finding such equilibria will be presented. Concerning equilibrium, one fundamental question is how good an equilibrium is. Prisoner Dilemma is a canonical example to show that Nash Equilibrium can be very bad. Efficiency measures and techniques, e.g., Price of Anarchy and Smoothness, will be covered.

In the second part, we address another fundamental question concerning equilibrium: how an equilibrium is reached. We will study a number of simple game/market dynamics, e.g., Multiplicative-Weight Updates, Tatonnement and Proportional Response Dynamic, aiming to explain how equilibrium can be reached in a highly distributed environment, in which individual agents can access very limited local information only. We will also look into an interesting special case of Linear Fisher and Arrow-Debreu markets, for which flow-type algorithms were developed.

In the third part, we focus on the prominent application of game theory in the digital era --- design of auction, or what we call the Mechanism Design, e.g., eBay, Google ad auction, spectrum auction. In the simplest setting, there is an auctioneer selling a number of items, and there are many bidders interested in those items. Mechanism design concerns Our course will have some overlaps with the following materials. We will also provide self-contained lecture notes in this webpage.

Lecture Notes, Exercise Sheets, Course Schedule and Suggested Readings

Lecture notes will be updated shortly after each lecture. Exercise sheet is handed out every two weeks, and typically you are given one week to finish; you are required to submit it just before the exercise session begins.

Date Lecture Content Lecture Note Exercise Sheet Remarks Suggested Readings
N/A Course Logistics Note 0
23 October, 2017 Basic Game Modelling Ideas
Pure and Mixed Strategies
Pure and Mixed Nash Equilibria
Note 1 Sheet 1 Quanta Magazine article: In Game Theory, No Clear Path to Equilibrium
30 October, 2017 Two-Person Zero-Sum Games
The Minimax Theorem
Understanding Multi-people General-Sum Games
Note 2 Andersen and Feige on Application of Zero-sum game on Probabilistic Mapping (discussing the work of Räcke in STOC 2008)
6 November, 2017 Price of Anarchy (PoA) and Price of Stability
Splittable Routing Game and its PoA Analysis
Note 2 (con't of last lecture) Sheet 2 Exercise Session on 7 November, 2017 Chen, Lu: Generalized Mirror Descents in Congestion Games (AAMAS 2014, Artificial Intelligence 2016)
13 November, 2017 Smoothness Framework of PoA Analysis
Unsplittable Routing Game: Existence and Algorithm
PLS-Completeness
Note 3 Exercise Session on 14 November, 2017 Awerbuch, Azar, Epstein: The Price of Routing Unsplittable Flow (STOC 2005, SICOMP 2013)

Lipton, Markakis, Mehta: Playing Large Games Using Simple Strategies (EC 2003)

In the lecture note, we have a rather concise section discussing PLS-completeness of Unsplittable Selfish Routing. See Roughgarden's Lecture Note for a more elaborated discussion.
20 November, 2017 Lemke-Howson Algorithm for Computing Nash Equilibrium of Two-Player General-sum Games
PPAD Complexity Class
Note 4 Sheet 3 Herings, Peeters: Homotopy Methods to Compute Equilibria in Game Theory (Economic Theory 2010)

Goldberg, Papadimitriou, Savani: The Complexity of the Homotopy Method, Equilibrium Selection, and the Lemke-Howson Solutions (FOCS 2011, ACM TEAC 2013)
27 November, 2017 Multiplicative Weight (MW) Algorithm
MW in Two-Person Zero-Sum Games
MW in General Games --- (Coarsely) Correlated Equilibrium
Note 5 Exercise Session on 28 November, 2017 Freund, Schapire: Adaptive Game Playing Using Multiplicative Weights (GEB 1999)

Daskalakis, Deckelbaum, Kim: Near-Optimal No-Regret Algorithms for Zero-sum Games (SODA 2011, GEB 2015)

Rakhlin, Sridharan: Optimization, Learning and Games with Predictable Sequences (NIPS 2013)

Arora, Hazan, Kale: The Multiplicative Weights Update Method: a Meta-Algorithm and Applications (Theory of Computing 2012)

Cesa-Bianchi, Lugosi: Prediction, Learning and Games (Cambridge University Press 2006)
4 December, 2017 Fisher Markets, Arrow-Debreu Markets
Market Equilibrium
Tatonnement
Note 6 Sheet 4 Cheung, Cole, Devanur: Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue (STOC 2013)
11 December, 2017 "Gap Narrowing" Analysis of Tatonnement
"Misspending Potential Function" Analysis of Tatonnement
Note 6 (con't of last lecture) Exercise Session on 12 Dec, 2017 (by Marco) Cole, Fleischer, Rastogi: Discrete Price Updates Yield Fast Convergence in Ongoing Markets with Finite Warehouses (arXiv 2010) This paper is recommended for more elaborate understanding of the misspending potential function. While reading the whole paper is appreciated, as a starting point, you may read Sections 1, 2.1, 2.2, 3.1 and 3.2 first.
18 December, 2017 Orlin's Weakly Poly-time Algorithm for Linear Fisher Markets Note 7 Sheet 5 Orlin: Improved Algorithms for Computing Fisher's Market Clearing Prices (STOC 2010)

Orlin: A Faster Strongly Polynomial Minimum Cost Flow Algorithm (Operations Research 1993)
8 January, 2018 Network Flow Algorithms for Linear Arrow-Debreu Markets (by Bhaskar) Note 8 Duan, Mehlhorn: A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market (ICALP 2013, Inf. Computation 2015)
9 January, 2018 Network Flow Algorithms for Linear Arrow-Debreu Markets (by Bhaskar) Note 8 (con't of last lecture) Sheet 6 Exercise Session on 15 January, 2018
22 January, 2018 Introduction to Mechanism Design
Combinatorial Auction
Truthfulness, VCG Mechanism and its Complexity Concern
Note 9 Exercise Session on 23 January, 2018 Lavi, Swamy: Truthful and Near-Optimal Mechanism Design via Linear Programming (FOCS 2005, JACM 2011)
29 January, 2018 Social Welfare and Config LP of Combinatorial Auction
Ellipsoid Method and Separation Oracle
Demand Oracle
Gross Substitute / Greedy Solvable Valuation Functions
Note 10 Paes Leme: Gross Substitutability - An Algorithmic Survey (GEB 2017)
30 January, 2018 Truthful Mechanism Design without Monetary Transfer Note 11 Sheet 7 There will not be an exercise session to cover Sheet 7. Instead, immediately after its due date, we will send a solution outline to students' emails. Procaccia, Tennenholtz: Approximate Mechanism Design without Money (EC 2009, ACM TEAC 2013)

Guo, Conitzer: Strategy-proof allocation of multiple items between two agents without payments or priors (AAMAS 2010)

Cole, Gkatzelis, Goel: Mechanism Design for Fair Division - Allocating Divisible Items without Payments (EC 2013)

Cheung: Better Strategyproof Mechanisms without Payments or Prior - An Analytic Approach (IJCAI 2016)


Imprint | Data Protection