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.

Exam Details

Quiz 1 (hybrid mode) - September 18, 2026 (Friday)
Mid-semester Examination - September 26, 2026 (Saturday)
Quiz 2 (in-class) - November 13, 2026 (Friday)  --  Rescheduled to an earlier date from Nov 20, 2026
End-semester Examination - TBD

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.

• Quiz 1: September 18, 2026

• Mid-Semester Examination: Sept 26, 2026

•  Lecture 13: (Roth’s Impossibility Theorem and Stable Matchings with Ties)  - Sept 28:  Proof of Roth’s impossibility theorem using his (3x3) instance with strict, complete preference lists;  stable marriage with ties and incomplete lists (SMTI); weak stability, strong stability, and super-stability; existence of weakly stable matchings via arbitrary tie-breaking; different tie-breakings can yield weakly stable matchings of different cardinalities; NP-hardness of MAX-SMTI (without proof); arbitrary tie-breaking followed by Gale–Shapley as a 2-approximation algorithm; the short-augmenting-path criterion for a (3/2)-approximation; Király’s promotion algorithm for ties only on the receivers’ side: promotion and starred proposers.
  
  References: (i) A. E. Roth. The Economics of Matching: Stability and Incentives. Mathematics of Operations Research, 7(4):617–628, 1982.  (ii) D. F. Manlove, R. W. Irving, K. Iwama, S. Miyazaki, and Y. Morita. Hard variants of stable marriage. Theoretical Computer Science, 276(1–2):261–279, 2002. (iii) Z. Király. Better and Simpler Approximation Algorithms for the Stable Marriage Problem. Algorithmica, 60:3–20, 2011. Conference version: ESA 2008, LNCS 5193, pp. 623–634. 2008

• Lecture 14: (Stable Matchings with Two-Sided Ties) - Oct 05: Review of Király’s promotion algorithm for ties only on the receivers’ side: promotion and starred proposers; proof of its (3/2)-approximation guarantee; Király’s algorithm for two-sided ties: the concept of uncertain proposals and favorite-neighbors to handle ties on the proposers’ side, and promotion to handle ties on the receivers’ side; complete proofs of stability and the (3/2)-approximation guarantee.
  
  References: (i) Z. Király. Linear Time Local Approximation Algorithm for Maximum Stable Marriage. Algorithms, 6(3):471–484, 2013.

• Lecture 15 and 16: (Popular Matchings with Two-Sided Strict Preferences) - Oct 09 and Oct 12:  Motivation: relaxing pairwise stability to obtain larger matchings; popular matchings defined through votes; strict, possibly incomplete preference lists on both sides; existence of popular matchings, in contrast to the one-sided setting; every stable matching is popular and has minimum cardinality among popular matchings; the two-level GS/DA algorithm for computing a maximum-cardinality popular matching; structural properties of the output using levels and edge labels; complete proofs of popularity and maximum cardinality using alternating paths and cycles; linear running time; the (3/2)-approximation guarantee with respect to any maximum-cardinality matching (not necessarily popular).
  
  Reference: T. Kavitha. A Size-Popularity Tradeoff in the Stable Marriage Problem. SIAM Journal on Computing, 43(1):52–71, 2014.

• Lecture 17: (Cake Cutting I - Proportional Division) - Oct 16: Heterogeneous divisible goods and additive valuations; proportionality and envy-freeness, and their relationship; the Robertson–Webb query model and query complexity; cut-and-choose for two agents and its extension to proportional division among three agents; the Dubins–Spanier moving-knife procedure for n agents and its discrete implementation using O(n^2) queries; the Even–Paz divide-and-conquer algorithm using O(n\log n) queries; correctness proofs and query-complexity analyses of these protocols.
  
  References:  (i) (Chapter 1 and Section 2.4) of J. Robertson and W. Webb. Cake-Cutting Algorithms: Be Fair If You Can. A K Peters, 1998. (ii) S. Even and A. Paz. A Note on Cake Cutting. Discrete Applied Mathematics, 7(3):285–296, 1984.