Compatible k k -Relaxations of Fairness and Non-Wastefulness Under Hereditary Constraints
Tenma Wakasugi, Zhaohong Sun, Kei Kimura, Makoto Yokoo · 2026
Read Compatible k k -Relaxations of Fairness and Non-Wastefulness Under Hereditary Constraints by Tenma Wakasugi, Zhaohong Sun, Kei Kimura, Makoto Yokoo (2026) 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-2605-00134.txt.
Introduction
Tenma Wakasugi, Zhaohong Sun, Kei Kimura, and Makoto Yokoo study two-sided matching markets, such as assigning students or refugees to places, under broad hereditary constraints. These constraints go beyond simple capacity limits. In such markets, fairness and non-wastefulness often clash, and most methods protect one by giving up the other.
The authors instead relax both goals in a balanced, measured way. They define two graded notions, each indexed by a number k, and prove the two can always be met together for any fixed k. They give two fast algorithms to compute such matchings. Experiments show that even a small relaxation strikes a good balance between fairness and use of places.
Catalog record
| CREATOR | Tenma Wakasugi, Zhaohong Sun, Kei Kimura, Makoto Yokoo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.00134
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Compatible k k -Relaxations of Fairness and Non-Wastefulness Under Hereditary Constraints Tenma Wakasugi, Zhaohong Sun, Kei Kimura, Makoto Yokoo Abstract We study two-sided matching markets under hereditary constraints, which extend beyond simple capacity limits and arise in applications such as diversity requirements and refugee resettlement. In these settings, fairness and non-wastefulness are often incompatible, and existing approaches typically address this tension by prioritizing one property at the expense of the other. We take a different approach by relaxing both properties simultaneously in a controlled and symmetric manner. We introduce two notions indexed by an integer k k : envy-received up to k k peers (ER- k k ) and non-wastefulness up to k k objections (NW- k k ). Our main theoretical result shows that ER- k k and NW- k k are always compatible under hereditary constraints for any fixed k k . We provide two equivalent polynomial-time algorithms to compute such matchings: a k k -admissible cutoff algorithm and a k k -admissible college-proposing deferred acceptance mechanism. Finally, experimental results demonstrate that even small relaxations achieve a favorable balance between fairness and non-wastefulness. 1 Introduction Centralized algorithms for two-sided matching markets have achieved remarkable success in a wide range of applications, most notably in matching residents to hospitals ( 23 ) and students to colleges ( 1 ) . Classical models, however, typically assume simple capacity constraints on each institution. In many real-world matching and allocation problems, feasibility requirements are substantially richer and cannot be adequately represented by capacities alone. A prominent example arises in college admissions, where diversity considerations play a central role. Students are often associated with observable characteristics, and colleges reserve seats by type in order to promote balanced representation ( 3 ; 7 ; 2 ) . In refugee resettlement, authorities must assign refugee families to localities subject to limited resources across multiple dimensions, such as education, healthcare, housing, and employment, while ensuring that all members of a family are placed together ( 11 ; 5 ) . Daycare assignment provides another illustration: legal regulations impose age-dependent teacher–child ratios and space requirements, giving rise to feasibility constraints that cannot be effectively captured by simple capacity limits ( 18 ; 24 ) . More complex feasibility structures also arise when individual institutions face their own capacity constraints while collections of institutions are jointly subject to aggregate quotas, as in Hungarian college admissions ( 8 ) and hospital–doctor matching in Japan ( 16 ) . Related feasibility concerns appear in internship and research matching programs, where assigning students to projects requires supervisors to allocate limited funding or supervision capacity across multiple projects, as observed in Australian undergraduate research schemes ( 4 ) . The abovementioned forms of feasibility constraints all fall within a broad framework commonly referred to as hereditary constraints ( 14 ; 21 ) . This framework provides a unifying and expressive way to model a wide range of practically important matching environments. Under hereditary constraints, any feasible matching remains feasible after the removal of any subset of matched students. In this paper, we focus on matching problems with hereditary constraints and investigate which desirable properties can be achieved under such general feasibility restrictions. Given the generality of these constraints, the classical notion of stability from the seminal matching literature is no longer guaranteed to exist. Stability can be decomposed into two distinct components: fairness , which requires that no agent has justified envy toward another agent with lower priority, and non-wastefulness , which requires that no agent can claim an empty seat, i.e., no agent can be matched to a more preferred option without violating feasibility. Under general feasibility constraints, these two properties are often fundamentally in tension. Existing approaches typically address this tension by prioritizing one property at the expense of the other, either abandoning one property entirely ( 14 ; 18 ) or preserving one while substantially weakening the other ( 4 ) . Consequently, mechanisms that enforce fairness may lead to highly wasteful outcomes with many empty seats, while mechanisms that enforce non-wastefulness may produce outcomes exhibiting widespread justified envy. What is notably missing is an approach that treats fairness and non-wastefulness in a balanced manner. In this paper, we take a different approach. Rather than insisting on fully preserving one property, we propose to relax both fairness and non-wastefulness simultaneously, in a controlled and symmetric manner. By weakening each notion just enough, we restore their compatibility and obtain outcomes that strike a meaningful balance: matchings that are substantially fair while avoiding excessive waste. This perspective enables us to navigate the fundamental trade-off between fairness and efficiency under general feasibility constraints, leading to new existence results and polynomial-time algorithms. To operationalize this idea, we introduce two symmetric, parametric relaxations of fairness and non-wastefulness. Both notions are indexed by a nonnegative integer k , which measures the extent to which violations are permitted. The first notion, envy-received up to k peers (ER- k ), relaxes fairness by limiting how widespread envy can be. Specifically, no student may be envied by more than k other students. When k=0 , ER- 0 coincides with classical fairness, while larger values of k allow controlled violations of fairness, in the sense that any envy is confined to at most k affected students. 1 1 1 This concept was studied independently and contemporaneously by 25 in a different setting, and their paper appeared shortly before the present submission. Although motivated by different considerations, the resulting notion is equivalent. The second notion, non-wastefulness up to k objections (NW- k ), relaxes non-wastefulness by limiting when a student can legitimately claim an empty seat. Under NW- k , an empty seat may remain unfilled only if assigning a student to that seat would trigger objections from more than k other students. Thus, larger values of k make it harder to justify leaving seats unfilled, strengthening efficiency requirements by allowing empty seats only when filling them would substantially harm other students. We summarize our contributions as follows. First, we introduce new relaxations of fairness and non-wastefulness, both parameterized by an integer k : Envy-Received-Freeness up to k Agents (ER- k ) and Non-Wastefulness up to k Objections (NW- k ). By varying k , these notions subsume several existing concepts in the literature and provide a unified taxonomy of fairness and non-wastefulness. Figure 1 illustrates the relationships and compatibility among these notions. Second, we establish a general existence result for ER- k and NW- k outcomes, showing that the two notions are always compatible under hereditary constraints. This result generalizes the findings of 4 , whose notions of fairness and cutoff non-wastefulness correspond to the special cases ER- 0 and NW- 0 in our framework. We further show that this result is tight: in general, ER- k and NW- k+1 , as well as ER- k-1 and NW- k , are incompatible. Note that ER-k becomes more stringent as k decreases, whereas NW-k becomes more stringent as k increases. Third, we design two polynomial-time algorithms for computing ER- k and NW- k matchings: a k -admissible cutoff algorithm and a k -admissible college-proposing deferred acceptance mechanism . The former extends the original cutoff algorithm, which is restricted to ER-