Whoever Said Money Won't Solve All Your Problems? Weighted Envy-free Allocation with Subsidy
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917946823016448 |
|---|---|
| author | Elmalem, Noga Klein Aziz, Haris Gonen, Rica Huang, Xin Kimura, Kei Saha, Indrajit Segal-Halevi, Erel Sun, Zhaohong Suzuki, Mashbat Yokoo, Makoto |
| author_facet | Elmalem, Noga Klein Aziz, Haris Gonen, Rica Huang, Xin Kimura, Kei Saha, Indrajit Segal-Halevi, Erel Sun, Zhaohong Suzuki, Mashbat Yokoo, Makoto |
| contents | We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where each agent deems their allocated portion relative to their entitlement at least as favorable as any others relative to their own. Often, achieving WEF necessitates monetary transfers, which can be modeled as third-party subsidies. The goal is to attain WEF with bounded subsidies.
Previous work relied on characterizations of unweighted envy-freeness (EF), that fail in the weighted setting. This makes our new setting challenging. We present polynomial-time algorithms that compute WEF allocations with a guaranteed upper bound on total subsidy for monotone valuations and various subclasses thereof.
We also present an efficient algorithm to compute a fair allocation of items and money, when the budget is not enough to make the allocation WEF. This algorithm is new even for the unweighted setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09006 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Whoever Said Money Won't Solve All Your Problems? Weighted Envy-free Allocation with Subsidy Elmalem, Noga Klein Aziz, Haris Gonen, Rica Huang, Xin Kimura, Kei Saha, Indrajit Segal-Halevi, Erel Sun, Zhaohong Suzuki, Mashbat Yokoo, Makoto Computer Science and Game Theory We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where each agent deems their allocated portion relative to their entitlement at least as favorable as any others relative to their own. Often, achieving WEF necessitates monetary transfers, which can be modeled as third-party subsidies. The goal is to attain WEF with bounded subsidies. Previous work relied on characterizations of unweighted envy-freeness (EF), that fail in the weighted setting. This makes our new setting challenging. We present polynomial-time algorithms that compute WEF allocations with a guaranteed upper bound on total subsidy for monotone valuations and various subclasses thereof. We also present an efficient algorithm to compute a fair allocation of items and money, when the budget is not enough to make the allocation WEF. This algorithm is new even for the unweighted setting. |
| title | Whoever Said Money Won't Solve All Your Problems? Weighted Envy-free Allocation with Subsidy |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.09006 |