All lectures will be recorded. Recordings will be available on Echo360.
Date | Topics | Reading |
---|---|---|
Markets and Fair-division | ||
Tue, Aug 24, 2020 | No lecture due to ADFOCS 2020 | |
Thu, Aug 28, 2020 | Course overview. Competitive equilibrium (CE) | Course overview slides and CE slides. For notes on CE, see Chapter 5 of the Algorithmic Game Theory book. |
Tue, Sept 1, 2020 | Competitive equilibrium and Properties | CE slides. For notes on CE, see Chapter 5 of the Algorithmic Game Theory book. |
Thu, Sept 3, 2020 | Computation of Competitive equilibrium | Slides. See Sections 2, 3, 4, 5 of the DPSV08 paper for CE algorithm. |
Tue, Sept 8, 2020 | Hylland-Zeckhauser. Fair division w/ indivisible items: EF1, EFX | Slides. See Section 4 of VY20 for the HZ equilibrium algorithm. |
Thu, Sept 10, 2020 | Fair division w/ indivisible items: MMS, Prop1 | Slides |
Tue, Sept 15, 2020 | Fair division w/ indivisible items: MMS, MNW | Slides |
Thu, Sept 17, 2020 | Fair division w/ indivisible items: Maximizing Nash welfare | Slides |
Games and Equilibria | ||
Tue, Sept 22, 2020 | Two-player games and Nash equilibrium | Slides |
Thu, Sept 24, 2020 | Nash equilibrium computation | Scribbles |
Tue, Sept 29, 2020 | Nash, Brouwer, Sperner, and TFNP classes | Slides |
Thu, Oct 1, 2020 | Game models and other equilibrium notions | Slides |
Tue, Oct 6, 2020 | Bayesian games and Security games | For Bayesian games see Slides (slides 33-38). For security games see Scribbles, and Paper, Sections 3, Section 4 (only page 9), and Section 5 (before Lemma 5.2). |
Thu, Oct 8, 2020 | Security game (contd.). Selfish-Routing and Price of Anarchy | Notes by Prof. Tim Roughgarden. Lecture scribbles |
Selfish Routing, Congestion Games, Potential Games | ||
Tue, Oct 13, 2020 | Non-Atomic Selfish-Routing, N/w Over Provisioning | Notes1 and notes2 by Tim. Lecture scribbles |
Thu, Oct 15, 2020 | Atomic Selfish Routing, Potential Games, Smooth Games | Notes on atomic selfish routing, see section 1 of notes for Potential games, and notes on smooth games by Tim; this also includes smoothness proof for Location Games where players want to maximize payoff. Lecture scribbles |
Tue, Oct 20, 2020 | Cost Sharing Games | Notes by Tim on Cost-sharing games. Lecture scribbles |
Thu, Oct 22, 2020 | Best Response Dynamics and the Rate of Convergence | Notes by Tim on Cost-sharing games. Lecture scribbles |
Mechanism Design | ||
Tue, Oct 27, 2020 | Single item auctions -- First and second price | Notes by Tim. Lecture scribbles |
Thu, Oct 29, 2020 | Single parameter auction. Myerson's Lemma | Notes by Tim. Lecture scribbles |
Thu, Nov 5, 2020 | Cancelled | |
Tue, Nov 10, 2020 | VCG, Auction design to Algorithm design, Indirect Mechanism, Revelation Principle | On VCG, and notes on the rest by Tim. Lecture scribbles |
Thu, Nov 12, 2020 | Myerson's Optimal (Revenue maximizing) Auction, Bulow-Klemperer Theorem | Notes1 and Notes2 by Tim. Lecture scribbles |
Tue, Nov 17, 2020 | Case Study on Spectrum Auction | Spectrum Auc by Tim. Lecture scribbles |
Date | Topics | Reading |
---|---|---|
Mechanism Design | ||
Mechanism design w/o money -- top trading cycle. kidney exchange. stable matching. | Notes by Prof. Tim Roughgarden. Notes by Widmayer and Dutting | |
Prophet Inequality, Combinatorial Auctions | Prophet Inequality notes due to Tim, and Slides due to Brendan. Comb. Auction by Tim | |
Implementability of Comb. Auction | KC Auction by Tim | |
Walrasian Equilibrium | VCG+Walrasian Equilibrium by Tim | |
Selfish Routing, Congestion Games, Potential Games | ||
No-Regret Dynamics. | Notes by Tim. | |
Fair-division | ||
Markets | ||
 | Market: Fisher, Equilibrium | Notes by Prof. Mansor. AGT book Chapter 5, Sections 1 and 3 |
 | Eisenberg-Gale Convex Formulation, Kelly's resource allocation problem -- fair solution | AGT book Chapter 5, Sections 5.1-5.3, Section 13. Chapter 6, section 6.2. More notes will be posted. |
 | Exchange Model: Existence, Convex formulation and auction based approximation algorithm for the Linear utilities case. | AGT book Chapter 5, Sections 5.11, 5.12, Chapter 6, Section 6.1.1. Chapter 3 (Section 3.3) of Notes by Prof. Bisin. |
 | Market: Discrete-goods, Strategization | Slides. Sections 2, 3.2 and 4.1 of this paper. |
 | (market equilibrium) Fisher markets, Eisenberg-Gale convex formulation, an overview of Devanur-Papadimitriou-Saberi-Vazirani (DPSV) algorithm. Arrow-Debreu market, PPAD-hardness, Lemke’s algorithm. |  |