CS Paper Radar

Tight Maximin Share Guarantees of EFX and PMMS

Qinghua Qin

cs.GT ·submitted 2026-08-31 05:17 UTC · v2
benchmarktheory

Abstract

In the fair division of indivisible goods among autonomous agents, allocations frequently satisfy strong pairwise fairness criteria while failing to guarantee an agent's full maximin share. Maximin share (MMS) is a global benchmark: the value an agent can guarantee by partitioning all goods into $n$ bundles and receiving her least preferred bundle. In contrast, local pairwise fairness notions---most notably envy-freeness up to any good (EFX) and pairwise maximin share (PMMS)---evaluate fairness through bilateral bundle comparisons. We resolve the open question of determining the optimal universal MMS approximation factor guaranteed by either local notion under nonnegative additive valuations, proving that both factors equal exactly $10/17$. For the lower bound, we show that both EFX and PMMS imply a common local residual inequality: the value of any foreign bundle after removing its least valuable item cannot exceed the focal agent's allocated value. We design a continuous piecewise weight function that converts this local constraint into the global $10/17$ MMS guarantee. The same charging argument establishes that $α$-EFX implies $(10α/17)$-MMS. For tightness, we construct an explicit family of complete allocations that simultaneously satisfy PMMS and EFX$_0$, including comparisons involving zero-valued goods, and whose MMS ratios converge to $10/17$. For each fixed number of agents, we also establish exact reciprocal identities connecting fair division to scheduling: the EFX guarantee is the reciprocal of the pure price of anarchy in selfish identical-machine covering, while the PMMS guarantee is the reciprocal of a locality gap for exact repartition of two machines.

Closest papers

Nearest neighbours by meaning across the whole index.

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.80
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

Fair Allocation with Optional Selling

cs.GT econ.TH ·2026-08-25 ·Uriel Feige, Yotam Gafni
similarity 0.75
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

Pairwise Maximin Share Allocations Need Not Exist

cs.GT ·2026-09-05 ·Haris Aziz
similarity 0.73
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.

0.43

Fair Division Under Boolean Valuations: Beyond Normalization

cs.GT ·2026-08-30 ·Nisarg Shah, Paritosh Verma
similarity 0.73
Abstract

We study fair division of indivisible items when agents have arbitrary two-level preferences: the value of each agent for any set of items is Boolean, which need not be monotone or additive. Notably, we do not impose the standard assumption of normalization, i.e., different agents may value the empty set at different Boolean levels. Since the preferences are nonmonotone, envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) each admit several variants, depending on which items are tested for removal and whether they are removed from the envious agent's bundle or the envied agent's bundle. This paper investigates the existence of these variants of EF1 and EFX, on their own and together with economic efficiency, incentive compatibility, feasibility constraints, and lottery-based randomization. Our results highlight that the existence landscape depends crucially on the number of normalized agents, who value the empty bundle at the lower Boolean level. The authors used significant assistance from GPT-5.6-Sol for deriving theoretical results, verified any AI-generated proofs for correctness, and expanded on the exposition and simplified arguments, with the aid of GPT-5.6-Sol and Claude Opus 5.

0.17

Polynomial Algorithms for Simultaneous Share-Based and Envy-Based Guarantees

cs.GT ·2026-10-11 ·Hannaneh Akrami, Arash Ashuri, Kurt Mehlhorn
similarity 0.73
Abstract

We study the simultaneous achievement of share-based and envy-based fairness in the allocation of indivisible goods with nonnegative additive valuations. The AnyPrice share (APS) is a strengthening of the maximin share (MMS). A polynomial-time algorithm is known to guarantee a $2n/(3n-1)$ approximation of APS, but without an accompanying envy-based guarantee. Separately, allocations simultaneously satisfying minimum EFX share (MXS) and envy-freeness up to one less-preferred good (EFL), and subsequently the stronger requirement of residual maximin share (RMMS) together with EFL, have been shown to exist. However, the known constructions do not provide pseudopolynomial-time guarantees. We develop algorithms that combine these share-based and envy-based fairness requirements. First, for every $\varepsilon \in (0,1)$, we give an algorithm that computes an allocation satisfying exact EFL, $(1-\varepsilon)$-MXS, and $2n/(3n-1)$-APS. Its running time is polynomial in the binary input length and $1/\varepsilon$. Thus, we match the previously established polynomial-time APS approximation while simultaneously guaranteeing exact EFL and an arbitrarily close approximation to MXS. Second, we provide a pseudopolynomial-time algorithm that simultaneously guarantees exact MXS, exact EFL, and $2n/(3n-1)$-APS. Third, for every fixed number of agents, we obtain a pseudopolynomial-time algorithm that simultaneously achieves exact RMMS and exact EFL. Finally, we establish that computing a numerical threshold between MXS and RMMS is weakly NP-hard, even for additive valuations. This identifies a computational barrier to extending our polynomial-time approach to exact MXS through independently computed residual-valid share thresholds.

0.38

When Maximum Nash Welfare Becomes Strongly Fair: Bi-valued Goods

cs.GT ·2026-09-09 ·Zehan Lin, Xiaowei Wu, Shengwei Zhou
similarity 0.73
Abstract

For the fair allocation of indivisible goods, the milestone work of Caragiannis et al. (2019) revolutionized the understanding of Maximum Nash Welfare (MNW) allocations by revealing their "unreasonable" ability to balance fairness (EF1) and efficiency (PO) for general additive functions. Subsequent work established that MNW allocations simultaneously satisfy EFX and GMMS (and consequently MMS and PMMS) for binary instances (Amanatidis et al. 2021 and Barman et al. 2018), and satisfy EFX for bi-valued instances (Amanatidis et al. 2021). In this paper, we revisit the (personalized) bi-valued instances and provide a tight characterization of the approximation guarantees of MNW allocations with respect to EFX, PMMS, and GMMS, showing that these guarantees are significantly stronger than what is known for general valuations. Furthermore, we demonstrate that even for the slightly more general setting of tri-valued instances, the fairness guarantees of MNW deteriorate significantly, which establishes a sharp boundary on the instances for which MNW allocations are strongly fair.

0.18

Maximin Share Allocations Beyond Weakly Lexicographic Valuations

cs.GT ·2026-09-12 ·Nicholas Teh
theory similarity 0.72
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

Exact Hill Shares Are Simultaneous Guarantees

cs.GT ·2026-09-18 ·Bo Li, Hanyu Li, Chenghua Liu
benchmarktheory similarity 0.72
Abstract

Fair division of indivisible bads seeks allocations that guarantee every agent a bundle whose cost is no larger than a meaningful fairness benchmark. The canonical minimax share has widely been used; unfortunately, it is not a simultaneous guarantee. Hill (Ann. Probab., 1987) initiated a complementary approach in which the share depends only on the number of agents and the largest possible single-item value. Li et al. (ACM Trans. Econ. Comput., 2024) gave the exact Hill formula and proved that its monotone closure is a simultaneous guarantee. The closure treats the largest-item cost only as an upper bound and can be strictly larger than the share conditioned on the \emph{actual} largest item. They asked whether this smaller exact share is itself simultaneously guaranteed for three or more agents. We resolve this open question affirmatively. For any number of agents and arbitrary heterogeneous largest-item costs, there is one allocation that satisfies every agent's exact Hill's share. We further provide a polynomial-time algorithm computes such an allocation. Our algorithm combines an ordered moving knife with a tail-domination invariant, and a one-sided trimmed subset-sum routine for the two-agent endpoint without computing an exact minimax partition.

0.16