On MMS, APS and XOS
For researchers in fair division, this provides a better MMS approximation for XOS valuations, though the improvement is incremental and only applies to large n.
The paper improves the approximation ratio for maximin share (MMS) allocations under XOS valuations from 4/17 to over 11/40 for sufficiently large numbers of agents, by first analyzing the gap between anyprice share (APS) and MMS for identical valuations and then extending the algorithm to heterogeneous valuations.
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$.