Fair allocations with subadditive and XOS valuations
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917956208820224 |
|---|---|
| author | Feige, Uriel Grinberg, Vadim |
| author_facet | Feige, Uriel Grinberg, Vadim |
| contents | We consider the problem of fair allocation of $m$ indivisible goods to $n$ agents with either subadditive or XOS valuations, in the arbitrary entitlement case. As fairness notions, we consider the anyprice share (APS) ex-post, and the maximum expectation share (MES) ex-ante.
We observe that there are randomized allocations that ex-ante are at least $\frac{1}{2}$-MES in the subadditive case and $(1-\frac{1}{e})$-MES in the XOS case. Our more difficult results concern ex-post guarantees. We show that $(1 - o(1))\frac{\log\log m}{\log m}$-APS allocations exist in the subadditive case, and $\frac{1}{6}$-APS allocations exist in the XOS case. For the special case of equal entitlements, we show $\frac{4}{17}$-APS allocations for XOS.
Our results are the first for subadditive and XOS valuations in the arbitrary entitlement case, and also improve over the previous best results for the equal entitlement case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10513 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fair allocations with subadditive and XOS valuations Feige, Uriel Grinberg, Vadim Computer Science and Game Theory 68Q25 F.2.2 We consider the problem of fair allocation of $m$ indivisible goods to $n$ agents with either subadditive or XOS valuations, in the arbitrary entitlement case. As fairness notions, we consider the anyprice share (APS) ex-post, and the maximum expectation share (MES) ex-ante. We observe that there are randomized allocations that ex-ante are at least $\frac{1}{2}$-MES in the subadditive case and $(1-\frac{1}{e})$-MES in the XOS case. Our more difficult results concern ex-post guarantees. We show that $(1 - o(1))\frac{\log\log m}{\log m}$-APS allocations exist in the subadditive case, and $\frac{1}{6}$-APS allocations exist in the XOS case. For the special case of equal entitlements, we show $\frac{4}{17}$-APS allocations for XOS. Our results are the first for subadditive and XOS valuations in the arbitrary entitlement case, and also improve over the previous best results for the equal entitlement case. |
| title | Fair allocations with subadditive and XOS valuations |
| topic | Computer Science and Game Theory 68Q25 F.2.2 |
| url | https://arxiv.org/abs/2503.10513 |