Oral exam
Written exam if more than 10 students register
Course Description
Fair Division is a fundamental area at the intersection of algorithm design, game theory, and economics, concerned with allocating resources among agents in a way that is fair and efficient. Applications range from dividing goods and tasks to modern problems such as allocating computational resources, matching markets, and online platforms.
This course introduces the mathematical and algorithmic foundations of fair division, covering both classical results and recent developments. Emphasis will be placed on precise fairness notions and algorithmic techniques for achieving fair outcomes under various constraints. In addition, the course will highlight existential results, including proofs of the existence of fair allocations under various models, and their relationship to constructive (algorithmic) methods and efficiency guarantees such as Nash social welfare.
The course aims to provide a working understanding of key models and solution concepts, along with the ability to analyze and design fair and efficient allocation algorithms.
Tentative Topics
- Classical cake-cutting protocols, including proportionality and envy-freeness
- Indivisible goods and fairness notions: EF, EF1, EFX, and MMS
- Efficiency concepts: Pareto efficiency and social welfare measures, in particular Nash social welfare
- Trade-offs between fairness and efficiency
- Approximation algorithms and computational complexity of fair division
- Market-based approaches: Fisher markets and competitive equilibria
- Fair division with strategic agents and mechanism-design aspects
- Randomized and probabilistic allocation methods
- Recent advances and open problems in fair division