Source-linked AI summary
PMMS Allocations Need Not Exist for 3 Agents with Additive Valuations
Paul Gölz
TL;DR
Whether PMMS allocations always exist for additive valuations remained an open question. The paper constructs a three-agent, nine-good instance and proves that no PMMS allocation exists. It also notes that this is the smallest agent count for such a nonexistence result, while the proof’s many simultaneous inequalities leave the instance mostly opaque.
Problem
Whether PMMS allocations always exist for additive preferences had remained open.
Source: §1 · p. 1Method
The paper constructs an additive fair-division instance and proves nonexistence by analyzing its possible allocations.
Source: §2 · pp. 2–4Results
The instance with 3 agents and 9 goods has no PMMS allocation.
Source: §2 · p. 2Takeaways & Limitations
Three agents are the smallest number for an additive-valuation PMMS nonexistence result; the author believes 9 goods is minimal or almost minimal.
Source: §4 · p. 8The simultaneous inequalities supporting the nonexistence example still make the instance appear mostly opaque.
Source: AI Usage · p. 9
Abstract
from arXiv · showhide
This note gives an instance demonstrating that the pairwise maximin share (PMMS) property cannot be satisfied by any allocation in certain fair division problems with indivisible goods and additive valuations. The instance requires only $n=3$ agents and $m=9$ goods, and is accompanied by a proof that no PMMS allocation exists. A separate instance shows (certified by exhaustive enumeration with a computer) that PMMS cannot be approximated within a ratio above $78/79 \approx 0.987$.
1 Model
The model considers indivisible goods with additive valuations and seeks a partition of the goods among agents. It frames PMMS as a pairwise fairness condition, motivated by its relation to EFX and the open existence question for additive preferences.
1 Model
- Each agent values a bundle by summing its values for the goods, and an allocation partitions all goods into agent-associated bundles.Source: §1 · p. 1
- PMMS requires each agent’s allocated bundle to be worth at least their maximin share of the union of their bundle and any other agent’s bundle.Source: §1 · p. 1
- Under mild conditions, PMMS is stronger than EFX, whose existence for all additive valuations remains a major open question.Source: §1 · p. 1
- Whether PMMS always exists for additive preferences remained open, while Byrka et al. show nonexistence for general monotone valuations for every n ≥ 2.Source: §1 · pp. 1–2
2 Counterexample
The section constructs an additive fair-division instance with three agents and nine goods and proves that no PMMS allocation exists. Its proof restricts hypothetical allocations to two partitions of the first eight goods, then uses the makeweight good to contradict PMMS.
2 Counterexample
- No PMMS allocation exists for the constructed additive instance with 3 agents and 9 goods.The instance uses goods a1, a2, a3, b1, b2, b3, b4, c, and d.Source: §2 · p. 2
- In both P and Q, each agent has the same two equally valued favorite bundles, and each bundle is favored by two agents.Each agent can split the union of their favorite bundles into values t−1 and t+1.Source: §2 · p. 3
- If the first eight goods follow either partition P or Q, adding d to any bundle still cannot produce a PMMS allocation.A recipient without d must receive a favorite bundle; another agent can repartition their two favorite bundles so both resulting bundles exceed their current utility.Source: §2 · p. 3
- Any hypothetical PMMS allocation must give each agent exactly one large good and at least one small good.Each large good is worth at least 133, exceeding the value of all small goods combined; the proof separately rules out an agent receiving no small good.Source: §2 · pp. 3–4
- Whether c goes to agent 2 or not, a PMMS allocation would have to partition the first eight goods according to P or Q.The proof treats the c-in-agent-2 and c-not-in-agent-2 cases separately, using constraints on small-goods bundles and case distinctions.Source: §2 · pp. 4–7
3 Barriers to Approximation
Earlier work guaranteed (17 − 1)/4 ≈ 0.781-PMMS for additive valuations. The paper’s counterexamples show that guarantees above 78/79 ≈ 0.987 cannot be ensured.
3 Barriers to Approximation
- For additive valuations, (17 − 1)/4 ≈ 0.781-PMMS allocations always exist; this guarantee requires each agent’s utility to be at least that fraction of the best equal split of their bundle together with another agent’s.Source: §3 · p. 8
- Using the code in Section A, the counterexample shows that α-PMMS cannot be guaranteed for any α > 186/187 ≈ 0.995; this earlier counterexample also has n=3 and m=9.Source: §3 · p. 8
- Running the code in Section A certifies that α-PMMS cannot be guaranteed for parameter values α greater than 78/79, approximately 0.987.Source: §3 · p. 8
4 Discussion
The discussion places the three-agent impossibility alongside known existence results for EFX and epistemic PMMS, and compares the instance with MMS counterexamples. It also describes the proof’s development and notes that its many inequalities leave the construction opaque.
4 Discussion
- Unlike this three-agent PMMS impossibility, EFX and epistemic PMMS allocations are known to exist for three additive agents.The passage contrasts the result with EFX existence for three agents and additive preferences, and with a recent relaxation, epistemic PMMS.Source: §4 · p. 8
- The first known MMS counterexample used 3 agents and 12 goods; a later result reduced this to 3 agents and 9 goods.The paper says PMMS neither implies nor is implied by MMS, and calls the parallel intriguing while leaving a deeper connection open.Source: §4 · p. 8
- For 3 agents, PMMS allocations exist when m ≤ 5; the author believes 9 goods is minimal or nearly minimal, having found no counterexample with m ≤ 8.For 2 agents, additive PMMS allocations can be found through I-cut-you-choose; the author therefore identifies 3 as the smallest agent count for this nonexistence result.Source: §4 · p. 8
- The initial 12-good counterexample came from a language model, and the author later pursued simplification through ChatGPT, integer linear programming, and manual inspection.The nine-good instance was found by ChatGPT; the author says substantial further nudging was needed to simplify its proof.Source: AI Usage · pp. 8–9
- The author rewrote the generated proof by hand to improve readability and check correctness independently, but found its simultaneous inequalities left the instance mostly opaque.The author also says there seems little chance that others will build on a proof for a concrete counterexample.Source: AI Usage · p. 9
A Code for Verifying Nonexistence Computationally
The code exhaustively checks allocations to determine whether a PMMS allocation exists and, when none does, reports the best achievable alpha-PMMS value. Its output matches the section’s claims for both counterexamples.
A Code for Verifying Nonexistence Computationally
- For a fixed allocation, the code exhaustively finds the largest alpha for which that allocation satisfies alpha-PMMS, then uses a value of at least 1 to test PMMS existence.The PMMS test compares an agent’s own bundle value with the pairwise maximin value; the code separately handles a zero maximin value.Source: A Code for Verifying Nonexistence… · p. 11
- The checker enumerates every assignment of the m goods to n agents and retains the largest alpha found across allocations.It treats an allocation as a length-m vector whose entries identify the assigned agent.Source: A Code for Verifying Nonexistence… · pp. 11–12
- The implementation uses exact fractional arithmetic and checks that valuations are nonnegative and have one value per good.This avoids floating-point issues for the given integer valuations.Source: A Code for Verifying Nonexistence… · p. 12
- The checker reports best achievable alpha-PMMS values of 186/187 for the main counterexample and 78/79 for the approximation counterexample.The code output is described as matching the claims in Section 3.Source: A Code for Verifying Nonexistence… · pp. 12–13