MMS Approximations Under Additive Leveled Valuations
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916421844336640 |
|---|---|
| author | Afshinmehr, Mahyar Kazemi, Mehrafarin Mehlhorn, Kurt |
| author_facet | Afshinmehr, Mahyar Kazemi, Mehrafarin Mehlhorn, Kurt |
| contents | We study the problem of fairly allocating indivisible goods to a set of agents with additive leveled valuations. A valuation function is called leveled if and only if bundles of larger size have larger value than bundles of smaller size. The economics literature has well studied such valuations.
We use the maximin-share (MMS) and EFX as standard notions of fairness. We show that an algorithm introduced by Christodoulou et al. ([11]) constructs an allocation that is EFX and $\frac{\lfloor \frac{m}{n} \rfloor}{\lfloor \frac{m}{n} \rfloor + 1}\text{-MMS}$. In the paper, it was claimed that the allocation is EFX and $\frac{2}{3}\text{-MMS}$. However, the proof of the MMS-bound is incorrect. We give a counter-example to their proof and then prove a stronger approximation of MMS. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_02274 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | MMS Approximations Under Additive Leveled Valuations Afshinmehr, Mahyar Kazemi, Mehrafarin Mehlhorn, Kurt Computer Science and Game Theory We study the problem of fairly allocating indivisible goods to a set of agents with additive leveled valuations. A valuation function is called leveled if and only if bundles of larger size have larger value than bundles of smaller size. The economics literature has well studied such valuations. We use the maximin-share (MMS) and EFX as standard notions of fairness. We show that an algorithm introduced by Christodoulou et al. ([11]) constructs an allocation that is EFX and $\frac{\lfloor \frac{m}{n} \rfloor}{\lfloor \frac{m}{n} \rfloor + 1}\text{-MMS}$. In the paper, it was claimed that the allocation is EFX and $\frac{2}{3}\text{-MMS}$. However, the proof of the MMS-bound is incorrect. We give a counter-example to their proof and then prove a stronger approximation of MMS. |
| title | MMS Approximations Under Additive Leveled Valuations |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2410.02274 |