Date | Topics | Reading |
---|---|---|

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

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

Mechanism Design | ||

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

Fair Division | ||

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 |

Note on this by Tim in his book

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.

Date | Topics | Reading |
---|---|---|

Lemke-Howson (path-following) algorithm to find a Nash equilibrium | Slides from a previous course. AGT book by Nisan, Roughgarden, Tardos, and Vazirani, sections 2.1-2.4, 3.1-3.6 | |

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