Improved Maximin Share Guarantee for Additive 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_ | 1866914089454796800 |
|---|---|
| author | Heidari, Ehsan Kaviani, Alireza Seddighin, Masoud Shahrezaei, AmirMohammad |
| author_facet | Heidari, Ehsan Kaviani, Alireza Seddighin, Masoud Shahrezaei, AmirMohammad |
| contents | The maximin share ($\textsf{MMS}$) is the most prominent share-based fairness notion in the fair allocation of indivisible goods. Recent years have seen significant efforts to improve the approximation guarantees for $\textsf{MMS}$ for different valuation classes, particularly for additive valuations. For the additive setting, it has been shown that for some instances, no allocation can guarantee a factor better than $1-\tfrac{1}{n^4}$ of maximin share value to all agents. However, the best currently known algorithm achieves an approximation guarantee of $\tfrac{3}{4} + \tfrac{3}{3836}$ for $\textsf{MMS}$. In this work, we narrow this gap and improve the best-known approximation guarantee for $\textsf{MMS}$ to $\tfrac{10}{13}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_10423 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Maximin Share Guarantee for Additive Valuations Heidari, Ehsan Kaviani, Alireza Seddighin, Masoud Shahrezaei, AmirMohammad Computer Science and Game Theory The maximin share ($\textsf{MMS}$) is the most prominent share-based fairness notion in the fair allocation of indivisible goods. Recent years have seen significant efforts to improve the approximation guarantees for $\textsf{MMS}$ for different valuation classes, particularly for additive valuations. For the additive setting, it has been shown that for some instances, no allocation can guarantee a factor better than $1-\tfrac{1}{n^4}$ of maximin share value to all agents. However, the best currently known algorithm achieves an approximation guarantee of $\tfrac{3}{4} + \tfrac{3}{3836}$ for $\textsf{MMS}$. In this work, we narrow this gap and improve the best-known approximation guarantee for $\textsf{MMS}$ to $\tfrac{10}{13}$. |
| title | Improved Maximin Share Guarantee for Additive Valuations |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2510.10423 |