Compatible $k$-Relaxations of Fairness and Non-Wastefulness Under Hereditary Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918477017645056 |
|---|---|
| author | Wakasugi, Tenma Sun, Zhaohong Kimura, Kei Yokoo, Makoto |
| author_facet | Wakasugi, Tenma Sun, Zhaohong Kimura, Kei Yokoo, Makoto |
| contents | 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$: envy-received up to $k$ peers (ER-$k$) and non-wastefulness up to $k$ objections (NW-$k$). Our main theoretical result shows that ER-$k$ and NW-$k$ are always compatible under hereditary constraints for any fixed $k$. We provide two equivalent polynomial-time algorithms to compute such matchings: a $k$-admissible cutoff algorithm and a $k$-admissible college-proposing deferred acceptance mechanism. Finally, experimental results demonstrate that even small relaxations achieve a favorable balance between fairness and non-wastefulness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_00134 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Compatible $k$-Relaxations of Fairness and Non-Wastefulness Under Hereditary Constraints Wakasugi, Tenma Sun, Zhaohong Kimura, Kei Yokoo, Makoto Computer Science and Game Theory 91B68 F.2; I.2 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$: envy-received up to $k$ peers (ER-$k$) and non-wastefulness up to $k$ objections (NW-$k$). Our main theoretical result shows that ER-$k$ and NW-$k$ are always compatible under hereditary constraints for any fixed $k$. We provide two equivalent polynomial-time algorithms to compute such matchings: a $k$-admissible cutoff algorithm and a $k$-admissible college-proposing deferred acceptance mechanism. Finally, experimental results demonstrate that even small relaxations achieve a favorable balance between fairness and non-wastefulness. |
| title | Compatible $k$-Relaxations of Fairness and Non-Wastefulness Under Hereditary Constraints |
| topic | Computer Science and Game Theory 91B68 F.2; I.2 |
| url | https://arxiv.org/abs/2605.00134 |