Lectures on
Fair Division

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.

Lectures

1. 01
   12.10.

   Introduction to Fair Division · Cake Cutting

   Fair division, cake cutting, moving-knife procedures, and the Robertson–Webb model.
   Slides Lecture notes
2. 02
   19.10.

   Envy-free Cake Cutting · Sperner’s Lemma

   Selfridge–Conway, query complexity of envy-freeness, Sperner’s lemma, and envy-free divisions with contiguous pieces for any number of agents.
   Slides Lecture notes

Acknowledgements

Some of the lecture notes and slides are based on lecture notes by Masoud Seddighin and lecture slides by Nidhi Rathi.

Contact