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 · Introduction to Discrete Fair Division · Lecture forthcoming · Tutorial forthcoming
03 · Sperner's Lemma and fair cake-cutting · Lecture forthcoming · Tutorial forthcoming
04 · Introduction to Rent division · Lecture forthcoming · Tutorial forthcoming
05 · Fair Division and Efficiency · Lecture forthcoming · Tutorial forthcoming
06 · Discrete chores setting · Lecture forthcoming · Tutorial forthcoming
07 · Fair Division and Market Equilibrium · Lecture forthcoming · Tutorial forthcoming
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 · Discrete chores setting · Lecture forthcoming · Tutorial forthcoming
13 · Best-of-both-worlds · Lecture forthcoming · Tutorial forthcoming
14 · New Fairness Notions for Discrete Fair Division · 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.