A Unified Guide to Stable Matching Problems: Combinatorial Algorithms, Linear Programming, and Approximations Singh, Vivaan social computational choicerational decision makinglinear programmingstable matchingcombinatorial optimizationmechanism designmarket designsocial computational choicerational decision makinglinear programmingstable matchingcombinatorial optimizationmechanism designmarket designInformation Sciences and TechnologyB SMatching 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.Hadi Hosseini, Thesis SupervisorMartin Fürer, Thesis Honors Advisoropen_access2026-04-24T02:07:11Zhttps://honors.libraries.psu.edu/catalog/10171vzs5355