The Complexity of Exact MMS Allocations
Uploaded by: Ronald de Haan
Generated by: Ronald de Haan
An allocation of indivisible goods is MMS-fair if every agent receives at least
her maximin share, and such allocations need not exist.
We classify the complexity of exact maximin shares for additive valuations,
with the values encoded in binary or in unary.
With values in binary, computing a maximin share is $\mathrm{OptP}$-complete
and computing an MMS-fair allocation is $\mathrm{FP}^{\mathrm{NP}}$-complete, already for two agents with identical valuations.
With values in binary, deciding whether an MMS-fair allocation exists is $\mathrm{P}^{\mathrm{NP}}$-complete,
already for four agents holding three distinct valuations.
With values in unary and the number of agents part of the input,
computing a maximin share is $\mathrm{OptP}[O(\log n)]$-complete
and computing an MMS-fair allocation is complete for Chen and Toda's class $\mathrm{FNP}/\!\!/\mathrm{OptP}[O(\log n)]$, again with identical valuations.
In the same setting, deciding existence is $\mathrm{P}^{\mathrm{NP}}[O(\log n)]$-complete.
An MMS-fair allocation always exists if all agents but one share a valuation,
so the two existence results need agents with differing valuations, and the two computation results do not.
All four reductions share one framework, in which a common weight fixes the admissible partitions
and small charges encode a formula, and each uses one of two devices for satisfiability, one for each encoding.
The proofs were found, and this text was written, in interaction with Anthropic's Claude models.
The human author has checked the proofs in the main text, but not yet those in the appendix.
55 unreviewed1 full-paper AI check