Instructor: Paul Gölz
Meetings: Tue/Thu 11:40 a.m.–12:55 p.m.
Location: Rhodes 261 / Bloomberg 165 (Cornell Tech)
Office Hours: Mon/Wed 5:00–6:00 p.m. in Rhodes 221
Links: Canvas, Ed Discussion
Fair Allocation: The theory of private goods (i.e., each good only benefits one person, must decide who should get it).
Social Choice: The theory of voting and public goods (i.e., selected goods affect everyone).
In (almost) each session, we discuss one paper in depth, with a focus on technical content and the paper itself. This course will:
The format of this course is adapted from Role-Playing Paper-Reading Seminars by Alec Jacobson and Colin Raffel. Students will be assigned roles for each paper discussion.
Students will be a Reader roughly once per week and another role about once per week.
Subject to change. Papers available on Canvas.
| # | Date | Paper | Instructor topic |
|---|---|---|---|
| 1 | Tue Aug 26 | LECTURE: Overview and Format | |
| 2 | Thu Aug 28 | LECTURE: Fair Division: Envy-free and Pareto optimal allocations for divisible goods | |
| 3 | Tue Sep 02 | Su (1999): Rental Harmony: Sperner's Lemma in Fair Division (paper link) | Sperner’s lemma |
| 4 | Thu Sep 04 | Caragiannis et al. (2019): The Unreasonable Fairness of Maximum Nash Welfare (paper link) | Cardinal welfarism |
| 5 | Tue Sep 09 | Barman et al. (2018): Finding Fair and Efficient Allocations (paper link) | Fractional Pareto optimality |
| 6 | Thu Sep 11 | Bogomolnaia et al. (2017): Dividing goods or bads under additive utilities (paper link) | Relational axioms |
| 7 | Tue Sep 16 | Bogomolnaia and Moulin (2001): A New Solution to the Random Assignment Problem (paper link) | Stochastic dominance |
| 8 | Thu Sep 18 | Aziz et al. (2024): Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation (paper link) | Birkhoff–von Neumann theorem |
| 9 | Tue Sep 23 | Nisan and Ronen (2001): Algorithmic Mechanism Design (paper link) | VCG mechanism |
| 10 | Thu Sep 25 | Amanatidis et al. (2024): Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness (paper link) | Nash equilibria |
| 11 | Tue Sep 30 | Bansal and Sviridenko (2006): The Santa Claus Problem (paper link) | Relax-and-round, integrality gap |
| 12 | Thu Oct 02 | Benadè et al. (2023): Fair and Efficient Online Allocations (paper link) | Adversary models in online algorithms |
| 13 | Tue Oct 07 | Roth (1982): The Economics of Matching: Stability and Incentives (paper link) | Structure of stable matchings |
| 14 | Thu Oct 09 | LECTURE: Fair division recap & discussion | |
| Tue Oct 14 | 🍂 Fall break | ||
| 15 | Thu Oct 16 | LECTURE: Social Choice: Voting rules and May’s theorem | |
| 16 | Tue Oct 21 | Arrow (1950): A Difficulty in the Concept of Social Welfare (paper link) | Axiomatic method |
| 17 | Thu Oct 23 | Brandt et al. (2017): Optimal Bounds for the No-Show Paradox via SAT Solving (paper link) | Finding impossibilities with ILP |
| 18 | Tue Oct 28 | Gibbard (1977): Manipulation of Schemes that Mix Voting with Chance (paper link) | Randomized voting rules |
| 19 | Thu Oct 30 | Conitzer and Sandholm (2005): Common Voting Rules as Maximum Likelihood Estimators (paper link) | Maximum likelihood estimation |
| 20 | Tue Nov 04 | Anshelevich et al. (2015): Approximating Optimal Social Choice under Metric Preferences (paper link) | Utilitarian distortion |
| 21 | Thu Nov 06 | Gölz et al. (2025): Distortion of AI alignment (paper link) | Random utility models |
| 22 | Tue Nov 11 | Aziz et al. (2017): Justified Representation in Approval-Based Committee Voting (paper link) | Proportionality axioms for committee elections |
| 23 | Thu Nov 13 | Fain et al. (2016): The Core of the Participatory Budgeting Problem (paper link) | Lindahl equilibrium |
| 24 | Tue Nov 18 | Munagala et al. (2022): Approximate Core for Committee Selection via Multilinear Extension and Market Clearing (paper link) | Submodular functions and continuous extensions |
| 25 | Thu Nov 20 | Xia (2020): The Smoothed Possibility of Social Choice (paper link) | Smoothed analysis |
| 26 | Tue Nov 25 | TBA | |
| Thu Nov 27 | 🥧 Thanksgiving break | ||
| 27 | Tue Dec 02 | TBA | |
| 28 | Thu Dec 04 | Project presentation |
Subject to change.
Overall: 70% in-class participation, 30% project.