[2Yin-B] Poster 4

[2Yin-B-24] Relaxation of fairness and non-wastefulness in two-sided matching under hereditary constraints

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

Keywords:

Multi agent,Mechanism design,Two-sided matching

In this paper, we study two-sided matching under hereditary constraints, which is applicable to problems such as diversity requirements and refugee resettlement. In these settings, a fair and non-wasteful matching may not always exist. To address this incompatibility, a common approach is to balance fairness and non-wastefulness by fully satisfying one while partially relaxing the other. We take a different approach by relaxing both properties simultaneously. We introduce College-Envy-Freeness up to k students (CEF-k) as a relaxed notion of fairness, and Vacant-seat Claim up to l colleges (VC-l) as a relaxed notion of non-wastefulness. We provide a mechanism that satisfies both CEF-k and strategy-proofness (SP). Furthermore, we show that, in a matching market with n students and n schools, for some values of k, the proposed strategy-proof mechanism simultaneously satisfies CEF-k and VC-(n-k-1).