Improved Maximin Guarantees for Subadditive and Fractionally Subadditive Fair Allocation Problem

In this work, we study the maximin share fairness notion for allocation of indivisible goods in the subadditive and fractionally subadditive settings. While previous work refutes the possibility of obtaining an allocation which is better than 1/2-MMS, the only positive result for the subadditive setting states that when the number of items is equal to m, there always exists an Ω(1/log m)-allocation. Since the number of items may be larger than the number of agents (n), such a bound can only imply a weak bound of Ω(1/(n log n))-MMS allocation in general.

In this work, we improve this gap exponentially to an Ω(1/(log n log log n))-MMS guarantee. In addition to this, we prove that when the valuation functions are fractionally subadditive, a 1/4.6-MMS allocation is guaranteed to exist. This also improves upon the previous bound of 1/5-MMS guarantee for the fractionally subadditive setting.