Algorithmic Game Theory, Mechanism Design and Computational Economics
Advanced Course, 2+1
Announcements
 (6 Nov) Exercise Sheet 2 out. Deadline is 14 Nov.
 (23 Oct) Exercise Sheet 1 out. Deadline is 7 Nov.
 (14 Oct) Since the Semesterkickoff 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:

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 Zerosum Game and Generalsum Game, Nash Equilibrium, Market 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 flowtype 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 (polytime, 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 selfcontained lecture notes in this webpage.
 Thomas Ferguson's text on "Game Theory"
 Tim Roughgarden's courses on "Algorithmic Game Theory" and "Frontiers in Mechanism Design"
 Jason Hartline's text on "Mechanism Design and Approximation"
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.
Date  Lecture Topics  Exercise Sheet  Remarks  Remarks / Suggested Readings 
N/A  Course Logistics  CLICK HERE  
23 Oct, 2017 
 Exercise Sheet 1  CLICK HERE  Quanta Magazine article: In Game Theory, No Clear Path to Equilibrium  
30 Oct, 2017  TwoPerson Zerosum Games & the Minimax Theorem Understanding MultiplePeople Generalsum Games Lecture Note 2  CLICK HERE  Andersen and Feige on Application of Zerosum 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 HERE  Exercise Session on 7 Nov, 2017  Chen, 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 gradientdescent based approach for finding Approximate NE. 
13 Nov, 2017  Smoothness framework of PoA Analysis Unsplittable Selfish Routing: Existence & Algorithm PLSCompleteness (selfreading) Lecture Note 3  CLICK HERE  Exercise Session on 14 Nov, 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 PLScompleteness of Unsplittable Selfish Routing. See Roughgarden's Lecture Note for a more elaborated discussion.  
20 Nov, 2017  LemkeHowson Algorithm for Computing Nash Equilibrium of TwoPlayer Generalsum 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 LemkeHowson Solutions (FOCS 2011, ACM TEAC 2013)  
27 Nov, 2017  Multiplicative Weight Updates Coarse Correlated Equilibrium  Exercise Session on 28 Nov, 2017  
4 Dec, 2017  Fisher Markets, Market Equilibrium Tatonnement in Fisher Market, and Misspending Potential Function (Exercise Sheet 4 OUT)  
11 Dec, 2017  Proportional Response Dynamics in Fisher Market Basic Concepts/tools in Network Flow Algorithm for Computing Market Equilibrium  Exercise Session on 12 Dec, 2017 (by Marco)  
18 Dec, 2017  Orlin's Weakly Polytime Algorithm ArrowDebreu Markets, Balanced Flow, (Exercise Sheet 5 OUT)  
8 Jan, 2018  Network Flow Algorithms for Linear ArrowDebreu Markets (by Bhaskar)  Exercise Session on 9 Jan, 2018  
15 Jan, 2018  Network Flow Algorithms for Linear ArrowDebreu Markets (by Bhaskar) (Exercise Sheet 6 OUT)  
22 Jan, 2018  Introduction to Mechanism Design Combinatorial Auction Truthfulness, VCG Mechanism and its Complexity Concern  Exercise Session on 23 Jan, 2018  
29 Jan, 2018  Truthful Mechanism Design without Money Transfer Normed Utility Model SwapDictatorial Mechanism Partial Allocation Mechanism (Exercise Sheet 7 OUT)  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.  
30 Jan, 2018  GeneralizedSecondPrice (GSP) Auction PoA Analysis of GSP Auction (THIS IS A TUESDAY!!!) 