Maximum Welfare Allocations under Quantile Valuations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915978396303360 |
|---|---|
| author | Aziz, Haris Narang, Shivika Suzuki, Mashbat |
| author_facet | Aziz, Haris Narang, Shivika Suzuki, Mashbat |
| contents | We propose a new model for aggregating preferences over a set of indivisible items based on a quantile value. In this model, each agent is endowed with a specific quantile, and the value of a given bundle is defined by the corresponding quantile of the individual values of the items within it. Our model captures the diverse ways in which agents may perceive a bundle, even when they agree on the values of individual items. It enables richer behavioral modeling that cannot be easily captured by additive valuation functions. We study the problem of maximizing utilitarian and egalitarian welfare within the quantile-based valuation setting. For each of the welfare functions, we analyze the complexity of the objectives. Interestingly, our results show that the complexity of both objectives varies significantly depending on whether the allocation is required to be balanced. We provide near-optimal approximation algorithms for utilitarian welfare, and for egalitarian welfare, we present exact algorithms whenever possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_17869 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximum Welfare Allocations under Quantile Valuations Aziz, Haris Narang, Shivika Suzuki, Mashbat Computer Science and Game Theory We propose a new model for aggregating preferences over a set of indivisible items based on a quantile value. In this model, each agent is endowed with a specific quantile, and the value of a given bundle is defined by the corresponding quantile of the individual values of the items within it. Our model captures the diverse ways in which agents may perceive a bundle, even when they agree on the values of individual items. It enables richer behavioral modeling that cannot be easily captured by additive valuation functions. We study the problem of maximizing utilitarian and egalitarian welfare within the quantile-based valuation setting. For each of the welfare functions, we analyze the complexity of the objectives. Interestingly, our results show that the complexity of both objectives varies significantly depending on whether the allocation is required to be balanced. We provide near-optimal approximation algorithms for utilitarian welfare, and for egalitarian welfare, we present exact algorithms whenever possible. |
| title | Maximum Welfare Allocations under Quantile Valuations |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.17869 |