Algorithmics of Matching Under Preferences
by David F. Manlove · World Scientific
Research monograph on algorithms and complexity for matching problems where agents have preferences. It covers stable marriage, hospitals/residents, stable roommates, ties and incomplete lists, Pareto optimal and popular matchings, and house allocation.
This link may earn us a small commission at no extra cost to you. Affiliate disclosure
More resources on Matching Theory
Algorithms, Part I
This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms. All the features of this course are available for free. People who are interested in digging deeper into the content may wish to obtain the textbook Algorithms, Fourth Edition (upon which the course is based) or visit the website algs4.cs.princeton.edu for a wealth of additional material. This course does not offer a certificate upon completion.
Wolfram MathWorld
MathWorld is an online mathematics encyclopedia from Wolfram Research offering detailed, browsable articles on topics across the math spectrum, including algebra, geometry, calculus, and number theory. Each entry includes definitions, theorems, formulas, diagrams, worked examples, and links to further reading.
Wikipedia: Matching (graph theory)
Encyclopedia article covering matchings in graphs: maximal, maximum, perfect and weighted matchings, König's theorem, Hall's marriage theorem, Tutte's theorem, and algorithms such as Hopcroft–Karp and Edmonds' blossom, with references for deeper study.
Stable Allocations and the Practice of Market Design (Scientific Background, Nobel Prize in Economic Sciences 2012)
The Royal Swedish Academy's 44-page technical survey written for the 2012 economics prize to Shapley and Roth. It covers stable matching theory, deferred acceptance, strategy-proofness, the lattice of stable matchings, and real uses in medical residency matching, school choice, and kidney exchange.
College Admissions and the Stability of Marriage
Primary source for the stable-marriage part of the topic, readable without prerequisites. The 1962 American Mathematical Monthly paper that defined stable matchings and introduced the deferred-acceptance algorithm. In seven readable pages it proves that every stable marriage instance has a stable matching and extends the result to college admissions.
Lecture Notes on Non-Bipartite Matching (MIT 18.433 Combinatorial Optimization)
Companion MIT notes on maximum matchings in general graphs. They cover Berge's augmenting path theorem, the Tutte–Berge formula, Gallai–Edmonds structure, and Edmonds' blossom algorithm for finding maximum matchings when the graph is not bipartite.