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).

• Lecture 9: (Stable Marriage) -  Aug 31:  Stable marriage model; blocking pairs and stability; stability-checking algorithm; Gale-Shapley (GS) / deferred acceptance (DA) algorithm; stable matchings need not be unique (and there can be exponentially many); the GS/DA algorithm produces the stable matching that is best for every agent on the proposing side; all executions of men-proposing GS/DA algorithm produce the same stable matching.
  
  References: (i) Chapter 1, Sections 1.1, 1.2.1, and 1.2.2 of Gusfield, D. & Irving, R.W. (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press. (ii) D. Gale and L. S. Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1):9–15, 1962.

• Lecture 10:  (Lattice Structure of Stable Matchings) -  Sept 04: Men-optimal stable matching is women-pessimal and vice versa; men’s dominance order on stable matchings; partial-order structure of stable matchings; lattice theorem: any two stable matchings have a well-defined join and meet; opposite dominance order for women.
  
  References: (i) Chapter 1, Sections 1.2.2 and 1.3 of Gusfield, D. & Irving, R. W. (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press.

• Lecture 11:  (Rotation and Rotation Poset) - Sept 07:  GS-reduced lists; M-reduced(short) lists for a stable matching M; rotations; elimination of an exposed rotation gives the next stable matching, with no stable matching in between; every stable matching other than women-optimal stable matching exposes a rotation; at most O(n^2) rotations; the rotation poset; closed subsets of a poset.
  
  References: Chapter 2, Section 2.5 of Gusfield, D. & Irving, R. W. (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press.

• Lecture 12:  (Recap, Applications of Rotations, Incomplete Lists, Hospital–Residents, and Strategyproofness) -  Sept 11: 
  Story so far: Stable matchings of an instance form a distributive lattice with two extremes M_0 and  M_z; M_0 >=  M >= M_z for every stable matching M; short lists; intuitive meaning of rotations as special alternating cycles; eliminating a rotation from a stable matching results in a neighboring stable matching in the lattice; every non-M_z stable matching exposes a rotation (in fact,  for any two stable matchings M and N with M >= N, M exposes a rotation ρ and M/ρ >= N); rotations generate the entire lattice; all rotations exposed in a stable matching are pairwise disjoint; no rotation repeats along any sequence of rotation eliminations; if ρ \neq ρ′ are both exposed in M, then ρ remains exposed in M/ρ′, ρ′ remains exposed in M/ρ, and (M/ρ)/ρ′ = (M/ρ′)/ρ; for M>= N every sequence of rotation eliminations starting at M and ending at N uses the same number of steps and the same set of rotations (without proof -- try it yourself: first prove the result for N=M_z by induction and then use it to prove the general case  N <= M); O(n^2) many rotations; O(n^2) algorithm for enumerating all rotations using short lists (only intuitive idea without proof); the precedence relation on rotations; precedence relations can be generated in O(n^2) time (without proof); the resulting rotation poset; closed subsets; and the one-to-one correspondence between stable matchings in the lattice and closed subsets of the rotation poset.
  
  Applications of rotations: characterizing stable pairs; egalitarian stable matching (a very brief picture); and, of course, the compact representation of the set of all stable matchings.
  Stability with incomplete preference lists: the main structural picture developed so far extends to this setting (try it yourself); invariance of matched agents; all stable matchings in a one-to-one instance with strict preference lists have the same cardinality.
  Many-to-one Hospital–Residents setting: cloning technique; the corresponding GS/DA algorithm; Rural Hospitals theorem (statement only, without proof).
  Strategyproofness: For one-to-one setting, GS/DA is strategyproof for the proposing side (statement only); GS/DA is not strategyproof for the receiving side (counterexample); Roth's impossibility theorem (statement only; proof in the next lecture).
  
  References: (i) Section 2.5, 1.4, and 1.6 of Gusfield, D. & Irving, R. W. (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press.  (ii) A. E. Roth. The Economics of Matching: Stability and Incentives. Mathematics of Operations Research, 7(4):617–628, 1982.