Stable Matching with Predictions: Robustness and Efficiency under Pruned Preferences
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910008915001344 |
|---|---|
| author | McCauley, Samuel Moseley, Benjamin Niaparast, Helia Singh, Shikha |
| author_facet | McCauley, Samuel Moseley, Benjamin Niaparast, Helia Singh, Shikha |
| contents | In this paper, we study the fundamental problem of finding a stable matching in two-sided matching markets. In the classic variant, it is assumed that both sides of the market submit a ranked list of all agents on the other side. However, in large matching markets such as the National Resident Matching Program (NRMP), it is infeasible for hospitals to interview or mutually rank each resident. In this paper, we study the stable matching problem with truncated preference lists. In particular, we assume that, based on historical datasets, each hospital has a predicted rank of its likely match and only ranks residents within a bounded interval around that prediction.
We use the algorithms-with-predictions framework and show that the classic deferred-acceptance (DA) algorithm used to compute stable matchings is robust to such truncation. We present two algorithms and theoretically and empirically evaluate their performance. Our results show that even with reasonably accurate predictions, it is possible to significantly cut down on both instance size (the length of preference lists) as well as the number of proposals made. These results explain the practical success of the DA algorithm and connect market design to the emerging theory of algorithms with predictions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_02254 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Stable Matching with Predictions: Robustness and Efficiency under Pruned Preferences McCauley, Samuel Moseley, Benjamin Niaparast, Helia Singh, Shikha Computer Science and Game Theory Data Structures and Algorithms In this paper, we study the fundamental problem of finding a stable matching in two-sided matching markets. In the classic variant, it is assumed that both sides of the market submit a ranked list of all agents on the other side. However, in large matching markets such as the National Resident Matching Program (NRMP), it is infeasible for hospitals to interview or mutually rank each resident. In this paper, we study the stable matching problem with truncated preference lists. In particular, we assume that, based on historical datasets, each hospital has a predicted rank of its likely match and only ranks residents within a bounded interval around that prediction. We use the algorithms-with-predictions framework and show that the classic deferred-acceptance (DA) algorithm used to compute stable matchings is robust to such truncation. We present two algorithms and theoretically and empirically evaluate their performance. Our results show that even with reasonably accurate predictions, it is possible to significantly cut down on both instance size (the length of preference lists) as well as the number of proposals made. These results explain the practical success of the DA algorithm and connect market design to the emerging theory of algorithms with predictions. |
| title | Stable Matching with Predictions: Robustness and Efficiency under Pruned Preferences |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.02254 |