Beating the Logarithmic Barrier for the Subadditive Maximin Share Problem

We study the problem of fair allocation of indivisible goods for subadditive agents. While constant-$\mathsf{\text{MMS}}$ bounds have been given for additive and fractionally subadditive agents, the best existential bound for the case of subadditive agents is $1\mathrm{/}O(\log n\log \log n)$. In this work, we improve this bound to a $1\mathrm{/}O((\log \log n{)}^2)$-$\mathsf{\text{MMS}}$ guarantee. To this end, we introduce new matching techniques and rounding methods for subadditive valuations that we believe are of independent interest and will find their applications in future work.