All lectures will be recorded. Recordings will be available on Mediaspace.
Date | Topics | Reading |
---|---|---|
Fair-division, Social Choice (some of the covered topics are relatively new) | ||
Tue, Aug 23, 2022 | Introduction. Course overview. | Slides |
Thu, Aug 25, 2022 | Fair-division of Divisible Goods | Slides See also sections 10.1 and 10.2 of Yishay Mansour's notes. Note here that B_i is the budget that we assumed to be 1, and ρ is also 1 when valuations are linear. |
Tue, Aug 30, 2022 | Fair-division of Indivisible Goods - EF1 and Prop1 | Slides |
Thu, Sep 1 2022 | Fair-division of Indivisible Goods - MMS | Slides |
Tue, Sep 6 2022 | Stable Matching, House Allocation, Kidney Exchange | Lecture scribbles. Notes1 and Notes2 by Tim Roughgarden. Notes by Widmayer and Dutting |
Thu, Sep 8 2022 | Arrow's Impossibility Theorem | Notes.Slides by Kevin-Leyton Brown. |
Mechanism Design | ||
Tue, Sept 13, 2022 | Single Item Auction-- First and Second Price | Slides on equilibrium notions. Scribbles on single item auction. Notes by Tim. |
Sept 15, 2022 | Single parameter auction. Myerson's Lemma | Notes by Tim. Lecture scribbles |
Sept 20, 2022 | VCG, Auction design to Algorithm design, Indirect Mechanism, Revelation Principle | Lecture scribbles |
Sept 22, 2022 | Myerson's optimal (revenue maximizing) auction | Lecture scribbles |
Sept 27, 2022 | Simple vs Optimal Auctions: Bulow-Klemperer's Theorem and Prophet Inequality | Lecture notes and scribbles. Notes by Tim. Slides by Brendan. |
Sept 29, 2022 | Prophet Inequality: Variants and Extensions | Lecture notes and scribbles. Sahil's, Michal's and Thomas's slides. |
Oct 4, 2022 | Case Study on Spectrum Auction | Spectrum Auc by Tim. Lecture scribbles. |
Games and Equilibria | ||
Oct 6, 2022 | Two-player games and Nash equilibrium, zero-sum, minmax = LP duality | Slides |
Oct 13, 2022 | Nash, Brouwer, Lemke-Howson algorithm, Sperner, and TFNP classes | Slides |
Oct 18, 2022 | Game models and other equilibrium notions | Slides |
Oct 20, 2022 | Stackelberg equilibrium and Nash Bargaining | Lecture scribbles. Also see slides by Asu Ozdaglar on Nash bargaining |
Routing+Costsharing Games and Price-of-Anarchy | ||
Oct 25, 2022 | Non-Atomic Selfish Routing | Notes by Tim. Lecture scribbles |
Oct 27, 2022 | N/W Over Provisioning, Atomic Selfish Routing | Notes by Tim. Lecture scribbles |
Nov 1, 2022 | Potential Games and Smoothed Games | 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 |
Nov 3, 2022 | Cost Sharing Games | Notes by Tim on Cost-sharing games. Lecture scribbles |
No class - Election Day | Please Go Vote! | |
Nov 10, 2022 | No-regret Dynamics | Tim's notes on best-response dynamics notes on no-regret dynamics, and notes on on-swap-regret. Lecture scribbles |
Project Presentations | ||
Nov 15, 2022 | Project Presentations | |
Nov 17, 2022 | Project Presentations | |
Nov 29, 2022 | Project Presentations | |
Dec 1, 2022 | Project Presentations | |
Dec 6, 2022 | Project Presentations |
Roth et al. (2004) also extend the TTC algorithm and its incentive guarantee to accommodate both deceased donors (houses without owners) and patients without a living donor (agents without houses). The application of graph matching to pairwise kidney exchange is from Roth et al. (2005), Roth et al. (2007) consider three way kidney exchanges, with simultaneous surgeries on three donors and three patients. Three-way exchanges can significantly increase the number of matched patients, and for this reason are becoming common. Allowing four-way and larger exchanges does not seem to lead to significant further improvements.