Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.01084 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910316158255104 |
|---|---|
| author | Cho, Sung-Ho Kimura, Kei Liu, Kiki Liu, Kwei-guu Liu, Zhengjie Sun, Zhaohong Yahiro, Kentaro Yokoo, Makoto |
| author_facet | Cho, Sung-Ho Kimura, Kei Liu, Kiki Liu, Kwei-guu Liu, Zhengjie Sun, Zhaohong Yahiro, Kentaro Yokoo, Makoto |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_01084 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fairness and efficiency trade-off in two-sided matching Cho, Sung-Ho Kimura, Kei Liu, Kiki Liu, Kwei-guu Liu, Zhengjie Sun, Zhaohong Yahiro, Kentaro Yokoo, Makoto Computer Science and Game Theory 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. |
| title | Fairness and efficiency trade-off in two-sided matching |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2402.01084 |