Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations
share
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.
READ FULL TEXT