Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations

We consider the problem of guaranteeing 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 maximin-share to all the agents. Also, a deterministic allocation exists that guarantees 0.219225 of the maximin-share of each agent. Our results involve both deterministic and randomized allocations. On the deterministic side, we improve the best approximation guarantee for fractionally subadditive valuations to 3/13 0.230769 .