All lectures will be recorded. Recordings will be available on Echo360.
Date | Topics | Reading |
---|---|---|
Fair-division (covered topics are relatively new) | ||
Tue, Aug 24, 2021 | Course overview. Fair-division. | Course overview slides and fair-division (first few slides) |
Thurs, Aug 26, 2021 | Fair-division: Envy-free | Slides |
Tue, Aug 31, 2021 | Fair division w/ indivisible items: Prop1, MMS | Slides |
Thurs Sep 2, 2021 | Fair division w/ indivisible items: MMS (Cont...), NSW | Slides |
Tue Sep 7, 2021 | Fair division w/ indivisible items: Max Nash Social Welfare (Cont.) | Slides |
Thu Sep 9, 2021 | Stable Matching, House Allocation, Kidney Exchange | Lecture scribbles. Notes1 and Notes2 by Tim Roughgarden. Notes by Widmayer and Dutting |
Games and Equilibria | ||
Tue, Sept 14, 2021 | Two-player games and Nash equilibrium | Slides |
Thu, Sept 16, 2021 | Nash equilibrium: Existence and Computation | Slides |
Tue, Sept 21, 2021 | Nash, Brouwer, Sperner, and TFNP classes | Slides |
Thu, Sept 23, 2021 | Game models and other equilibrium notions | Slides |
Tue, Sept 28, 2021 | Stackelberg equilibrium and Security games | For Stackelberg equilibrium see Slides. For security games see Scribbles, and Paper, Sections 3, Section 4 (only page 9), and Section 5 (before Lemma 5.2). |
Thu, Sept 30, 2021 | Bayesian Games, Nash Bargaining | For Bayesian games see Slides. For Nash Bargaining see lecture Scribbles, and Asu Ozdaglar Slides. |
Mechanism Design | ||
Tue, Oct 5, 2021 | Cancelled | |
Thu, Oct 7, 2021 | Single item auctions -- First and second price | Notes by Tim. Lecture scribbles |
Tue, Oct 12, 2021 | Single parameter auction. Myerson's Lemma | Notes by Tim. Lecture scribbles |
Thu, Oct 14, 2021 | VCG, Auction design to Algorithm design, Indirect Mechanism, Revelation Principle | On VCG, and notes on the rest by Tim. Lecture scribbles |
Tue, Oct 19, 2021 | Myerson's optimal (revenue maximizing) auction, Bulow-Klemperer theorem | Notes1 and Notes2 by Tim. Lecture scribbles |
Thu, Oct 21, 2021 | Prophet Inequality and Simple Auctions | Prophet Inequality notes due to Tim, and Slides due to Brendan. |
Tue, Oct 26, 2021 | Case Study on Spectrum Auction | Spectrum Auc by Tim. Lecture scribbles |
Thu, Oct 28, 2021 | Spectrum Reverse Auction and Routing games | Spectrum Auc by Tim. Notes on routing games by Tim. Lecture scribbles |
Routing+Costsharing Games and Price-of-Anarchy | ||
Tue, Nov 2, 2020 | Non-Atomic Selfish-Routing, N/w Over Provisioning | Notes1 and notes2 by Tim. Lecture scribbles |
Thu, Nov 4, 2021 | 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, Nov 9, 2020 | Cost Sharing Games | Notes by Tim on Cost-sharing games. Lecture scribbles |
Thu, Nov 11, 2020 | No-regret Dynamics | Notes1 and notes2 by Tim. Lecture scribbles |
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.
Topics | Reading (coming up soon) |
---|---|
Stable Matching | |
Mechanism Design | |
Voting - Arrow's theorem | |
Single item auction: first and second price | |
Single parameter auction, Myerson's lemma | |
VCG, Auction design to algorithm design, Indirect mechanism, Revelation principle | |
Myerson's optimal (revenue maximizing) auction, Bulow-Klemperer theorem | |
Prophet inequality, Combinatorial auctions | |
Case study on Spectrum auctions | |
Games and Equlibria | |
Two player games, zero-sum, minmax = LP duality | |
Nash equlibria in bimatrix games: characterization, enumeration, existence, reduction to symmetric games | |
Lemke-Howson algorithm, Sperner | |
Class PPAD and other TFNP classes, iterated dominance and correlated equilibrium | |
Other equilibrium (coarse correlated, Stackelberg) and game (extensive form and Bayesian) notions | |
Security games and Stackelberg equilibria, Nash bargaining | |
Public good games | |
Price of Anarchy: Selfish Routing, Congestion Games, Potential games | |
Selfish routing and Price-of-Anarchy | |
Network over-provisioning and Non-atomic routing | |
Smooth games | |
Congestion games, potential games, equilibrium existence and complexity of computation, cost sharing games | |
Best response dynamics | |
No-regret dynamics | |
Markets | |
Market: Fisher, competitive equilibrium | |
Computation of competitive equilibrium | |
Hylland-Zeckhauser, Spending restricted models | |
Connections to fair division |