TY - JOUR

T1 - Fairness and Efficiency Trade-off in Two-Sided Matching

AU - Cho, Sung Ho

AU - Kimura, Kei

AU - Liu, Kiki

AU - Liu, Kwei Guu

AU - Liu, Zhengjie

AU - Sun, Zhaohong

AU - Yahiro, Kentaro

AU - Yokoo, Makoto

N1 - Publisher Copyright:
© 2024 International Foundation for Autonomous Agents and Multiagent Systems.

PY - 2024

Y1 - 2024

N2 - The theory of two-sided matching has been extensively developed and applied to many real-life application domains. As the theory has been applied to increasingly diverse types of environments, researchers and practitioners have encountered various forms of distributional constraints. As a mechanism can handle a more general class of constraints, we can assign students more flexibly to colleges to increase students' welfare. However, it turns out that there exists a trade-off between students' welfare (efficiency) and fairness (which means no student has justified envy). Furthermore, this trade-off becomes sharper as the class of constraints becomes more general. The first contribution of this paper is to clarify the boundary on whether a strategyproof and fair mechanism can satisfy certain efficiency properties for each class of constraints. Our second contribution is to establish a weaker fairness requirement called envy-freeness up to k peers (EF-k), which is inspired by a similar concept used in the fair division of indivisible items. EF-k guarantees that each student has justified envy towards at most k students. By varying k, EF-k can represent different levels of fairness. We investigate theoretical properties associated with EF-k. Furthermore, we develop two contrasting strategyproof mechanisms that work for general hereditary constraints, i.e., one mechanism can guarantee a strong efficiency requirement, while the other can guarantee EF-k for any fixed k. We evaluate the performance of these mechanisms through computer simulation.

AB - The theory of two-sided matching has been extensively developed and applied to many real-life application domains. As the theory has been applied to increasingly diverse types of environments, researchers and practitioners have encountered various forms of distributional constraints. As a mechanism can handle a more general class of constraints, we can assign students more flexibly to colleges to increase students' welfare. However, it turns out that there exists a trade-off between students' welfare (efficiency) and fairness (which means no student has justified envy). Furthermore, this trade-off becomes sharper as the class of constraints becomes more general. The first contribution of this paper is to clarify the boundary on whether a strategyproof and fair mechanism can satisfy certain efficiency properties for each class of constraints. Our second contribution is to establish a weaker fairness requirement called envy-freeness up to k peers (EF-k), which is inspired by a similar concept used in the fair division of indivisible items. EF-k guarantees that each student has justified envy towards at most k students. By varying k, EF-k can represent different levels of fairness. We investigate theoretical properties associated with EF-k. Furthermore, we develop two contrasting strategyproof mechanisms that work for general hereditary constraints, i.e., one mechanism can guarantee a strong efficiency requirement, while the other can guarantee EF-k for any fixed k. We evaluate the performance of these mechanisms through computer simulation.

UR - http://www.scopus.com/inward/record.url?scp=85196374539&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85196374539&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85196374539

SN - 1548-8403

VL - 2024-May

SP - 372

EP - 380

JO - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

JF - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

T2 - 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2024

Y2 - 6 May 2024 through 10 May 2024

ER -