Strategyproof Maximum Matching under Dichotomous Agent Preferences
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916613875302400 |
|---|---|
| author | Aziz, Haris Islam, Md. Shahidul Pápai, Szilvia |
| author_facet | Aziz, Haris Islam, Md. Shahidul Pápai, Szilvia |
| contents | We consider a two-sided matching problem in which the agents on one side have dichotomous preferences and the other side representing institutions has strict preferences (priorities). It captures several important applications in matching market design in which the agents are only interested in getting matched to an acceptable institution. These include centralized daycare assignment and healthcare rationing. We present a compelling new mechanism that satisfies many prominent and desirable properties including individual rationality, maximum size, fairness, Pareto-efficiency on both sides, strategyproofness on both sides, non-bossiness and having polynomial time running time. As a result, we answer an open problem whether there exists a mechanism that is agent-strategyproof, maximum, fair and non-bossy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09962 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Strategyproof Maximum Matching under Dichotomous Agent Preferences Aziz, Haris Islam, Md. Shahidul Pápai, Szilvia Computer Science and Game Theory Theoretical Economics 91A12, 68Q15 F.2; J.4 We consider a two-sided matching problem in which the agents on one side have dichotomous preferences and the other side representing institutions has strict preferences (priorities). It captures several important applications in matching market design in which the agents are only interested in getting matched to an acceptable institution. These include centralized daycare assignment and healthcare rationing. We present a compelling new mechanism that satisfies many prominent and desirable properties including individual rationality, maximum size, fairness, Pareto-efficiency on both sides, strategyproofness on both sides, non-bossiness and having polynomial time running time. As a result, we answer an open problem whether there exists a mechanism that is agent-strategyproof, maximum, fair and non-bossy. |
| title | Strategyproof Maximum Matching under Dichotomous Agent Preferences |
| topic | Computer Science and Game Theory Theoretical Economics 91A12, 68Q15 F.2; J.4 |
| url | https://arxiv.org/abs/2502.09962 |