Stable Matchings in Practice: A Constraint Programming Approach
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929210332807168 |
|---|---|
| author | Sun, Zhaohong Yamada, Naoyuki Takenami, Yoshihiro Moriwaki, Daisuke Yokoo, Makoto |
| author_facet | Sun, Zhaohong Yamada, Naoyuki Takenami, Yoshihiro Moriwaki, Daisuke Yokoo, Makoto |
| contents | We study a practical two-sided matching problem of allocating children to daycare centers, which has significant social implications. We are cooperating with several municipalities in Japan and our goal is to devise a reliable and trustworthy clearing algorithm to deal with the problem. In this paper, we describe the design of our new algorithm that minimizes the number of unmatched children while ensuring stability. We evaluate our algorithm using real-life data sets, and experimental results demonstrate that our algorithm surpasses the commercial software that currently dominates the market in terms of both the number of matched children and the number of blocking coalitions (measuring stability). Our findings have been reported to local governments, and some are considering adopting our proposed algorithm in the near future, instead of the existing solution. Moreover, our model and algorithm have broader applicability to other important matching markets, such as hospital-doctor matching with couples and school choice with siblings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_07761 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Stable Matchings in Practice: A Constraint Programming Approach Sun, Zhaohong Yamada, Naoyuki Takenami, Yoshihiro Moriwaki, Daisuke Yokoo, Makoto Computer Science and Game Theory 91B68 F.2; I.2 We study a practical two-sided matching problem of allocating children to daycare centers, which has significant social implications. We are cooperating with several municipalities in Japan and our goal is to devise a reliable and trustworthy clearing algorithm to deal with the problem. In this paper, we describe the design of our new algorithm that minimizes the number of unmatched children while ensuring stability. We evaluate our algorithm using real-life data sets, and experimental results demonstrate that our algorithm surpasses the commercial software that currently dominates the market in terms of both the number of matched children and the number of blocking coalitions (measuring stability). Our findings have been reported to local governments, and some are considering adopting our proposed algorithm in the near future, instead of the existing solution. Moreover, our model and algorithm have broader applicability to other important matching markets, such as hospital-doctor matching with couples and school choice with siblings. |
| title | Stable Matchings in Practice: A Constraint Programming Approach |
| topic | Computer Science and Game Theory 91B68 F.2; I.2 |
| url | https://arxiv.org/abs/2401.07761 |