Source-linked AI summary
The Exact MMS Guarantees of EFX and PMMS
Qinghua Qin
TL;DR
The paper determines the exact relationship between EFX and PMMS, as local fairness notions, and MMS, as a global benchmark, under nonnegative additive valuations. Using a reduction and combinatorial charging argument, it proves that both optimal universal factors equal 10/17 and constructs tight examples.
Problem
The paper asks for the exact quantitative relationship between local fairness notions EFX and PMMS and the global MMS benchmark for indivisible goods.
Method
A reduction makes EFX and PMMS imply the same local inequality on foreign bundles, which a three-piece concave weight function converts into a global guarantee.
Results
10/17 is the optimal universal factor for both EFX-to-MMS and PMMS-to-MMS, and explicit PMMS and EFX0 allocations have MMS ratios converging to 10/17.
Takeaways & Limitations
The matching constants show that PMMS’s additional pairwise flexibility does not improve the worst-case global MMS guarantee beyond 10/17.
Takeaways & Limitations
Exact finite-agent sequences for small fixed n, including n = 3, 4, 5, and extensions to broader valuation classes remain open questions.
Abstract
from arXiv · showhide
Envy-freeness up to any good (EFX) and pairwise maximin share (PMMS) are standard local fairness criteria for indivisible goods, whereas maximin share (MMS) is a global benchmark. We determine the exact quantitative relationship between these local fairness notions and the global MMS guarantee under nonnegative additive valuations. We show that the optimal universal factor for both notions is $ρ^{\mathrm{EFX}\to\mathrm{MMS}}=ρ^{\mathrm{PMMS}\to\mathrm{MMS}}=\frac{10}{17}$. We prove the lower bound by a combinatorial charging argument. After an initial reduction, both EFX and PMMS imply the same local condition on every foreign bundle from the perspective of a focal agent: deleting its least valuable good leaves value at most the focal bundle. A three-piece concave weight function translates this local condition into the global $10/17$ guarantee. We then construct an explicit family of complete allocations that are simultaneously PMMS and EFX$_0$, whose MMS ratios converge to $10/17$, showing that both constants are tight even in the presence of zero-valued goods. The argument also gives $α$-EFX $\Rightarrow (10α/17)$-MMS. Finally, we establish an exact correspondence between these fair-division guarantees and scheduling equilibria. For every fixed number of agents $n$, the EFX-to-MMS extremal ratio equals the reciprocal of the pure price of anarchy for selfish identical-machine covering. Similarly, the PMMS-to-MMS ratio equals the reciprocal of a locality gap based on exact pairwise machine repartition. These correspondences explain why the constant $10/17$ governs both problems.
1 Introduction
This paper resolves the open question of how strongly local fairness notions EFX and PMMS guarantee an agent’s global MMS. Both achieve the exact tight factor 10/17, with matching constructions and scheduling correspondences.
- Main result: PMMS’s stronger pairwise protection does not improve the worst-case global MMS guarantee beyond EFX’s factor.PMMS allows arbitrary bipartitions between agent pairs, but both notions have the same extremal factor.
- Lower bound: A charging argument reduces both notions to a common local bundle condition and uses a three-piece concave weight function to prove the lower bound.The weight function assigns at most one weight to each admissible foreign bundle while benchmark bundles of value at least 17/10 require weight at least one.
- Lower bound: The threshold 17/10 is tight because the bundle values {1, 1/2, 1/5} attain total weight exactly one.The corresponding weights are 1/2, 1/3, and 1/6.
- Tightness: Explicit complete allocations that are simultaneously PMMS and EFX0 have MMS ratios converging to 10/17, and approximate fairness satisfies α-EFX ⇒ (10α/17)-MMS.The tight construction uses perturbed blocks with local partitions satisfying the fairness condition and benchmark partitions approaching value 17/10.
- Scheduling correspondence: For fixed n, the fair-division ratios correspond exactly to reciprocals of scheduling-game inefficiency and locality-gap measures.The EFX ratio matches the reciprocal pure price of anarchy, while the PMMS ratio matches the reciprocal exact-repartition locality gap.
2 Preliminaries
The paper formalizes EFX, EFX0, α-EFX, MMS, and PMMS for indivisible goods under nonnegative additive valuations, then introduces reductions that preserve or increase a focal agent’s MMS.
- An allocation is a partition of indivisible goods among agents with nonnegative additive valuations.
- EFX requires each agent to value every other bundle after removing any positively valued good at no more than their own bundle.EFX0 applies the condition also to zero-valued goods, while α-EFX scales the comparison by α.
- MMS is the focal agent’s maximum guaranteed value across all n-partitions of the goods, and β-MMS requires receiving at least β times MMS.
- PMMS requires every pair of agents to satisfy the corresponding two-agent maximin-share condition on their combined bundles.
- Removing singleton or empty nonfocal bundles, together with their goods, does not decrease the focal agent’s MMS.The reduction follows by discarding one partition part containing the removed good and reallocating its remainder.
3 The Combinatorial Charging Theorem
The lower-bound proof reduces both EFX and PMMS to the same local bundle condition and uses a weight-function charging argument to obtain the exact 10/17 MMS guarantee, including its α-EFX extension.
- Lower bounds: 10/17: Every EFX allocation is a (10/17)-MMS allocation under nonnegative additive valuations.
- Local reduction: After normalization, EFX implies that deleting the least valuable good from every foreign bundle leaves value at most 1.Reductions remove zero-valued goods and singleton or empty bundles before normalization.
- Lower bounds: 10/17: Every PMMS allocation is also a (10/17)-MMS allocation.PMMS yields the same local inequality used in the EFX charging proof.
- Approximate fairness: 10α/17: Every α-EFX allocation is an (10α/17)-MMS allocation for α ∈ (0, 1].The proof rescales the focal valuation and applies the same contradiction when normalized MMS exceeds 17/10.
4 An Explicit Family Approaching 10/17
An explicit family constructs complete allocations that are simultaneously PMMS and EFX0 while their MMS ratios converge to 10/17, proving tightness.
- Construction: The construction uses seven copies of a recursively defined block plus one additional unit-valued good.Each block contains goods with values 1, ai, bi, ci, and di satisfying the stated recurrence and sum identities.
- Tightness: 10/17: The explicit family shows that the lower-bound constant is tight for both PMMS and EFX0.
- Construction: Each block has a local partition satisfying the fairness condition and a benchmark partition whose bundles have value Cℓ = 17/10 − δℓ.The benchmark pairs ai with di and bi with ci, then adds one unit-valued good to each pair.
- Fairness: The complete allocation is simultaneously EFX0 and PMMS.The focal singleton has value 1; deleting a minimum-valued item from any foreign bundle leaves value at most 1, and the pairwise MMS condition follows from the same bound.
- Tightness: Nℓ = 14(10^ℓ − 1): The family has this many agents and admits a complete allocation with MMS ratio at most 1/Cℓ.Since Cℓ = 17/10 − δℓ, the ratio converges to 10/17.
5 Equivalences with Machine Covering
This section establishes exact fixed-n correspondences between fair-division guarantees and selfish identical-machine covering, linking EFX and PMMS ratios to scheduling quantities.
- Fixed-n EFX and PNE equivalence: The universal EFX-to-MMS factor is the reciprocal of the pure price of anarchy for identical-machine covering.The construction and its converse identify the fair-division ratio with the covering optimum relative to minimum equilibrium load.
- Fixed-n EFX and PNE equivalence: For every n ≥2, EFX allocations correspond exactly to pure Nash equilibria in identical-machine covering.The correspondence maps positive goods to jobs and uses dummy jobs to normalize machine loads.
- PMMS and two-machine locality gaps: For PMMS, pairwise maximin share corresponds to exact two-machine repartition, while MMS corresponds to the global covering optimum.The mapping identifies each two-bundle PMMS benchmark with a two-machine covering optimum.
- PMMS and two-machine locality gaps: The PMMS locality-gap sequence Γ_n is nondecreasing in n.This monotonicity supports taking asymptotic limits across agent counts.
6 Analysis of Homogeneous Layered Partitions
The section proves that the Sylvester recursion is optimal among homogeneous layered partitions, but that restricted family cannot attain the global 10/17 frontier.
- Homogeneous layered partitions: The recursive construction generates ratios c_r=(1+Σ_t=1^r 1/d_t)^−1 converging to c∞≈0.591355 > 10/17.The sequence is defined by d_1=2 and d_{t+1}=d_t(d_t+1).
- Homogeneous layered partitions: The homogeneous layered-partition optimization has the Sylvester sequence as its unique equality case.The theorem compares feasible layered sequences and identifies equality uniquely with (2, 3, 7, 43, …).
- Homogeneous layered partitions: 10/17 requires mixed bundles because continuing the optimal homogeneous recursion cannot reach the global frontier.The mixed-bundle construction therefore escapes the restriction imposed by homogeneous layered partitions.
7 Related Work
The related-work section situates the paper between prior quantitative fair-division results and established scheduling bounds, highlighting its exact cross-domain equivalences.
- Scheduling theory: Scheduling research established the 17/10 bound for identical-machine covering and pure price of anarchy.This paper adds exact fixed-n equivalences between those scheduling quantities and fair-division guarantees.
8 Conclusion
The conclusion resolves the universal EFX- and PMMS-to-MMS factors at 10/17 and connects them exactly to machine-covering equilibria. It also identifies finite-agent sequences and broader valuation classes as open directions.
- Main conclusions: 10/17 ≈0.588235 is the identical optimal universal MMS factor for EFX and PMMS under nonnegative additive valuations.This settles the previously unresolved worst-case MMS guarantees for both notions.
- Lower-bound structure: Both EFX and PMMS reduce to the same foreign-bundle inequality, which a three-piece concave weight function converts into the sharp global guarantee.The local condition is v(B)−min_g∈B v(g)≤1 after normalizing the focal bundle.
- Tightness and mixed bundles: A complete allocation family that is simultaneously PMMS and EFX_0 has MMS ratios converging to 10/17.Reaching this frontier requires non-homogeneous mixed bundles, unlike the homogeneous Sylvester family.
- Machine-covering duality: For every fixed n, EFX ratios correspond exactly to pure price of anarchy, while PMMS ratios correspond to exact-repartition locality gaps.The correspondence explains the reciprocal appearance of 17/10 in scheduling and 10/17 in fair division.
- Open directions: Exact finite-agent sequences for small n, including n=3, 4, 5, remain open.The universal and asymptotic limits are settled, but finite-agent values are not fully determined.
- Open directions: Extending the charging approach to submodular or subadditive valuations remains an open research direction.The conclusion also asks whether other local fairness concepts correspond to alternative scheduling equilibria.
A Appendix A: Elementary Weight Identities
Appendix A records elementary inequalities for the weight function and two nonnegative algebraic identities. The weight ratio is bounded below by 2/3 on the stated intervals.
- For 0 ≤ x ≤ 1/2, w(x)/x = 1/(1 + x) ≥ 2/3.
- For 1/2 < x ≤ 2/3, w(x)/x = 1/(2 − x) ≥ 2/3.
- For nonnegative a and b, the displayed rational expression equals ab(2 + a + b)/((1 + a)(1 + b)(1 + a + b)) and is nonnegative.
- The displayed expression involving q equals (2q − 1)(6 − 5q)/(2(2 − q)(17 − 10q)) and is nonnegative.
B Appendix B: Counting the Local Bundles in the Tight Family
Appendix B introduces the total number of bundles in Table 1.
- The appendix states that it will give the total number of bundles in Table 1.
C Appendix C: Finite Values of the Layered Recursion
Appendix C compares finite-depth bounds for two recursive families: the mixed-bundle family r_ℓ and the Sylvester recursion c_r.
- Table 2 compares finite-depth values of the mixed-bundle family r_ℓ with the Sylvester recursion c_r.