Near-Feasible Solutions to Complex Stable Matching Problems

Gergely Csáji (HUN-REN KRTK) · 2025

Read Near-Feasible Solutions to Complex Stable Matching Problems by Gergely Csáji (HUN-REN KRTK) (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02503.txt.

Introduction

Gergely Csaji shows that near-feasible stable solutions always exist for many hard variants of the stable matching problem, in a 2025 paper. A solution is near-feasible when it stays stable but may slightly break some capacity limits. That promise matters when exact stable solutions cannot be found.

His rounding method starts from a stable fractional solution and adjusts capacities step by step until a whole-number stable solution exists. The start is computed with a classic algorithm. For one problem type, the whole method runs in fast polynomial time. The results give strong guarantees that stability can be restored with small changes, even under complex rules.

Catalog record

CREATORGergely Csáji (HUN-REN KRTK)
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-02503

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Near-Feasible Solutions to Complex Stable Matching Problems Gergely Csáji (HUN-REN KRTK) Abstract . In this paper, we demonstrate that in many NP-complete variants of the stable matching problem, such as the Stable Hypergraph Matching problem, the College Admission problem with Common Quotas and the Stable Multicommodity Flow problem, a near-feasible stable solution – that is, a solution which is stable, but may slightly violate some capacities – always exists. Our results provide strong theoretical guarantees that even under complex constraints, stability can be restored with minimal capacity modifications. To achieve this, we present an iterative rounding algorithm that starts from a stable fractional solution and systematically adjusts capacities to ensure the existence of an integral stable solution. This approach leverages Scarf’s algorithm to compute an initial fractional stable solution, which serves as the foundation for our rounding process. Notably, in the case of the Stable Fixtures problem, where a stable fractional matching can be computed efficiently, our method runs in polynomial time. These findings have significant practical implications for market design, college admissions, and other real-world allocation problems, where small adjustments to institutional constraints can guarantee stable and implementable outcomes. Conference: ; ; 1. Introduction and Related Work Stable matching problems are fundamental in economics and operations research, underpinning key applications such as student admissions, job markets, kidney exchanges, and housing allocations. These models provide a structured way to assign agents to institutions while ensuring fairness and stability. The Stable Matching problem was introduced by Gale and Shapley (1962) , along with their celebrated polynomial-time algorithm to find a stable matching. In their model, students express preferences over colleges, while colleges rank applicants and specify admission quotas, all of which are coordinated centrally. The key solution concept they introduced is stability , which ensures that a college only rejects an applicant if it has already filled its available spots with more preferred candidates. They proposed the deferred-acceptance (DA) algorithm, which guarantees the existence of a stable matching and yields an outcome most favorable to students when they are the proposing side. Gale and Shapley’s work has sparked extensive research across multiple disciplines, including mathematics, computer science, operations research, economics, and game theory. This field, commonly referred to as Matching Under Preferences or Matching Markets, has since grown into a major area of study. For a comprehensive overview, we refer readers to the book by Manlove (2013) . Stable matchings are also utilized in various real-world applications, including the famous U.S. National Resident Matching Program (NRMP) ( Roth, 1984 ) . Furthermore, they are used in various national college admissions and school choice programs worldwide. For an overview of applications in the U.S., we refer readers to the survey by Roth (2008) . Since the introduction of stable matchings, extensive generalizations have been studied, encompassing more complex settings where additional constraints, such as quotas or preferences over multiple partners, come into play. Some variants remain tractable, such as the Stable Roommates problem ( Irving, 1985 ) , which extends stable matchings to general graphs and the Stable Fixtures problem ( Irving and Scott, 2007 ) , which also introduces capacities. However, many extensions lead to computational intractability, including Stable Hypergraph Matching, College Admission (or Many-to-one Stable Matching) with Common Quotas, and the Stable Multicommodity Flow problem, all of which are NP-hard. Also, for such complex variants, stable matchings may fail to exist, making them less viable in practice. The main purpose of this paper is to show that even in these NP-hard variants, the existence of stable matchings can be guaranteed, if the capacities are allowed to be slightly violated. As a particularly relevant case, we also focus on a problem coming from college admissions. Here, many additional constraints and special features necessitate modifications to the standard DA algorithm. One key challenge is the presence of common quotas, which arise for example due to faculty-imposed limits on program enrollments and national quotas for state-financed students in specific subjects, see a description of the Hungarian case in ( Ágoston et al., 2022 ) . This feature makes the underlying matching problem NP-hard ( Biró et al., 2010 ) (except for the case, when the common quotas form a laminar system), though the resulting computational challenges can be potentially tackled by Integer Programming methods, as demonstrated by Ágoston et al. (2022) . As one of our main results, we show that for the College Admission with Common Quotas problem, if each college belongs to only a few sets with a common quota, then a minimal amount of modifications in the quotas can guarantee the existence of a stable matching. The study of stable matchings in hypergraphs originated with Aharoni and Fleiner (2003) , who formulated it as the problem of identifying core elements in simple NTU-games. This is closely related to core stability in hedonic coalition formation games (see, e.g., ( Banerjee et al., 2001 ; Woeginger, 2013 ; Aziz and Brandl, 2012 ) ). In this framework, vertices represent agents, while hyperedges correspond to potential coalitions. Each agent can participate in at most one (or more generally, a fixed number of) coalition(s) in the final solution, meaning that the goal is to find a valid matching in the hypergraph. Since agents’ preferences depend only on their own coalition, the problem is referred to as hedonic. Preferences are typically represented by a linear ordering of the incident hyperedges for each vertex. A coalition structure belongs to the core (or equivalently, the matching is stable) if no hyperedge exists that is strictly preferred by all its members over their current assignments. A special case of stable hypergraph matching, the 3-dimensional variant of stable matching – that is also related to the problem of assigning residents to hospitals in the presence of couples, as is the case currently in the NRMP – was proposed by Knuth (1997) and later investigated by Ng and Hirschberg (1991) and Huang (2007) . They proved that the problem is NP-complete even in restricted settings. Subsequent research has explored more complex matching problems to determine whether they can be framed as special cases of stable matchings in hypergraphs, where agents may also have capacity constraints. A general framework for this approach was developed by Biró and Fleiner (2016) , who applied Scarf’s lemma ( Scarf, 1967 ) , a fundamental theorem for NTU games, to prove the existence of fractional stable solutions in (capacitated) hypergraph matching problems. Moreover, as Scarf’s lemma was proved in an algorithmic way – later referred to as Scarf’s algorithm – this implies that stable fractional matchings can be found algorithmically. Sadly, the computation of a fractional solution by Scarf’S algorithm is not polynomial time in general. The PPAD-hardness of computing a fractional stable matching was proved by Kintali et al. (2013) and were linked with several other PPAD-hard combinatorial problems. A different type of generalization to network flows, called the Stable Flow problem, introduced by Fleiner (2010) , captures the challenge of finding a flow that satisfies stability conditions within a network, and the author provided a polynomial-time algorithm for computing such a stable solution. This concept was later extended by Király and Pap (2013) , who explored the more complex case of multiple commodities.

Read the complete text