PMMS Allocations Need Not Exist for 3 Agents with Additive Valuations

Impact Assessment

Core Contribution. This note resolves a well-defined open problem in fair division: whether pairwise maximin share (PMMS) allocations always exist for indivisible goods under additive valuations. The answer is negative. The paper exhibits a concrete counterexample with only n=3 agents and m=9 goods, provides a hand-checkable proof of nonexistence, and separately establishes an approximation barrier showing that α-PMMS cannot be guaranteed for α > 78/79 ≈ 0.987. The existence question was prominent — listed as Open Problem 8 in the Amanatidis et al. (2023) survey and among 24 questions in the econcs-bench collection — and PMMS is of special interest because (under positive values) it is stronger than EFX, "arguably the largest open question in fair division." The result is sharp in a meaningful sense: PMMS is known to exist for m ≤ n+2, coincides with MMS for n=2 (solvable by cut-and-choose), so n=3 is the minimal agent count for such an impossibility.

Methodological Rigor. This is a strong point. The nonexistence claim is backed two ways: a carefully structured human-readable proof (Theorem 1, Lemmas 1–2) that uses high-level arguments — every agent gets exactly one large good and at least one small good — to prune the case analysis, and an independent exhaustive computer enumeration over all 3⁹ ≈ 20,000 allocations using exact fractional arithmetic (avoiding floating-point pitfalls). The code is included and publicly posted. The dual certification (analytic + computational, exact) makes the central claim essentially incontrovertible. The approximation bound is likewise computationally certified.

Potential Impact. The result definitively redirects a strand of research: the community can stop seeking PMMS existence proofs for additive valuations and instead focus on approximation guarantees (the best known is ≈0.781-PMMS) or relaxations such as epistemic PMMS (which the author notes *does* exist for 3 additive agents). This is genuine knowledge that changes what problems are worth pursuing. That said, impossibility results built around a single opaque instance have inherently limited extensibility — the author candidly concedes "the chances of people building on the proof of nonexistence for a concrete counterexample instance seem quite limited," and that the instance remains "mostly opaque" despite the clean write-up. The most enduring citations will likely be to the *fact* rather than the technique.

A notable secondary contribution is the transparent documentation that the counterexample was found "largely autonomously" by an LLM (GPT-6 Astra / ChatGPT), with the human role being simplification, verification, and exposition. As one of the earliest documented cases of an LLM resolving a research-level open problem in combinatorial mathematics, this meta-narrative may draw citations from the rapidly growing "AI-for-mathematics" community beyond fair division proper.

Timeliness & Relevance. Highly timely on two axes. The existence question was recently and explicitly flagged as open in surveys and benchmarks, and a concurrent paper (Byrka et al. 2026) settled the easier monotone-valuation case — this note closes the harder additive case. The AI-discovery angle is also of the moment.

Strengths & Limitations.

Other observations. The comparison to MMS is intriguing: the first MMS counterexample was also n=3, m=12 (later reduced to n=3, m=9), mirroring the trajectory here, and the author speculates about a deeper connection — an open direction that could seed follow-up. The contrast with EFX (exists for 3 agents) and epistemic PMMS (exists for 3 additive agents) sharpens the theoretical landscape and is itself a useful conceptual takeaway.

Overall, this is a rigorous, cleanly executed, and definitive resolution of a recognized open problem — high-value and reliable, but bounded in downstream extensibility by its nature as a single-instance impossibility. Its impact is amplified modestly by timeliness and the AI-discovery meta-story.