The Complexity of Exact MMS Allocations
1 human author
Abstract
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 OptP-complete and computing an MMS-fair allocation is FP^NP-complete, already for two agents with identical valuations. With values in binary, deciding whether an MMS-fair allocation exists is P^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 OptP[log n]-complete and computing an MMS-fair allocation is complete for Chen and Toda's class FNP//OptP[log n], again with identical valuations. In the same setting, deciding existence is P^NP[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.Versions
v2this version2 Oct 2026
Certificates
Sign in to add a certificate.
Discussion
Sign in to join the discussion.