Lect# Title & Link Date Extra Reading
0 Course intro: course smorgasbord Sep. 10
1 Intro to Nash equilibrium Sep. 15 Nisan et al. Chapter 1, Dixit & Skeath Chapter 4
2 Nash Equilibria: existence vs. computability Sep. 17 Dixit & Skeath Chapter 5 for mixed nash equilibria, and here's a nice survey on the PPAD completeness of computing Nash equilibria
3 Fair Division: Cutting a cake Sep. 22 I think chapter 8 here is quite good. Honestly I'd consider all sections relevant, but the protocols we covered came mostly pre-section 8.4. The first few sections are mostly dedicated to definitions of 'fairness', before it even starts describing a single protocol.
4 Fair Division: Cutting a cake is actually quite hard Sep. 24 Stromquist's paper
5 Fair Division: Indivisible Items and a Little Background on Hardness Sep. 29 Chapter 9 from last week's text is reasonable start - but only section 9.4 - 9.6 I'd say. Then I'd move over to chapter 34 of CLRS. Maybe just the first couple sections, and then finish after Thursday.
6 More on NP-Completeness Oct. 1 Finish chapter 34 of CLRS.
7 Approximation Algorithms for Knapsack Oct. 6 CLRS has a nice FPTAS for SubsetSum. If you want to get a headstart for Thursday, here's the paper that we'll be proving the main result from.
8 A 2/3-MMS protocol for indivisible goods Oct. 8 There isn't a much better resource than the actual paper. The protocol we did is from section 3.
9 Introduction to Mechanism Design: VCG Mechanisms Oct. 15 So the Nisan et al. book on our homepage actually handles this pretty well. Specifically sections 9.4 and 9.5 were the focus of today's lecture. A lot of the book is kinda hard to read, which is why I haven't been linking it so much this semester, but we'll definitely use this chapter this week and when we cover elections after the midterm.
10 Combinatorial Auctions Oct. 20 Today's lecture came from a bunch of places:
  • The NP-Hardness of maximizing social welfare and the 2-approximation: sections 5.2, 5.3, and 5.4
  • The Incentive Compatible sqrt(m)-Approximation: section 5
  • Although I didn't explicitly use it today, chapter 11 of the Nisan et al. text is an excellent survey:
11 Review Oct. 22
12 Elections Oct. 27 Today's Lecture covered:
13 Arrow's Theorem Oct. 29 My proof basically follows section 9.2 of Nisan et al.'s book, which also has the proof of Gibbard-Satterthwaite if my hints are insufficient.
14 Domain Restriction Nov. 3 I got most of today's lecture from chapters 1 - 3 (we only got through the first couple sections of chapter 3) of this survey.
15 Distortion Nov. 5 This survey inspired this lecture. I got the randomized results from this paper.
16 Stable Marriage (Gale-Shapley) Nov. 10

Most of today's lecture came from this book, specifically part 1 chapters 1 and 3 (chapter 3 relies on some small parts of chapter 2).

However, I highly recommend all my students read the original paper. It's quite well written. If you read nothing else from it though, read the last two paragraphs. It's an interesting take, though the last paragraph I think is an incredibly bad take.

17 Stable Roommates? Nov. 12 Most of today's lecture came from every snippet I could find about Irving's original algorithm. However, while looking again during 375's exam on the same night, I finally found the original paper hiding on some professor's website who seems to have not noticed that he's ignoring copyright rules. I think it would probably be unethical for me to do the same, but I'll say that the title of the paper is An Efficient Algorithm for the “Stable Roommates” Problem and Google Scholar will often just give you links to pdfs if it can find them. Anyway, the original paper seems to be a good resource to look through.
18 Min Cost Matching: The Assignment Problem and the Hungarian Algorithm Nov. 17
19 Online matching Nov. 19
19 Dynamic Pricing for Online Matching Dec. 1