**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 . Lecture scribblesmaximize payoff |

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. | Â |