← all papers · overview

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)²)-\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.

Related papers

Ranked by semantic similarity — how closely each paper's abstract matches this one (100% = near-identical topic).