Beating the Logarithmic Barrier for the Subadditive Maximin Share Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910991676080128 |
|---|---|
| author | Seddighin, Masoud Seddighin, Saeed |
| author_facet | Seddighin, Masoud Seddighin, Saeed |
| contents | We study the problem of fair allocation of indivisible goods for subadditive agents. While constant-\textsf{MMS} bounds have been given for additive and fractionally subadditive agents, the best existential bound for the case of subadditive agents is $1/O(\log n \log \log n)$. In this work, we improve this bound to a $1/O((\log \log n)^2)$-\textsf{MMS} guarantee. To this end, we introduce new matching techniques and rounding methods for subadditive valuations that we believe are of independent interest and will find their applications in future work. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_05613 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beating the Logarithmic Barrier for the Subadditive Maximin Share Problem Seddighin, Masoud Seddighin, Saeed Computer Science and Game Theory We study the problem of fair allocation of indivisible goods for subadditive agents. While constant-\textsf{MMS} bounds have been given for additive and fractionally subadditive agents, the best existential bound for the case of subadditive agents is $1/O(\log n \log \log n)$. In this work, we improve this bound to a $1/O((\log \log n)^2)$-\textsf{MMS} guarantee. To this end, we introduce new matching techniques and rounding methods for subadditive valuations that we believe are of independent interest and will find their applications in future work. |
| title | Beating the Logarithmic Barrier for the Subadditive Maximin Share Problem |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2506.05613 |