Polytime Algorithms for One-to-Many Matching Games
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913951449612288 |
|---|---|
| author | Garrido-Lucero, Felipe Laraki, Rida |
| author_facet | Garrido-Lucero, Felipe Laraki, Rida |
| contents | Matching games is a novel matching model introduced by Garrido-Lucero and Laraki, in which agents' utilities are endogenously determined as the outcome of a strategic game they play simultaneously with the matching process. Matching games encompass most one-to-one matching market models and reinforce the classical notion of pairwise stability by analyzing their robustness to unilateral deviations within games. In this article, we extend the model to the one-to-many setting, where hospitals can be matched to multiple doctors, and their utility is given by the sum of their game outcomes. We adapt the deferred acceptance with competitions algorithm and the renegotiation process to this new framework and prove that both are polynomial whenever couples play bi-matrix games in mixed strategies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2107_07440 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Polytime Algorithms for One-to-Many Matching Games Garrido-Lucero, Felipe Laraki, Rida Computer Science and Game Theory Matching games is a novel matching model introduced by Garrido-Lucero and Laraki, in which agents' utilities are endogenously determined as the outcome of a strategic game they play simultaneously with the matching process. Matching games encompass most one-to-one matching market models and reinforce the classical notion of pairwise stability by analyzing their robustness to unilateral deviations within games. In this article, we extend the model to the one-to-many setting, where hospitals can be matched to multiple doctors, and their utility is given by the sum of their game outcomes. We adapt the deferred acceptance with competitions algorithm and the renegotiation process to this new framework and prove that both are polynomial whenever couples play bi-matrix games in mixed strategies. |
| title | Polytime Algorithms for One-to-Many Matching Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2107.07440 |