CS Paper Radar

Fairness and Non-wastefulness in Matching with Siblings and Initial Enrollments: Compatibility and Complexity

Haris Aziz, Gergely Csáji, Zhaohong Sun, Makoto Yokoo

cs.GT ·submitted 2026-10-01 04:34 UTC · v1

Abstract

We study a two-sided matching problem between families and daycare centers in which a family may have multiple children with joint preferences, and some children may already be enrolled in daycare centers while seeking transfers. Our model combines and generalizes two well-studied matching frameworks: matching with couples and school choice with initial enrollments. The interaction between joint family preferences and initial enrollments creates fundamental challenges for the existence of desirable outcomes and the design of computationally efficient algorithms. Since stable matchings need not exist, we decompose stability into individual rationality, fairness, and non-wastefulness, and study the trade-off between fairness and non-wastefulness from two complementary directions. To preserve non-wastefulness, we first consider master-list-based approaches and show that they are insufficient in the presence of initial enrollments. We then introduce \emph{resettlement}, which protects displaced families by allowing them to return to their initial assignments, and develop a greedy improvement algorithm that establishes the existence of matchings satisfying non-wastefulness together with resettlement-based fairness. To preserve fairness, we first examine a generalized cutoff approach and then develop a fairness-preserving non-wasteful algorithm that guarantees fairness together with a relaxed notion of non-wastefulness. We further characterize the computational complexity of these solution concepts. While several fairness notions can be verified in polynomial time, deciding whether a non-wasteful matching satisfying them exists is NP-complete. Resettlement restores universal existence, but computing resettlement-based outcomes is PLS-hard, and verifying the stronger dominance-based fairness notion is coNP-complete.

Closest papers

Nearest neighbours by meaning across the whole index.

Fair Stable Matching: A Nash Social Welfare Approach

cs.GT cs.AI ·2026-09-02 ·Parth Desai, Rasheed M, Ganesh Ghalme, Sujit Gujar
similarity 0.66
Abstract

While traditional stable matching algorithms, such as the Gale-Shapley algorithm, prioritize stability, they may fall short of achieving equitable outcomes among participants. We study the role of \emph{Nash social welfare} (NSW) as a fairness objective in the classic \emph{stable marriage problem}. We develop \texttt{SNSW-Alg} that finds a stable matching that maximizes Nash social welfare under rank-induced utilities in $\tilde{\mathcal{O}}(n^4)$ time, where $n$ is the number of men or women. We demonstrate that \texttt{SNSW-Alg} balances equity while preserving stability. We empirically evaluate our methods across diverse preference distributions, demonstrating significant gains in fairness without substantial losses in other key measures such as regret, egalitarian criterion, and sex equality. Our findings suggest that the stable matching produced by \texttt{SNSW-Alg} is statistically Pareto-undominated by stable matchings based on other fairness measures - regret, egalitarian, and sex equality. This study offers compelling insights for designing fair-stable matching.

0.23

Capacity Modification for Matching with Couples: An Integer Programming and Computational Study

cs.GT ·2026-10-23 ·Zexiao Wu, Genjiu Xu, Péter Biró
similarity 0.64
Abstract · 31 pages, 4 figures

We study capacity modification in the Hospitals/Residents problem with Couples, in which hospital capacities and a stable matching are jointly determined. Exact and Cutoff integer programming formulations are developed for the resulting problem. We assume that, for each couple, either both members are matched or neither is. For arbitrary strict preferences, every instance admits a stable matching after changing each hospital capacity by at most two. Total capacity increases by at most one, and this bound is tight. Under sub-responsive and sub-complete couple preferences, a stable matching exists after adding at most one position to each hospital. The total number of additions is at most the number of couples, and this bound is also tight. Computational experiments show that Exact formulations are modestly faster at fixed capacities, whereas Cutoff formulations perform substantially better in the minimum repair experiments and attain higher completion rates in markets with up to 30,000 doctors. Across 96,000 synthetic and reconstructed markets, small capacity changes restore existence whenever no stable matching exists at the original capacities.

0.25

Rules, Choice, and Chance: A Welfare Evaluation Framework for Student-School Matching

cs.CY ·2026-11-08 ·Reetahan Mukhopadhyay, Clara Strasser Ceballos, Augustin Plantureux, Christoph Kern, Julia Stoyanovich
code/data similarity 0.60
Abstract · 42 pages, 26 figures, with 14 page main section

Centralized student-school matching systems, adopted in the United States, Chile, the Netherlands, and the United Kingdom, assign students to schools based on their submitted preference rankings and schools' priority policies. Yet welfare in these systems is typically measured through a narrow lens: a few aggregate statistics published by education authorities, such as the share of students unmatched or assigned to a top-ranked choice. A single aggregate cannot reveal how outcomes vary across students, or why. Welfare depends on three interacting forces: the rules policymakers set (algorithm, tie-breaking, list length limits); the choices students make (which and how many schools to rank); and chance (lottery draws and students' residential location). A rule that reduces unmatched rates may simultaneously lower top-ranked assignment rates for specific groups, and evaluating such trade-offs in advance is challenging because individual-level preference data are rarely available. We present Trace (Trade-offs in Rules, Agency, Chance, and Equity), an open-source framework that synthesizes individual-level preference profiles from aggregate data using mixtures of Mallows models and evaluates alternative rules across multiple welfare metrics, disaggregating outcomes by choice and chance. We apply Trace to two real-world systems: NYC high school matching, where we study minimum list length requirements, and Chilean school assignment, where we compare the current multiple tie-breaking rule with a counterfactual single tie-breaking rule. Both reveal substantial, heterogeneous welfare trade-offs, underscoring the value of simulation-based evaluation before implementing school choice reforms.

0.27

Computing Stable Matchings under Complementarities and Preference Misalignment

cs.GT ·2026-10-05 ·Tatsuya Iwase, Baharak Rastegari, Sebastian Stein, Enrico H. Gerding
similarity 0.60
Abstract

We study many-to-one, two-sided stable matching problems in which preferences are complementary and firms and workers may rank the same allocation differently. Here a coalition is a group of workers that can be jointly matched with a firm. With complementary preferences, a stable matching need not exist. We show that a stable matching exists for every instance when two conditions hold. The first requires each firm to have an anchor worker who is included in every feasible coalition that can be matched with that firm. The second is Transitive Alignment, which means there must be an overall ranking across different coalitions that is consistent with the workers' preferences. We propose CDAR (Combinatorial Deferred Acceptance with Reproposals), a Deferred Acceptance-style algorithm that permits reproposals, and prove its finite-time convergence and its output of a stable matching by constructing an $N$-digit potential function. Moreover, we show that, under strict preferences, the output of CDAR is Pareto optimal among stable matchings. The proposed framework naturally captures applications such as vehicle-route assignment for traffic safety and the misaligned interests of labor and management in wage negotiation.

0.17

Online Fair Division under Eligibility Constraints

cs.GT ·2026-10-06 ·Joes Biburger, Nicole Megow, Golnoosh Shahkarami
theory similarity 0.57
Abstract

We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assignment in scheduling, with agents as machines and items as jobs, and captures settings where work or resources must be split among parties with different capabilities. Eligibility makes the usual fairness benchmarks inadequate, as agents should not be measured against items they could never receive. We therefore use eligibility-aware versions of proportionality and envy-freeness, where an agent's proportional share splits each item equally among its eligible agents, and envy comparisons discount items the agents are not eligible for. Our main finding is a sharp chore--goods separation for proportionality. We focus on identical valuations: under arbitrary valuations, no online algorithm can guarantee even an $o(m)$-approximation for chores. For chores, Prop1 is achievable offline, whereas exact proportionality and proportionality up to any item are not. For online chores, the optimal approximation factor for Prop1 for deterministic algorithms is $Θ(\sqrt m)$, with the lower bound holding even for unit-size jobs. For goods, Prop1 is again achievable offline, but the tight online bound drops to $Θ(\log m)$. For envy-based fairness, the picture is different. Goods and chores are equivalent under eligibility-aware envy notions, while the choice of notion is decisive. Strong EF1 may fail to exist even offline and cannot be approximated online. In contrast, weak EF1 can be maintained online, while weak EFX separates offline from online. Together, these results give a systematic study of online proportional and envy-based fairness in restricted assignment and show which fairness guarantees remain achievable under eligibility constraints.

0.36

Personalized Recommendations Without Inducing Congestion: Mitigating Disparities in the NYC High School Match

cs.CY econ.GN ·2026-10-06 ·Erica Chiang, Kenny Peng, Rebecca Lichtenstein, Brielle McDaniel, Kristen O'Neil +5 more
similarity 0.57
Abstract · Preliminary version in ACM EC 2026

Algorithmic recommendations can help participants navigate large matching markets. For example, recommendations for school and college choices may reduce information frictions and disparities in access to high-performing programs. At scale, however, recommenders in capacity-constrained settings can be self-defeating: if they steer too many users toward the same items, then even users who were originally predicted to have a high chance of matching to an item may not, due to increased competition. In this paper, we formalize this phenomenon of recommendation-induced congestion; motivated by the NYC high school match, we show that naive recommendations can cause sharp decreases in program acceptance rates, most affecting applicants with the fewest nearby options. Next, we propose and theoretically analyze a congestion-aware, bilevel optimize-and-simulate approach to allocate recommendations and improve match outcomes safely, in equilibrium. Finally, we deploy this approach in the 2025-26 admissions cycle of the NYC high school match, aiming to reduce disparities by highlighting personalized lists of nearby, high-performing programs where an applicant has a high predicted offer likelihood. In a randomized controlled trial, we find that 16.4% of treatment applicants ranked a recommended program, versus 10.5% of control applicants who ranked a program they would have been recommended (57% relative increase; $p$=0.011); 5.6% of treatment applicants matched to such a program, versus 3.3% of control applicants (71% relative increase; $p$=0.071); further, no treatment applicant was rejected from a recommended program. Our findings suggest that recommenders should be analyzed and designed as market-shaping interventions.

0.32

A Matroid Generalization of Weighted Popular Matching: Characterization and Algorithm

cs.GT cs.DS ·2026-10-13 ·Yuni Iwamasa, Yusuke Kobayashi, Ryoga Mahara, Kenjiro Takazawa
similarity 0.56
Abstract

We study a problem that unifies two major generalizations of popular matchings in the one-sided preference model. In a bipartite graph in which each vertex, or applicant, on one side has preferences over the adjacent vertices, a matching is called popular if it does not lose a head-to-head election against any other matching. Since the seminal work of Abraham, Irving, Kavitha, and Mehlhorn, who gave the first polynomial-time algorithm for finding a popular matching, numerous generalizations of the popular matching problem have been investigated. Two prominent directions are weighted popular matchings, in which each applicant is assigned a voting weight, and popularity problems under matroid constraints. The former admits a polynomial-time algorithm due to Mestre, while the most general form of the latter is the popular common independent set problem, for which a polynomial-time algorithm is given by Kavitha, Makino, Schlotter, and Yokoi. In this paper, we introduce the weighted popular common independent set problem, which simultaneously generalizes weighted popular matchings and popular common independent sets. Our main result is the first polynomial-time algorithm for this problem. A key ingredient of the algorithm is a solution-independent characterization of weighted popular common independent sets, which we establish in this paper. As consequences of our algorithmic result, we obtain polynomial-time algorithms for several previously unresolved problems, including weighted popular matchings with matroid constraints and weighted popular branchings.

0.12

The Complexity of Minimizing Subsidies in Envy-Free House Allocation

cs.GT cs.CC ·2026-08-23 ·Sijia Dai, Minming Li, Xiaowei Wu, Yong Zhang
similarity 0.56
Abstract

The house allocation problem is a classical one-sided matching problem that concerns the assignment of a set of $m$ houses to $n$ agents according to their preferences, where each agent is assigned exactly one house. Among the various objectives studied in this setting, envy-freeness is one of the most widely adopted fairness criteria. As envy-free house allocations do not always exist, we address this challenge by introducing subsidies and aim to compute allocations that achieve envy-freeness with minimum total subsidy. For binary instances, we show that a total subsidy of at most $(n-1)$ suffices to guarantee envy-freeness in house allocation, and this bound is tight. Building on the known NP-hardness for general utilities, we further show that computing an allocation that minimizes the total subsidy is NP-hard, even under binary utilities. However, when there are only a bounded number of types of agents with binary utilities, the problem can be solved in polynomial time. Finally, we present a polynomial time algorithm that computes the minimum subsidy required to achieve envy-freeness for two types of agents with general utilities.

0.22