Algorithmic Game Theory, Mechanism Design and Computational Economics

Advanced Course, 2+1

Announcements

This course is done. This webpage will NOT be further updated. However, we will make further updates (adding new materials, fixing typos) to the lecture notes; please see the cleaner course webpage for such updates.

- (15 Jan) Exercise Sheet 6 out. Deadline is 23 Jan, 2018.
- (18 Dec) Exercise Sheet 5 out. Deadline is 9 Jan, 2018.
- (4 Dec) Exercise Sheet 4 out. Deadline is 12 Dec.
- (20 Nov) Exercise Sheet 3 out. Deadline is 28 Nov.
- (6 Nov) Exercise Sheet 2 out. Deadline is 14 Nov.
- (23 Oct) Exercise Sheet 1 out. Deadline is 7 Nov.
- (14 Oct) Since the Semester-kick-off Meeting will be held at 4:30pm on 16 Oct, our first lecture will start on 23 October, 2017
.

Basic Information

Lecturer: Yun Kuen Cheung (You may call me Marco.)
Lectures: Monday 4pm to 6pm, Room 021 in Building E1.4
Tutor: Bhaskar Ray Chaudhury
Tutorials: Alternating Tuesday 2pm to 4pm, Room 021 in Building E1.4
Credits: 5
Prerequisites: The following knowledge is assumed from enrolled students:
  • Basic knowledge in algorithms and data structure, and their analyses
  • Calculus, including the concepts of limit, convergence, derivative and integration
  • Basic Linear Algebra, including how to solve linear systems
The following knowledge will be useful in some parts of the course, but NOT a prerequisite for enrolling:
  • Basics of probability theory (what are discrete/continuous distributions, expected values and variances)
  • Linear programming and its duality
  • Basic max-flow algorithm, e.g. Ford-Fulkerson
 
 For more details about course logistics, syllabus, exercises and examinations, click here.

 

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, operational research, dynamical system, and more. In this course, we will discuss the very core of this exciting new research direction.

For ambitious students who want to develop rigorous theoretical training related to this topic, I can suggest extra materials for reading and thinking.

This course is divided into three parts.

In the first part, we cover some basic concepts in games and markets, including Zero-sum Game and General-sum Game, Nash EquilibriumMarket Equilibrium, Correlated Equilibrium and Regret Minimization. Algorithms for finding such equilibria in 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. 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/Exchange market, 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 agents who are interested in those items. Mechanism design concerns

  • the design of communication protocols between auctioneer and agents
  • design of efficient (poly-time, or even stricter time requirement due to practical applications) algorithms to decide the allocation of items which achieve good efficiency
  • design of truthful mechanism which motivates agents not to be strategic on reporting their preferences

Online Reference

Our course will have some overlaps with the following materials. We will also provide self-contained lecture notes in this webpage.

Lectures and Exercises

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

Below is a tentative schedule on the topics to be discussed. They are subject to change.

DateLecture TopicsExercise SheetRemarksRemarks / Suggested Readings
N/ACourse Logistics --- CLICK HERE   
23 Oct, 2017 
  • Basic Game Modelling Ideas
  • Pure and Mixed Strategies
  • Pure and Mixed Nash Equilibrium
Lecture Note 1 --- CLICK HERE
Exercise Sheet 1 --- CLICK HERE Quanta Magazine article: In Game Theory, No Clear Path to Equilibrium
30 Oct, 2017 
  • Two-Person Zero-sum Games
  • The Minimax Theorem
  • Understanding Multiple-People General-sum Games
Lecture Note 2 --- CLICK HERE
  Andersen and Feige on Application of Zero-sum game on Probabilistic Mapping (discussing the work of Räcke in STOC 2008)
6 Nov, 2017 
  • Price of Anarchy (PoA) and Price of Stability (PoS)
  • Splittable Routing Game and its PoA Analysis
Lecture Note 2 (continuation of last lecture) --- CLICK HERE
Exercise Sheet 2 --- CLICK HEREExercise Session on 7 Nov, 2017Chen, Lu: Generalized Mirror Descents in Congestion Games (AAMAS 2014, Artificial Intelligence 2016)

Tsaknakis, Spirakis: An Optimization Approach for Approximating Nash Equilibria (WINE 2007, Internet Maths. 2008) --- Also trace the literature cited in this paper about the gradient-descent based approach for finding Approximate NE.
13 Nov, 2017 
  • Smoothness framework of PoA Analysis
  • Unsplittable Selfish Routing: Existence & Algorithm
  • PLS-Completeness (self-reading)
Lecture Note 3 --- CLICK HERE
 Exercise Session on 14 Nov, 2017Awerbuch, 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 Nov, 2017 
  • Lemke-Howson Algorithm for Computing Nash Equilibrium of Two-Player General-sum Games
  • PPAD Complexity Class
Lecture Note 4 --- CLICK HERE
Exercise Sheet 3 --- CLICK HERE 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 Nov, 2017 
  • Multiplicative Weight (MW) Algorithm
  • MW in Two-Person Zero-Sum Games
  • MW in General Games --- (Coarsely) Correlated Equilibrium

Lecture Note 5 --- CLICK HERE

 Exercise Session on 28 Nov, 2017Freund, 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 Dec, 2017 
  • Fisher Markets, Arrow-Debreu Markets
  • Market Equilibrium
  • Tatonnement

Lecture Note 6 --- CLICK HERE

Exercise Sheet 4 --- CLICK HERE

(This is a corrected version of exercise sheet --- there are 2 standard and 3 bonus exercises in it.)
 Cheung, Cole, Devanur: Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue (STOC 2013)
11 Dec, 2017 
  • "Gap Narrowing" Analysis of Tatonnement
  • "Misspending Potential Function" Analysis of Tatonnement
Lecture Note 6 (continuation of last lecture) --- CLICK HERE
 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 Dec, 2017 
  • Orlin's Weakly Poly-time Algorithm for Linear Fisher Markets

Lecture Note 7 --- CLICK HERE

Exercise Sheet 5 --- CLICK HERE 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 Jan, 2018 
  • Network Flow Algorithms for Linear Arrow-Debreu Markets (by Bhaskar)

Lecture Note 8 --- CLICK HERE

  Duan, Mehlhorn: A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market (ICALP 2013, Inf. Computation 2015)
9 Jan, 2018Lecture Note 8 (continuation of last lecture) --- CLICK HEREExercise Sheet 6 --- CLICK HEREExercise Session on 15 Jan, 2018 (Monday) 
22 Jan, 2018 
  • Introduction to Mechanism Design
  • Combinatorial Auction
  • Truthfulness, VCG Mechanism and its Complexity Concern

Lecture Note 9 --- CLICK HERE

 Exercise Session on 23 Jan, 2018Lavi, Swamy: Truthful and Near-Optimal Mechanism Design via Linear Programming (FOCS 2005, JACM 2011)
29 Jan, 2018 
  • Social Welfare and Config LP of Combinatorial Auction
  • Demand Oracle
  • Gross Substitute Valuation

Lecture Note 10 --- CLICK HERE

  Paes Leme: Gross Substitutability - An Algorithmic Survey (GEB 2017)
30 Jan, 2018 
  • Truthful Mechanism Design without Monetary Transfer
(THIS IS A TUESDAY!!!)

Lecture Note 11 --- CLICK HERE
Exercise Sheet 7 --- CLICK HERE 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)

There will not be an exercise session to cover Exercise Sheet 7. Instead, we will post solutions of Exercise Sheet 7 immediately after its due date.