On MMS, APS and XOS
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917476819795968 |
|---|---|
| author | Feige, Uriel Grinberg, Vadim |
| author_facet | Feige, Uriel Grinberg, Vadim |
| contents | We consider allocations of a set of $m$ indivisible goods to $n$ agents of equal entitlements that have valuations from the class XOS. A previous sequence of works showed allocations that obtain an $α$-approximation for the maximin share (MMS), for values of $α$ that gradually approach $\frac{1}{4}$ from below (the currently known ratio is $\frac{4}{17}$). In this work we attempt to obtain ratios better than $\frac{1}{4}$, and manage to do so for sufficiently large $n$. Our methodology is to first investigate the gap between the anyprice share (APS) and the MMS when all agents have the same XOS valuations, for which we design an allocation algorithm and prove that each agent receives at least $α> \frac{11}{40}$ times the APS. Then, we derive inspiration from this algorithm, and modify it so that it applies also when agents have different XOS valuations. Using this modified version, we show that for some sufficiently large $n_0$, there is an $α$-MMS allocation (in fact, an $α$-APS allocation) for every $n \geq n_0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_08859 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On MMS, APS and XOS Feige, Uriel Grinberg, Vadim Computer Science and Game Theory 68Q25 F.2.2 We consider allocations of a set of $m$ indivisible goods to $n$ agents of equal entitlements that have valuations from the class XOS. A previous sequence of works showed allocations that obtain an $α$-approximation for the maximin share (MMS), for values of $α$ that gradually approach $\frac{1}{4}$ from below (the currently known ratio is $\frac{4}{17}$). In this work we attempt to obtain ratios better than $\frac{1}{4}$, and manage to do so for sufficiently large $n$. Our methodology is to first investigate the gap between the anyprice share (APS) and the MMS when all agents have the same XOS valuations, for which we design an allocation algorithm and prove that each agent receives at least $α> \frac{11}{40}$ times the APS. Then, we derive inspiration from this algorithm, and modify it so that it applies also when agents have different XOS valuations. Using this modified version, we show that for some sufficiently large $n_0$, there is an $α$-MMS allocation (in fact, an $α$-APS allocation) for every $n \geq n_0$. |
| title | On MMS, APS and XOS |
| topic | Computer Science and Game Theory 68Q25 F.2.2 |
| url | https://arxiv.org/abs/2605.08859 |