CS Paper Radar

Pairwise Maximin Share Allocations Need Not Exist

Haris Aziz

cs.GT ·submitted 2026-09-05 22:33 UTC · v1

Abstract

We study the fair allocation of indivisible goods among agents with strictly positive additive valuations. Pairwise maximin share fairness (PMMS) asks that, for every ordered pair of agents, the first agent value her own bundle at least as highly as the best worst-case share she could secure by repartitioning the two agents' combined bundles into two parts. Whether a PMMS allocation always exists for positive additive valuations has remained open since the notion was introduced. We resolve this question in the negative. We construct an instance with four agents and strictly positive additive valuations that admits no complete PMMS allocation.

Closest papers

Nearest neighbours by meaning across the whole index.

PMMS Allocations Need Not Exist for 3 Agents with Additive Valuations

cs.GT ·2026-09-08 ·Paul Gölz
highly cited similarity 0.84
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$.

0.44

Maximin Share Allocations Beyond Weakly Lexicographic Valuations

cs.GT ·2026-09-12 ·Nicholas Teh
theory similarity 0.81
Abstract

We study the fair division of indivisible goods among agents with nonnegative additive valuations. An agent's maximin share (MMS) is the value she can guarantee by partitioning the goods into as many bundles as there are agents and receiving a least-valued bundle. We prove the existence of exact MMS allocations for a valuation domain that generalizes several few-valued domains as well as weakly lexicographic valuations. For each agent, the lower-valued goods, after a positive rescaling, may take values in $\{0,1,d,d+1\}$, $\{0,1,2,2e\}$, or $\{0,1,2,3,4\}$, where $d,e\ge 2$ are integers. Above these goods, the valuation may contain arbitrarily many value classes, subject to the condition that a single good in each class is worth at least the total value of all strictly lower-valued goods. The value classes, scaling factors, and parameters may vary across agents. We give an algorithm that computes an MMS allocation in $O(nm\log^2(2+m))$ time, where $n$ is the number of agents and $m$ is the number of goods.

0.34

Fair Allocation with Optional Selling

cs.GT econ.TH ·2026-08-25 ·Uriel Feige, Yotam Gafni
similarity 0.79
Abstract

We consider fair allocation of indivisible goods in a setting in which agents have subjective valuation functions over the set of goods, and in addition, goods may be sold at given market prices. In this setting, a fair allocation involves {deciding which goods to sell, how to allocate the unsold goods, and how to divide the money received from the sold goods.} We adapt to this setting the definitions of share-based fairness notions, such as the maximin share (MMS) and the truncated proportional share (TPS), and comparison-based fairness notions such as EF1 and EFX (which we adapt to SEF1 and SEFX). We show the following results when the utility of each agent is additive both over goods and over money. With two agents, there are allocations that are simultaneously MMS and SEFX. With three agents, there are instances in which no allocation gives every agent more than $\frac{11}{12}$-MMS. With any number of agents, there are $\frac{2}{3}$-MMS allocations. There also are allocations that are simultaneously SEFX and $\frac{n}{2n-1}$-TPS. This latter ratio is best possible, even without the SEFX requirement.

0.32

To EFX OR to MMS, That is the Question

cs.GT ·2026-08-11 ·Hadi Hosseini, Payas Khurana, Shraddha Pathak, Rohit Vaish
theory similarity 0.77
Abstract

We study the agent-wise disjunction of two central fairness notions for indivisible items, where every agent must be either envy-free up to any item (EFX) or maximin-share (MMS) satisfied. One might expect that having a flexible fairness requirement for individual agents will restore existence, especially because the existence of EFX itself resisted resolution for nearly a decade. Surprisingly, it does not. We construct counterexamples with three agents and eight submodular goods, and with three agents and seven submodular chores, significantly strengthening recent EFX impossibility results. On the positive side, we prove existence for additive mixed items with at most three valuation types when one type is a singleton. Additionally, we obtain polynomial-time approximation schemes for additive goods-only and chores-only instances. We also identify a clean separation between the disjunction and its constituents: For additive chores with two valuation types, EFX and MMS are both known to fail, whereas an EFX $\vee$ MMS allocation always exists. Finally, we show that identical additive valuations even admit the conjunction EFX $\wedge$ MMS for mixed items. Overall, our results show that allowing flexibility in choosing agent-specific fairness certificates expands the frontier of fair solutions while also uncovering surprising impossibilities.

0.32

Non-Existence of PMMS Allocations and a $4/3$-PMMS Guarantee for Additive Chores

cs.GT ·2026-09-09 ·Xiaohui Bei, Zehan Lin, Shengxin Liu, Rong Luan, Biaoshuai Tao
theory similarity 0.76
Abstract · 23 pages, no figure

We study pairwise maximin share (PMMS) fairness for indivisible items with additive preferences. We give a polynomial-time reduction from chores to goods that preserves the existence of a PMMS allocation. Together with known nonexistence results for chores, this yields nonexistence for additive goods. In addition, we show that deciding if a given instance admits a PMMS allocation is NP-hard. We also give explicit instances whose PMMS factors are $226/227$ for goods and $1.102065$ for chores, certified by exact enumeration. Complementing these impossibility results, we prove that every additive-chore instance admits a $4/3$-PMMS allocation.

0.38

Pareto Inefficiency of EFX

cs.GT ·2026-10-21 ·Sepideh Mahabadi, Prasanna Ramakrishnan, Jakub Tarnawski
similarity 0.75
Abstract

We consider the problem of allocating indivisible goods to agents with additive valuations, under two classic notions of fairness and efficiency: envy-freeness up to any good (EFX) and Pareto optimality. While some of the earliest work on EFX showed that Pareto optimal EFX allocations may not exist if agents can have zero value for some goods, it has remained open whether the same is true when all values are positive. We present a simple instance in which every good has positive value to every agent, but no Pareto optimal EFX allocation exists. We then generalize to a family of instances showing that Pareto optimal $α$-EFX allocations may not exist for any $α> 2/3$.

0.39

The Golden Ratio: EF1 and Ordinal-MMS for Additive Goods

cs.GT ·2026-11-11 ·Hadi Hosseini, Shraddha Pathak
theory similarity 0.75
Abstract

Every complete allocation that is envy-free up to one good (EF1) guarantees each of the $n$ agents her $1$-out-of-$(2n-1)$ maximin share. Can we construct allocations that satisfy EF1 together with stronger ordinal maximin share guarantees? For additive valuations, we prove that there always exists a complete allocation that is simultaneously EF1 and ($1$-out-of-$\lfloor\varphi n\rfloor$)-MMS, where $\varphi=(1+\sqrt{5})/2$ is the golden ratio. For bivalued valuations, where each agent may have her own two non-negative values for the goods, we obtain a complete allocation that is simultaneously envy-free up to any good (EFX) and ($1$-out-of-$\lceil(7n-1)/6\rceil$)-MMS.

0.05

On MMS allocations with few items

cs.GT ·2026-10-05 ·Uriel Feige
theory similarity 0.75
Abstract

We consider the problem of allocating $m$ indivisible items to $n$ agents. For $n \ge 2$, we define $μ(n)$ as the largest $m$ for which every allocation instance with $n$ agents and $m$ items has an allocation that gives each agent at least her maximin share (MMS). We prove that for general monotone valuations, $μ(n) = n + Θ(\log n)$. This holds both for goods and for chores. For arbitrary valuations (not monotone), we prove that $μ(n) = \log n + O(1)$.

0.38