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  TwoPerson ZeroSum Games The Minimax Theorem Understanding Multipeople GeneralSum Games 
Note 2  Andersen and Feige on Application of Zerosum 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 PLSCompleteness 
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 PLScompleteness of Unsplittable Selfish Routing. See Roughgarden's Lecture Note for a more elaborated discussion. 

20 November, 2017 
LemkeHowson Algorithm for Computing Nash Equilibrium of TwoPlayer Generalsum 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 LemkeHowson Solutions (FOCS 2011, ACM TEAC 2013) 

27 November, 2017 
Multiplicative Weight (MW) Algorithm MW in TwoPerson ZeroSum 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: NearOptimal NoRegret Algorithms for Zerosum 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 MetaAlgorithm and Applications (Theory of Computing 2012) CesaBianchi, Lugosi: Prediction, Learning and Games (Cambridge University Press 2006) 

4 December, 2017 
Fisher Markets, ArrowDebreu 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 Polytime 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 ArrowDebreu Markets (by Bhaskar)  Note 8  Duan, Mehlhorn: A Combinatorial Polynomial Algorithm for the Linear ArrowDebreu Market (ICALP 2013, Inf. Computation 2015)  
9 January, 2018  Network Flow Algorithms for Linear ArrowDebreu 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 NearOptimal 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: Strategyproof 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) 