Tree Splitting Based Rounding Scheme for Weighted Proportional Allocations with Subsidy
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914749193650176 |
|---|---|
| author | Wu, Xiaowei Zhou, Shengwei |
| author_facet | Wu, Xiaowei Zhou, Shengwei |
| contents | We consider the problem of allocating $m$ indivisible items to a set of $n$ heterogeneous agents, aiming at computing a proportional allocation by introducing subsidy (money). It has been shown by Wu et al. (WINE 2023) that when agents are unweighted a total subsidy of $n/4$ suffices (assuming that each item has value/cost at most $1$ to every agent) to ensure proportionality. When agents have general weights, they proposed an algorithm that guarantees a weighted proportional allocation requiring a total subsidy of $(n-1)/2$, by rounding the fractional bid-and-take algorithm. In this work, we revisit the problem and the fractional bid-and-take algorithm. We show that by formulating the fractional allocation returned by the algorithm as a directed tree connecting the agents and splitting the tree into canonical components, there is a rounding scheme that requires a total subsidy of at most $n/3 - 1/6$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07707 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tree Splitting Based Rounding Scheme for Weighted Proportional Allocations with Subsidy Wu, Xiaowei Zhou, Shengwei Computer Science and Game Theory We consider the problem of allocating $m$ indivisible items to a set of $n$ heterogeneous agents, aiming at computing a proportional allocation by introducing subsidy (money). It has been shown by Wu et al. (WINE 2023) that when agents are unweighted a total subsidy of $n/4$ suffices (assuming that each item has value/cost at most $1$ to every agent) to ensure proportionality. When agents have general weights, they proposed an algorithm that guarantees a weighted proportional allocation requiring a total subsidy of $(n-1)/2$, by rounding the fractional bid-and-take algorithm. In this work, we revisit the problem and the fractional bid-and-take algorithm. We show that by formulating the fractional allocation returned by the algorithm as a directed tree connecting the agents and splitting the tree into canonical components, there is a rounding scheme that requires a total subsidy of at most $n/3 - 1/6$. |
| title | Tree Splitting Based Rounding Scheme for Weighted Proportional Allocations with Subsidy |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2404.07707 |