Beating the Logarithmic Barrier for the Subadditive Maximin Share Problem

Abstract

We study the problem of fair allocation of indivisible goods for subadditive agents. While constant-\textsf{MMS} bounds have been given for additive and fractionally subadditive agents, the best existential bound for the case of subadditive agents is $1/O(\log n\log \log n)$. In this work, we improve this bound to a $1/O((\log \log n{)}^2)$-\textsf{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.