A Unified Guide to Stable Matching Problems: Combinatorial Algorithms, Linear Programming, and Approximations

open_access
Open Access
Author:
Singh, Vivaan
Area of Honors:
Information Sciences and Technology
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
Hadi Hosseini, Thesis Supervisor
Martin Fürer, Thesis Honors Advisor
Keywords:
social computational choice
rational decision making
linear programming
stable matching
combinatorial optimization
mechanism design
market design
social computational choice
rational decision making
linear programming
stable matching
combinatorial optimization
mechanism design
market design
Abstract:
Matching markets govern consequential allocations without prices: medical residents to hospitals, students to schools, donors to kidney patients. In these settings an algorithm decides who is assigned to whom, and the minimum acceptable standard for its output is stability — no pair of agents should prefer each other to their assigned partners. The standard mechanism, deferred acceptance, produces a stable matching but is systematically biased: the proposing side receives its best stable partner and the receiving side its worst. When fairness between sides matters, this bias is unacceptable. A typical instance admits many stable matchings, and different stable matchings embody different notions of welfare and fairness. This gives rise to a family of stable matching variants, each selecting a stable matching that optimizes some criterion. This thesis asks, for each variant, what the computationally best way to solve it is, with the goal of contributing solvers to MatchXplain, a web-based platform for exploring matching markets and the tradeoffs between their possible allocations. For each variant, a combinatorial algorithm is implemented alongside a linear or integer linear programming formulation over the stable matching polytope, and the two approaches are benchmarked empirically for correctness and runtime. The strict-preference variants studied are classical stable matching, egalitarian, minimum-regret, sex-equal, and median; the tie-preference variants are strong and super stability. On the polynomially solvable variants, the combinatorial and LP approaches return the same optimum — with the caveat that minimum-regret requires the ILP rather than the LP relaxation — but the combinatorial algorithm is faster by several orders of magnitude, except in the egalitarian case, where the gap narrows. On the hard variants (sex-equal is NP-hard, median is #P-hard), a breadth-first search over the rotation poset remains exact and tractable on random instances into the hundreds; beyond that regime, dedicated combinatorial approximations — bidirectional local search (BiLS) for sex-equal and Cheng’s topological-prefix algorithm for median — deliver the best quality, while LP rounding gives the weakest approximation tested. MatchXplain therefore ships the combinatorial solvers. The LP formulation nonetheless earns its place as a unifying lens: one polytope underlies every variant, and each variant reduces to a single objective over it.