Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations

We consider the problem of guaranteeing a fraction of the maximin-share (MMS) when allocating a set of indivisible items to a set of agents with fractionally subadditive (XOS) valuations. For XOS valuations, it has been previously shown that for some instances no allocation can guarantee a fraction better than $1/2$ of the maximin-share to all the agents. Also, a deterministic allocation exists that guarantees $0.219225$ of the maximin-share to each agent. Our results pertain to deterministic and randomized allocations. On the deterministic side, we improve the best approximation guarantee for fractionally subadditive valuations to $3/13 = 0.230769$. We develop new ideas for allocating large items which might be of independent interest. Furthermore, we investigate randomized algorithms and best-of-both-worlds fairness guarantees. We propose a randomized allocation that is $1/4$-MMS ex-ante and $1/8$-MMS ex-post for XOS valuations. Moreover, we prove an upper bound of $3/4$ on the ex-ante guarantee for this class of valuations.