Two-Sided Fairness in Many-to-One Matching
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918150073745408 |
|---|---|
| author | Igarashi, Ayumi Kamiyama, Naoyuki Kawase, Yasushi Suksompong, Warut Sumita, Hanna Yokoi, Yu |
| author_facet | Igarashi, Ayumi Kamiyama, Naoyuki Kawase, Yasushi Suksompong, Warut Sumita, Hanna Yokoi, Yu |
| contents | We consider a classic many-to-one matching setting, where participants need to be assigned to teams based on the preferences of both sides. Unlike most of the matching literature, we aim to provide fairness not only to participants, but also to teams using concepts from the literature of fair division. We present a polynomial-time algorithm that computes an allocation satisfying team-justified envy-freeness up to one participant, participant-justified envy-freeness, balancedness, Pareto optimality, and group-strategyproofness for participants, even in the possible presence of ties. Our algorithm generalizes both the Gale-Shapley algorithm from two-sided matching as well as the round-robin algorithm from fair division. We also discuss how our algorithm can be extended to accommodate quotas and incomplete preferences. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_24111 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two-Sided Fairness in Many-to-One Matching Igarashi, Ayumi Kamiyama, Naoyuki Kawase, Yasushi Suksompong, Warut Sumita, Hanna Yokoi, Yu Theoretical Economics Computer Science and Game Theory We consider a classic many-to-one matching setting, where participants need to be assigned to teams based on the preferences of both sides. Unlike most of the matching literature, we aim to provide fairness not only to participants, but also to teams using concepts from the literature of fair division. We present a polynomial-time algorithm that computes an allocation satisfying team-justified envy-freeness up to one participant, participant-justified envy-freeness, balancedness, Pareto optimality, and group-strategyproofness for participants, even in the possible presence of ties. Our algorithm generalizes both the Gale-Shapley algorithm from two-sided matching as well as the round-robin algorithm from fair division. We also discuss how our algorithm can be extended to accommodate quotas and incomplete preferences. |
| title | Two-Sided Fairness in Many-to-One Matching |
| topic | Theoretical Economics Computer Science and Game Theory |
| url | https://arxiv.org/abs/2509.24111 |