TAs: There are three (fantastic!) TAs for the class: Sirui Li (sirui.li), Gwyneth Pearson (gpearson), and Angelica Tao Zhu (angelica.tao). The TAs will hold regular office hours, grade homeworks, and answer questions on Piazza.
The office hour schedule is as follows:
Mondays | 2:00-3:00 (Sanmay, Jolley 512) | Wednesdays | 4:00-6:00 (Gwyneth, Jolley 224) |
Thursdays | 1:00-3:00 (Angelica, Jolley 224) |
Fridays | 4:15-6:15 (Sirui, Jolley 224) |
Date | Topics | Readings | Extras |
Jan 16 | Introduction. Course policies. Course overview. | Lecture notes | |
Jan 18 | The assignment problem. The auction algorithm. | SLB Section 2.3.2 | |
Jan 23 | (Brief) introduction to linear programming and duality. | SLB Appendix B. Chapter 7 of Algorithms (Dasgupta et al). | GNU Linear Programming Kit. We'll post some installation tips on Piazza. |
Jan 25 | LP form of the assignment problem. Two-sided matching. | SLB Section 10.6.4 (through Theorem 10.6.13). The original Gale and Shapley paper | |
Jan 30 | Two-sided matching, contd. Proposer optimality. LP formulation of stable matching. | SLB Section 10.6.4 (through Theorem 10.6.13). | |
Feb 1 | LP formulation of stable matching, contd. Housing with endowments and the Top Trading Cycles algorithm. Intro to preferences. | The first two pages of Stable matchings and linear programming (Vohra, 2012). Incentive compatibility in a market with indivisible goods (Roth, 1982) | |
Feb 6 | No class. Sanmay at AAAI. | HW1 out | |
Feb 8 | Preferences and von Neumann-Morgenstern utilities. | SLB Section 3.1 | |
Feb 13 | Risk-aversion and log utilities. Intro to game theory: Pareto-optimality and strict dominance. | NRTV Sections 1.1-1.3. SLB Section 3.3.1 | |
Feb 15 | Game theory, contd.: Nash equilibrium. | SLB Sections 3.3 and 4.5 (excluding 4.5.2) | |
Feb 20 | Mixed strategy Nash equilibria contd. Congestion games. | NRTV Section 1.3. SLB Sections 3.3.2, 6.4.1 | |
Feb 22 | Congestion games and potential games. Correlated equilibrium. | SLB Sections 6.4.2-6.4.3, NRTV Sections 1.3.6 | |
Feb 27 | Sequential games and subgame perfection. | SLB 5.1, NRTV 1.5 | |
Mar 1 | Games of imperfect information. Sequential equilibrium. | SLB 5.2.1, 5.2.2, 5.2.4. Game trees from lecture (from David Kreps' book) | HW2 out |
Mar 6 | Games of incomplete information. Bayes-Nash equilibrium. | SLB 6.3. | |
Mar 8 | Bayes Nash equilibrium continued. Analyzing first-price auctions as Bayesian games. | Easley and Kleinberg, Chapter 9 (especially 9.7) | |
Mar 20 | Computing equilibria in 2-player zero-sum games. General sum games and linear complementarity problems | SLB 3.4.1, 4.1, 4.2.1, 4.2.2 | |
Mar 22 | Ben-Gurion's Tri-Lemma | Paper by James Stodder | |
Mar 27 | Midterm review | ||
Mar 29 | Midterm | ||
Apr 3 | Midterm discussion. Intro to social choice theory | SLB 4.1, 4.2.1, 4.2.2. NRTV 9.1 and 9.2. SLB 9.1-9.3 | |
Apr 5 | Arrow's impossibility theorem. Single-peaked preferences and the median voter theorem. | Third proof in Geanakoplos' paper. NRTV 10.1 and 10.2. | |
Apr 10 | The Gibbard-Satterthwaite theorem. Mechanism design and VCG mechanisms. | SLB 9.4. NRTV 9.2-9.3 | |
Apr 12 | VCG mechanisms. | NRTV 9.3 | HW3 out |
Apr 17 | Guest lecture by Peter Hovmand on Prevention and Systems | See Piazza for link to slides | |
Apr 19 | Mechanism design, contd. Sponsored search. | Edelman, Ostrovsky, and Schwartz (2007) | |
Apr 26 | Final Jeopardy! |