A graduate course in Theoretical Computer Science
MIMUW, University of Warsaw · Nidhi Rathi
90-minute lectures, followed by 90-minute tutorials.
Credits: 6 ECTS
Assessment: Two exams, each worth 50% of the final grade.
Fair Division is a fundamental area at the intersection of algorithm design, game theory, and economics, that studies the problem of allocating resources among agents in a fair and efficient manner.
The modern mathematical study of fair division was pioneered in the 1940s by Hugo Steinhaus, Bronisław Knaster, and Stefan Banach. The course introduces the mathematical and algorithmic foundations of fair division, covering both classical results and recent developments. Applications range from dividing goods and assinging tasks to modern problems such as allocating computational resources, matching markets, and online platforms.
We will study key allocation models, precise notions of fairness and efficiency, and techniques from theoretical computer science for designing and analysing allocation algorithms. Alongside constructive methods, the course will emphasize existence theorems and their proofs, examining when fair allocations exist and how they can be computed. Particular attention will be paid to the relationships and trade-offs between fairness, efficiency, and computation, including the role of welfare objectives such as Nash social welfare.
The course aims to provide a working understanding of key models and solution concepts, along with the ability to rigorously analyze and design fair and efficient allocation algorithms.
Materials will be added each week. The list of topics is tentative and may be adjusted during the semester.
01 · Introduction to Fair Cake Division · Lecture 01 · Tutorial 01
02 · Sperner's Lemma and envy-free cake division · Lecture 02 · Tutorial 02
03 · Equitability and Approximate EF · Lecture 03 · Tutorial 03
04 · Necklace Splitting using Borsuk-Ulam theorem · Lecture 04 · Tutorial 04
05 · Introduction to Fair Rent Division · Lecture 05 · Tutorial 05
06 · Introduction to Discrete Fair Division · Lecture 06 · Tutorial 06
07 · 1/2-EFX and EFX with Charity · Lecture 07 · Tutorial 07
First exam on November 23 from 2 - 4 pm
08 · Fair Division and Market Equilibrium · Lecture forthcoming · Tutorial forthcoming
09 · Discrete chores setting · Lecture forthcoming · Tutorial forthcoming
10 · Fair Division with charity · Lecture forthcoming · Tutorial forthcoming
11 · Discrete chores setting · Lecture forthcoming · Tutorial forthcoming
12 · New Fairness Notions for Discrete Fair Division · Lecture forthcoming · Tutorial forthcoming
13 · Best-of-both-worlds · Lecture forthcoming · Tutorial forthcoming
Nidhi Rathi · n.rathi@uw.edu.pl · Personal website
Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia (eds.). Handbook of Computational Social Choice. Cambridge University Press, 2016. ISBN: 9781107446984.
Hervé Moulin. Fair Division and Collective Welfare. MIT Press, 2003. ISBN: 9780262280297.
Additionally, the lectures will cover recent work published in journals and conference proceedings. See the following survey:
Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, Volume 322, Article 103965, Elsevier, 2023.