Matchings and Fair Division (MFD)

Course Description 

The course consists of two main modules.

• Matching under Preferences: House allocation, both with and without endowments; popular and rank-maximal matchings in one-sided settings; the lattice structure of stable matchings; the Rural Hospitals Theorem; stable matchings with ties (weak preferences); popular matchings in two-sided settings; and related topics.

• Fair Division: a brief introduction to cake-cutting, followed by the indivisible-goods setting, where we study fairness notions such as EF1, PROP1, EFX, and MMS, together with the algorithms, theoretical guarantees, and related results, including EF1+PO allocations.

A recurring theme throughout the course is the mechanism-design notion of strategyproofness. 

Prerequisites

• A basic course in algorithms, discrete maths, and mathematical maturity.

References

• Gusfield, D. & Irving, R.W. (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press.

• Manlove, D.F. (2013). Algorithmics of Matching Under Preferences. World Scientific.

• Robertson, J. & Webb, W. (1998). Cake-Cutting Algorithms: Be Fair if You Can. A K Peters.

• Amanatidis, G. et al. (2023). Fair Division of Indivisible Goods: Recent Progress and Open Questions. Artificial Intelligence, 103965.

Lecture timings

Monday 5:00 PM.
Friday 2:00 PM.
Venue: Lecture Hall 6.

Lectures

Material covered so far in each lecture:

• Lecture 1 (Introduction) - Wednesday, Aug. 5, 3:30 PM: Introduction to matching markets and fair division; allocation without prices; motivating applications (house allocation, school choice, medical residency (NRMP), and kidney exchange); failures of decentralized markets; centralized clearinghouses; informal introduction to stability, Pareto optimality, fairness, and strategyproofness; course roadmap.

• Lecture 2 (House Allocation) - Friday, Aug. 7, 2:00 PM: Formal model of the house allocation problem; Pareto optimality (PO), strategyproofness, and group strategyproofness; Serial Dictatorship (SD); Random Serial Dictatorship (RSD); lotteries over allocations; equal treatment of equals; brief introduction to the Probabilistic Serial (PS) mechanism.

References: (i) Manlove, D. F. (2013). Algorithmics of Matching Under Preferences, Chapter 6. (ii) Abdulkadiroğlu, A. and Sönmez, T. (1998). Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3), 689–701.

Suggested optional reading: Bogomolnaia, A. and Moulin, . H. (2001).  A New Solution to the Random Assignment Problem. 

• Lecture 3 (Housing Market) - Monday, Aug. 10, 3:30 PM: The Housing Market Model; Individually Rational (IR) Allocations; an example of a blocking coalition in an (IR+PO) allocation; the concept of the Core; the Core implies Pareto Optimality; Gale's Top Trading Cycles (TTC) algorithm; supporting lemmas for the proof of strategyproofness of TTC.

• Lecture 4: (Housing Market Continued) - Friday, Aug 14, 2:00 PM: Recap of the TTC algorithm; strategyproofness of TTC; the TTC allocation is in the core; uniqueness of the core allocation; a brief mention of the connection between RSD and TTC with random endowments; an introduction to House Allocation with Existing Tenants and the YRMH-IGYT mechanism; and a brief introduction to kidney exchange.
  
  References: (i) Manlove, D. F. (2013). Algorithmics of Matching Under Preferences, Chapter 6 (Section 6.2.1.4). (ii) Strategyproofness of TTC (iii) This and this slides (iv) Kidney exchange (Lecture 10 of these notes)
  
  Suggested optional reading: Abdulkadiroğlu, A. and Sönmez, T. (1999). House Allocation with Existing Tenants. Journal of Economic Theory, 88(2):233–260.

• Lecture 5: (Popular Matchings) - Monday, Aug 17, 5:00 PM: One-sided matching with applicant preferences; popularity as a majority-based comparison of matchings; non-transitivity and non-existence of popular matchings; characterization for strict preference lists using f(a), s(a), and the reduced graph; and a linear-time algorithm for finding a popular matching.
  
  References: (i) Sections 1 and 2 of Abraham, D.J., Irving, R.W., Kavitha, T., and Mehlhorn, K. (2007), Popular Matchings, SIAM Journal on Computing, 37(4), 1030–1045; (ii) Manlove, D. F. (2013). Algorithmics of Matching Under Preferences, Chapter 7 (Sections 7.1, 7.2.1–7.2.3).

• Lecture 6, 7, 8: (Popular matchings with Ties) - Aug 21, Aug 24, and Aug 28: Popular matchings in one-sided settings with ties; E/O/U decomposition and the Dulmage--Mendelsohn decomposition theorem; characterization via the generalized sets $f(a)$ and $s(a)$ and the reduced graph; and an $O(\sqrt{n}\,m)$ algorithm for finding a popular matching using the Hopcroft--Karp algorithm.
  
  References: (i) Section 3 of Abraham, D.J., Irving, R.W., Kavitha, T., and Mehlhorn, K. (2007), Popular Matchings, SIAM Journal on Computing, 37(4), 1030–1045; (ii) Manlove, D. F. (2013). Algorithmics of Matching Under Preferences, Chapter 7 (Section 7.2.6).