hide
Free keywords:
Computer Science, Computer Science and Game Theory, cs.GT
Abstract:
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.
