Pairwise Maximin Share Allocations Need Not Exist

• PMMS asks each agent to compare her bundle with the worst share she could secure by repartitioning her bundle and another agent’s into two parts.This imports the pairwise cut-and-choose benchmark into a multi-agent allocation.Source: §1 · p. 1
• PMMS is procedurally interpretable and symmetric across pairs, while evaluating fairness from each agent’s cardinal perspective.The benchmark remains meaningful when exact envy-freeness is impossible for indivisible goods.Source: §1 · p. 1
• Prior work left the additive exact case open despite a 0.781 existential guarantee and a counterexample with two nonadditive valuations (Byrka et al., 2026).Source: §1 · p. 1
• A four-agent instance with strictly positive additive valuations has no complete PMMS allocation, resolving exact existence for additive valuations in the negative.Four is the smallest number for which additive nonexistence is currently known; the three-agent additive case remains open.Source: §1 · p. 2
• For strictly positive additive valuations, PMMS implies EFX, but EFX does not imply PMMS; the result is not an EFX counterexample.Thus the theorem rules out PMMS as a route to proving universal additive EFX existence.Source: §1 · pp. 1–2

• Caragiannis et al. (2019) introduced PMMS alongside EFX in work on maximum Nash welfare allocations; Amanatidis et al. (2023) survey fairness notions for indivisible goods.Source: §2 · p. 2
• For positive additive valuations, every EFX allocation is 2/3-PMMS and every EF1 allocation is 1/2-PMMS, with both implications tight (Amanatidis et al., 2018).Source: §2 · p. 2
• For additive negative valuations (chores), EFX and therefore PMMS allocations need not exist for any n ≥ 4 (He and Tao, 2026).Source: §2 · p. 2
• Approximate results include a 0.781 existential PMMS guarantee, simultaneous fairness guarantees, and efficient guarantees for restricted additive and common-ranking instances.The cited simultaneous guarantees include 0.618-EFX and 0.717-PMMS (Amanatidis et al., 2020); the common-ranking guarantee is 4/5-PMMS (Feldman et al., 2026).Source: §2 · p. 2
• Before this work, the three-agent PMMS counterexample had only one additive valuation; exact PMMS was known in several structured domains and when each good is valued by at most two agents.The three-agent counterexample’s other two valuations were monotone and nonadditive (Byrka et al., 2026).Source: §2 · p. 2

• The model has finite sets of agents and indivisible goods, with nonnegative valuations normalized to zero for the empty bundle.In the counterexample, valuations are additive and strictly positive on every good.Source: §3 · p. 3
• α-PMMS applies a pairwise condition to every distinct agent pair; exact PMMS is α = 1, and a failed condition for an ordered pair is PMMS-envy.Source: §3 · p. 3
• EFX requires each agent’s value for her own bundle to be at least the value of another agent’s bundle after removal of any one good.Under strict positivity, the paper notes no distinction from the convention that checks only goods positively valued by the potentially envious agent.Source: §3 · p. 3

The construction

• The 52 goods comprise MA, MB, MC, and MD classes of sizes 3, 5, 5, and 39, adapting a He and Tao (2026) chore pattern.The construction converts chore costs into values and adds 39 common goods of value 101.Source: §4 · pp. 3, 6
• Writing each good’s value as 101 minus its deficit makes equal-size bundles more valuable when their deficits are smaller.Since total deficit is 100, fewer than one baseline good’s value, any bundle with more goods is strictly more valuable than one with fewer goods.Source: §4 · pp. 3–4

The proof

• Under PMMS, bundle sizes cannot differ by more than one; with 52 goods and four agents, each bundle therefore has 13 goods.The proof also derives a necessary condition: for every ordered pair and every bipartition of their relevant goods, at least one part’s deficit must reach the first agent’s bundle deficit.Source: §4 · p. 4
• No agent can receive two MA-goods, so the three such goods go to distinct agents and one agent receives none.The proof rules out both the ordinary case and the exceptional case by constructing a partition that violates the necessary deficit condition.Source: §4 · pp. 4–5
• For the agent without an MA-good, the proof establishes that her bundle contains at least three MB-goods and three MC-goods.The resulting counts allow the final partition to select three MC-goods and two MB-goods from her bundle.Source: §4 · p. 5

Step 5: the final violating partition

• A partition of S ∪ Yj has both parts’ agent-1 deficits below c1(S), contradicting the necessary PMMS condition for pair (1, j).For T containing three MC-goods and two MB-goods, c1(T) = 23 < 24 ≤ c1(S).Source: §4 · p. 6