Course Schedule
Click to expand the details of lectures and access the reading material
Week 1: Introduction and Voting
An introduction to the course; course logistics, and overview of the field of social choice and mechanism design.
This topics provides an introduction to social choice theory and voting rules for preference data aggregation. We discuss the non-existence of "prefect" voting rules (Arrow's impossibility theorem) and the non-existence of intuitive but desirable rules that are immune to strategic manipulation (Gibbard-Satterthwaite theorem). A brief discussion of domain restriction (median rule) and complexity of manipulation (Bartholdi, Tovey and Trick condition).
Additional Material
Week 2: Cake Cutting
An introduction to fair allocation of divisible resources (cake cutting). We will discuss fairness concepts such as proportionality and envy-freeness, seminal algorithms that guarantee these fairness properties and go over query a model for elicitation of preference data (the Robertson-Webb model).
Additional Material
Week 3: Fair Division
How should we allocate resources or goods when they are not divisible? We discuss a variety of deterministic relaxations such as envy-freeness up to one item as well as other fairness concepts such as the Maximin Share Guarantee, discuss computational challenges in achieving these properties, and explore their relation to other desirable concepts such as optimality (e.g. Pareto optimality, Nash welfare).
Additional Material
To Divide the Rent, Start With a Triangle [link]
Week 4: Fair Division (Advanced Topics)
More relaxations and allocations of chores.
Week 5: Random Assignment
Can we achieve fairness through randomization? We discuss randomized algorithms for allocating indivisible resources and focus on two seminal mechanisms: Random Serial Dictatorship and the Probabilistic Serial Rule. We also discuss the relation to other deterministic fairness notions such as EF1.
Additional Material
Week 6: Assignment with Endownment
How do we assign resources or goods when they are initially endowed by a collection of agents? We discuss the desirable properties such as individual rationality and the core, and explore an algorithm (Top Trading Cycle) that can uniquely find the more desirable solution for general preferences. We also discuss alternative algorithms in restricted domains and the its relation to randomized mechanisms such as RSD.
Matching under Preferences [link]
Week 7: Matching Markets (I)
How should mutually relationships form when two sides have preferences over one another? We discuss two-sided matching problems, algorithms for ensuring stability of the outcome (the Gale Shapley algorithm) as well as strategic manipulation in two-sided settings.
Additional Material
Week 8: Matching Markets (II) and AI, Ethics, and Philosophy
Discussions on applicable fairness concepts in two-sided matching markets (e.g. Justified Envy-Freeness).
Discussions on AI ethics, philosophical aspects of fairness and algorithmic decision making.
Additional Material
Week 9: Advanced Topics
October 17, 2023 - AI, Ethics, and Philosophy (see above)
October 19, 2023 - Discussions
Additional Material
PageRank: A trillion dollar algorithm (video) [link]
Week 10: Advanced Topics
October 24, 2022 - Paper 1: Three Fast Algorithms for Four Problems in Stable Marriage - Samarth
October 26, 2022 - Paper 2: Learning Strategies in Decentralized Matching Markets under Uncertain Preferences - Duohan
Week 11: Advanced Topics
October 31, 2022 - Paper 3: A Little Charity Guarantees Almost Envy-Freeness - Shraddha
November 2, 2022 - Paper 4: Envy-free allocations respecting social networks - Olivia/Ali
Week 12: Advanced Topics
November 7, 2022 - Dr. Sanjukta Roy: Fractional Matchings under Preferences: Stability and Optimality
November 9, 2022 - Paper 5: Fair algorithms for selecting citizens’ assemblies - Swapnika/Yaqi
Week 13: Advanced Topics
November 14, 2022 - Paper 6: ON MULTIPLE DISCOUNT RATES - Eduard/Min-Feng/Yutaro
November 16, 2022 - Paper 7: How Do Fairness Definitions Fare?: Examining Public Attitudes Towards Algorithmic Definitions of Fairness - Jiyoon/Sasha
Thanksgiving Holiday!
Week 14: Project Presentations
November 28, 2022 - Project Discussions
November 30, 2022 - Duohan / Olivia / Samarth
Week 15: Project Presentations
December 5, 2022 - Yutaro, Min-Feng, Eduard / Swapnika / Shraddha
December 7, 2022 - Sasha, Jiyoon / Ali / Yaqi