Finding Pareto frontier for one-sided matching
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913121722957824 |
|---|---|
| author | Dodda, Bhavik Shakya, Garima |
| author_facet | Dodda, Bhavik Shakya, Garima |
| contents | One-sided matching problems with ordinal preferences, such as hostel room allocation, are commonly solved using the Top Trading Cycles (TTC) mechanism, which guarantees Pareto-optimal (PO) outcomes. However, TTC does not yield a unique solution: multiple PO allocations may exist, and many distinct initial endowments can converge to the same outcome. Focusing on a single TTC result obscures the structure of the Pareto-efficient frontier and limits principled secondary optimization over fairness or welfare objectives. Therefore, the goal is to find the entire set of PO allocations for a given preference profile. We propose the Inverse Top Trading Cycles Enumeration Algorithm (ITEA), a novel method that efficiently computes the complete set of Pareto-optimal allocations in one-sided matching problems. We prove the soundness and completeness of the proposed algorithm and analyze its computational complexity. Although in the worst case, there can be $n!$ PO allocations; however, compared to the brute-force approach, our algorithm reduces time complexity when there are fewer PO allocations. Empirical results demonstrate substantial reductions in redundant TTC computations compared to brute-force enumeration, enabling efficient characterization of the Pareto frontier. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_21306 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Finding Pareto frontier for one-sided matching Dodda, Bhavik Shakya, Garima Computer Science and Game Theory One-sided matching problems with ordinal preferences, such as hostel room allocation, are commonly solved using the Top Trading Cycles (TTC) mechanism, which guarantees Pareto-optimal (PO) outcomes. However, TTC does not yield a unique solution: multiple PO allocations may exist, and many distinct initial endowments can converge to the same outcome. Focusing on a single TTC result obscures the structure of the Pareto-efficient frontier and limits principled secondary optimization over fairness or welfare objectives. Therefore, the goal is to find the entire set of PO allocations for a given preference profile. We propose the Inverse Top Trading Cycles Enumeration Algorithm (ITEA), a novel method that efficiently computes the complete set of Pareto-optimal allocations in one-sided matching problems. We prove the soundness and completeness of the proposed algorithm and analyze its computational complexity. Although in the worst case, there can be $n!$ PO allocations; however, compared to the brute-force approach, our algorithm reduces time complexity when there are fewer PO allocations. Empirical results demonstrate substantial reductions in redundant TTC computations compared to brute-force enumeration, enabling efficient characterization of the Pareto frontier. |
| title | Finding Pareto frontier for one-sided matching |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2604.21306 |