Pairwise maximin share fairness breaks down with three agents and nine goods
PMMS Allocations Need Not Exist for 3 Agents with Additive Valuations
Computer Science and Game Theory
Summary
Sometimes when sharing items among people, we want each person to feel they got a fair portion based on how they value the items. One fairness idea is called pairwise maximin share (PMMS), which means no one envies another's share when comparing just two people at a time. This paper shows that for three people and nine items, it’s impossible to divide the items so that everyone’s share meets this fairness idea. The authors also demonstrate that even getting close to this fairness measure can fail by a very small amount, using a computer to check all possibilities.
fair divisionpairwise maximin shareindivisible goodsadditive valuationsenvy-freenessapproximation ratioallocationcomputational fairnessexhaustive enumeration
Authors
Paul Gölz
Abstract
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$.