[2J5-GS-5] Agents:

[2J5-GS-5-03] New fairness and efficiency concepts in two-sided matching under regional constraints

〇Aoto Goto¹, Zhaohong Sun¹, Makoto Yokoo¹ (1. Kyushu University)

Keywords:two-sided matching, constraint programing

In this paper, we study a two-sided matching problem under regional quotas, with a particular focus on hospital-residency matching in Japan. It is well-established that when regional caps are imposed, a fair and non-wasteful matching may not always exist. To overcome this incompatibility, a common approach is to balance fairness and efficiency by fully satisfying one while partially relaxing the other. To address this challenge, we introduce the concepts of weaker fairness (EF-k, REF-k, SEF-k) and weaker efficiency (NW-l). Using constraint programming (CP), we propose algorithms that either satisfy non-wastefulness and relaxed fairness or fairness and relaxed non-wastefulness. Through evaluation experiments, we find that REF-k achieves the highest level of fairness when paired with CP under non-wastefulness constraints. We also compare the performance of CP-based approaches with constrained fairness and NW-l against existing fairness mechanisms, FDA and PLDA. Our results show that CP outperforms FDA while achieving comparable performance to PLDA.