Embedded Files
Click to expand the details of lectures and access the reading material
Click to expand the details of lectures and access the reading material
Week 1: Introduction and Voting
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
Additional Material
Week 2: Cake Cutting
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
Additional Material
Week 3: Fair Division
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
Additional Material
To Divide the Rent, Start With a Triangle [link]
Week 4: Fair Division (Advanced Topics)
Week 4: Fair Division (Advanced Topics)
More relaxations and allocations of chores.
Week 5: Random Assignment
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
Additional Material
Week 6: Assignment with Endownment
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)
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
Additional Material
Week 8: Matching Markets (II) and AI, Ethics, and Philosophy
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
Additional Material
Week 9: Advanced Topics
Week 9: Advanced Topics
October 18, 2022 - Dr. Tomasz Wąs: Axiomatization of PageRank
October 20, 2022 - Paper 1: Approximating Maximin Share Allocations - Medha
Additional Material
Additional Material
PageRank: A trillion dollar algorithm (video) [link]
Week 10: Advanced Topics
Week 10: Advanced Topics
October 25, 2022 - Discussions
October 27, 2022 - Paper 2: Surprisingly Popular Voting Recovers Rankings, Surprisingly! - Yimu/Prottay
Week 11: Advanced Topics
Week 11: Advanced Topics
November 1, 2022 - Dr. Sanjukta Roy: Fractional Matchings under Preferences: Stability and Optimality
November 3, 2022 - Paper 3: Efficient, Fair, and Incentive-Compatible Healthcare Rationing - Sumit/Amrit
Week 12: Advanced Topics
Week 12: Advanced Topics
November 8, 2022 - Paper 4: Fair Procedures with Naive Agents: Who Wants the Boston Mechanism? - Yubo/Tianqing
November 10, 2022 - Paper 5: Manipulating Gale-Shapley Algorithm: Preserving Stability and Remaining Inconspicuous - Ronak/Tatheer
Week 13: Advanced Topics
Week 13: Advanced Topics
November 15, 2022 - Paper 6: Fair algorithms for selecting citizens’ assemblies - Leah/Raj/Ritik
November 17, 2022 - Paper 7: Which Is the Fairest (Rent Division) of Them All? - Denesh/Yalda
Thanksgiving Holiday!
Thanksgiving Holiday!
Week 14: Project Presentations
Week 14: Project Presentations
November 29, 2022 - AI, Ethics, and Philosophy (see above)
December 1, 2022 - T1: Yubo/Yimu; T6: Ritik/Sumit/Raj; T2: Amrit
Week 15: Project Presentations
Week 15: Project Presentations
December 6, 2022 - T5: Ronak; T3: Yalda/Leah/Denesh; T8: Tianqin
December 8, 2022 - T7: Prottay/Tatheer; T4: Medha
December 14th: Final Projects
December 14th: Final Projects
Page updated
Google Sites
Report abuse