|Games, Equilibria, and Computation|
|Tue, Aug 28 || Course overview. Two-player games. Zero-sum, min-max = LP duality.
|| Overview slides and notes. Notes by Prof. Costis Daskalakis on Two-player games, Zero-sum games, min-max = LP duality.
|Thu, Aug 30 || Nash Eq. in bimatrix games, Characterization, enumeration, existence, reduction to symmetric game.
|| My hand-written notes. Notes by Prof. Costis Daskalakis on Two-player games.
|Tue, Sept 4 ||Cancelled|
|Thu, Sept 6|| Nash, Brouwer, Sperner; Class PPAD, and other TFNP classes.
|Tue, Sept 11|| Other equilibrium (dominant strategy, (coarse) correlated, stackelberg) and game (extensive form, Bayesian) notions.
||For Eq. notions see Slides. |
|Thu, Sept 13|| Security games and stackelberg equilibria. Nash bargaining
||For material covered on security games, see Paper, Sections 3, Section 4 (only page 9), and Section 5 (before Lemma 5.2). |
For Nash bargaining see Slides 6-15 by Prof. Asu Ozdaglar, and also Section 8.2 (Chapter 8) of book Game Theory by Roger Myerson.
|Tue, Sept 18|| Mechanism design w/o money -- top trading cycle. kidney exchange. stable matching.||Notes by Prof. Tim Roughgarden. Notes by Widmayer and Dutting|
|Thu, Sept 20||Voting ||Notes by Widmayer and Dutting. Notes by Tim|
|Tue, Sept 25||Single item auctions -- First and second price||Notes by Tim.|
|Thu, Sept 27||Single parameter auction. Myerson's Lemma||Notes by Tim.|
|Tue, Oct 2||Auction design to Algorithm design, Indirect Mechanism, Revelation Principle||Notes by Tim.|
|Thu, Oct 4||Myerson's Optimal (Revenue maximizing) Auction, Bulow-Klemperer Theorem||Notes1 and Notes2 by Tim.|
|Tue, Oct 9||Prophet Inequality, VCG, Combinatorial Auctions||Prophet Inequality, VCG+Comb. Auction by Tim|
|Thu, Oct 11||Implementability of Comb. Auction||KC Auction, VCG+Walrasian Equilibrium by Tim|
|Tue, Oct 16||VCG properties, Spectrum Auction||Notes1, Notes2 by Tim|
|Selfish Routing, Congestion Games, Potential Games||Thu, Oct 18||Selfish-Routing and Price of Anarchy
||Notes by Tim
|Tue, Oct 23||Network Over-Provisioning and Non-Atomic Routing||Notes by Tim.|
|Thu, Oct 25||Congestion games, Potential Games, Equilibrium Existence and Complexity of Computation.
||First part of Tim's Notes on Potential games. Slides by Prof. Apt on Congestion to Potential game reduction. Notes by Prof. Kesselheim on complexity of computing NE in congestion games.|
|Tue, Oct 30||(i) Smooth Games. (ii)Cost Sharing Games||Notes by Tim on (i); this also includes smoothness proof for Location Games where players want to maximize payoff. Notes by Tim on (ii).|
|Thu, Nov 1||No Lecture|
|Tue, Nov 6|| (i) Best Response Dynamics. (ii) No Regret Dynamics (discussed briefly). || Notes1 on (i), and Notes2 on (ii) by Tim. |
|Thu, Nov 8|| More on No-Regret Dynamics. || Notes by Tim. Notes on Swap-Regret by Tim. |
|Tue, Nov 13|| Fair division: Divisible goods || Section 1,2,3 except 3.2 from Notes by Endriss.|
|Thu, Nov 15|| Fair division: Indivisible goods. EF1, MMS, egalitarian, utilitarian, NSW || For EF1, Section 2 of paper 1 and Section 3 of paper 2. For MMS, Section 3 of paper 3. For the remaining, Sections 3 and 4 of paper 4, and Section 4.2 of paper 5 |