A d-multi-allocation with subadditive valuations can be converted to an allocation losing only a factor of about d, yielding an Omega(1/log log n)-MMS guarantee.
Beating the Logarithmic Barrier for the Subadditive Maximin Share Problem
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
cs.GT 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
From multi-allocations to allocations, with subadditive valuations
A d-multi-allocation with subadditive valuations can be converted to an allocation losing only a factor of about d, yielding an Omega(1/log log n)-MMS guarantee.