Improved Approximation Guarantees for Groupwise Maximin Share Fairness

Anna Korfiati; Christodoulos Santorinaios; Evangelos Markakis; Georgios Amanatidis

arxiv: 2606.04731 · v1 · pith:7VTAG3ZKnew · submitted 2026-06-03 · 💻 cs.GT

Improved Approximation Guarantees for Groupwise Maximin Share Fairness

Georgios Amanatidis , Anna Korfiati , Evangelos Markakis , Christodoulos Santorinaios This is my paper

Pith reviewed 2026-06-28 04:02 UTC · model grok-4.3

classification 💻 cs.GT

keywords groupwise maximin shareGMMS fairnessapproximation guaranteeindivisible goods allocationadditive valuationspolynomial timedraft and eliminatefair division

0 comments

The pith

A polynomial-time algorithm achieves a (φ-1) approximation to groupwise maximin share fairness.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper demonstrates that allocations satisfying a (φ-1)-approximate version of groupwise maximin share fairness can be found efficiently for any number of agents with additive valuations. The approach refines an existing Draft-and-Eliminate method by tightening the analysis of value bounds in subgroups of agents. A reader would care because groupwise maximin share is among the strongest fairness requirements studied for indivisible goods, and better approximations bring theoretical fairness closer to practical computation.

Core claim

It is possible to compute (φ-1)-approximate GMMS allocations in polynomial time. The algorithm maintains the main properties of the Draft-and-Eliminate algorithm while improving the approximation guarantee through careful bounding of relevant values in subinstances induced by restricting the allocation to subsets of agents. This bound is asymptotically tight for algorithms with these properties and provides stronger guarantees in restricted cases such as when agents agree on the top n goods or when the number of agents is small. For three agents a variant achieves an approximation of (√10 - 1)/3 ≈ 0.72 by partially characterizing the maximin share guarantees of short picking sequences.

What carries the argument

Draft-and-Eliminate algorithm with refined bounding of maximin share values in agent-subset subinstances

Load-bearing premise

The proposed algorithm preserves the key properties of the Draft-and-Eliminate algorithm that enable tighter value bounds in every induced subinstance.

What would settle it

An explicit instance of agents and goods where the algorithm returns an allocation violating the (φ-1) approximation for some agent's groupwise maximin share.

Figures

Figures reproduced from arXiv: 2606.04731 by Anna Korfiati, Christodoulos Santorinaios, Evangelos Markakis, Georgios Amanatidis.

**Figure 2.** Figure 2: The approximation guarantee of Algorithm 1 and a comparison with ϕ−1 for relatively small values of n; note that the approximation ratio is 2/3 for n ∈ {3, 4}. goods of agents 2 to n. Moreover, if v1(gk) ≤ 1 and vi(gk) < 1 for all i > 1 and k > n, then the unique NSW-maximizing matching allocation is the one that sets fi = gi . g1 g2 g3 · · · gn−1 gn a1 ϕ + ϵ 0 0 · · · 0 0 a2 ϕ + ϵ ϕ + ϵ/2 ϕ · · · ϕ 1 a3 ϕ… view at source ↗

read the original abstract

We study the problem of fairly allocating a set of indivisible goods to a set of $n$ agents with additive valuation functions. We focus on the very demanding notion of \textit{groupwise maximin share fairness} (GMMS), which requires that each agent $i$ receives value comparable to their maximin share, where the latter is computed \textit{with respect to any subset of agents that contains $i$}. We show that it is possible to compute $(\phi-1)$-approximate GMMS allocations in polynomial time, where $\phi \approx 1.618$ is the golden ratio). This improves on the previously known guarantee of $4/7$ of Chaudhury et al. [SICOMP; 2021] and Amanatidis et al. [TCS; 2020]. We propose a simple algorithm that maintains the same main properties as the Draft-and-Eliminate algorithm of Amanatidis et al. [TCS, 2020] and we improve on the approximation guarantee analysis by carefully bounding the relevant value within any subinstance induced by the restriction of our allocation to a subset of agents. Our analysis is asymptotically tight for algorithms that share these properties and has the additional benefit of giving improved guarantees for restricted settings; in particular, when the agents agree on the top $n$ goods or when the number of agents is small. To illustrate the challenges of going beyond the guarantees of our algorithm, we also present a variant with an improved approximation of $(\sqrt{10}-1)/3 \approx 0.72$ for the case of three agents. To achieve this improvement we partially characterize the maximin share guarantees of short picking sequences for a small number of goods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper improves the GMMS approximation ratio from 4/7 to φ-1 by tightening the analysis on a Draft-and-Eliminate variant while keeping its core properties.

read the letter

The central result is a polynomial-time algorithm for (φ-1)-approximate GMMS allocations, where φ is the golden ratio. This beats the prior 4/7 bound from Chaudhury et al. and Amanatidis et al. by refining the value bounds inside subinstances rather than changing the high-level procedure much.

The paper does a few things cleanly. It shows the new ratio is asymptotically tight for any algorithm that preserves the same structural properties as Draft-and-Eliminate. It also extracts better guarantees for the restricted cases where agents agree on the top n goods or when n is small. The three-agent variant reaching roughly 0.72 via a partial characterization of short picking sequences is a useful extra data point.

The load-bearing step is the claim that the new algorithm maintains exactly the properties needed for the tighter subinstance bounds to go through. The abstract is brief on which properties survive the modifications, so a referee would want to see the explicit list and the verification that nothing in the draft or elimination order breaks the earlier bounding lemmas. If that check holds, the argument looks standard and non-circular for additive valuations.

This is incremental work inside algorithmic fair division. Readers already following GMMS or maximin-share approximations will find the improved ratio and the tightness result useful. It is not going to change practice outside the subfield, but the poly-time guarantee plus the restricted-case improvements are concrete.

I would bring the paper to a reading group focused on fair allocation. I would cite the ratio if I needed the current best poly-time bound for GMMS. The work shows clear engagement with the literature and the math is reproducible in principle, so it deserves a serious referee rather than a desk reject.

Referee Report

1 major / 2 minor

Summary. The paper claims a polynomial-time algorithm for (φ-1)-approximate GMMS allocations of indivisible goods under additive valuations, improving the prior 4/7 guarantee. The algorithm modifies the Draft-and-Eliminate procedure while preserving its main structural properties, which enables a refined analysis that bounds relevant values more tightly inside every subinstance obtained by restricting the allocation to an agent subset containing a given i. The analysis is asymptotically tight for algorithms sharing those properties and yields better ratios in restricted cases (agents agreeing on top-n goods, small n); a separate 3-agent variant achieves (√10−1)/3 ≈ 0.72 via partial characterization of short picking sequences.

Significance. If correct, the result advances the state of the art for the strong GMMS notion by raising the polynomial-time guarantee from 4/7 to φ−1 ≈ 0.618. Explicit credit is due for the constructive algorithm, the subinstance-bounding technique, the tightness claim for the preserved-property class, and the improved special-case guarantees. These elements make the contribution substantive within algorithmic fair division.

major comments (1)

[Abstract and §3] Abstract and §3 (algorithm description): the central (φ-1) guarantee rests on the claim that the new procedure 'maintains the same main properties' as Amanatidis et al.'s Draft-and-Eliminate algorithm, thereby validating the improved subinstance bounds. The manuscript does not enumerate the precise properties (draft-round ordering, elimination rule, bundle-selection criterion, etc.) that are preserved. Because any alteration could invalidate the subinstance analysis used to derive the ratio, an explicit list together with a verification that each property survives the modifications is required.

minor comments (2)

[Abstract] Abstract: extraneous closing parenthesis after 'golden ratio'.
[§5] The 3-agent variant is presented as an illustration of challenges beyond the main result; a brief statement of whether its analysis re-uses the same subinstance technique or requires new arguments would aid readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for greater clarity on the algorithmic properties. We address the single major comment below and will revise the manuscript to incorporate the requested enumeration and verification.

read point-by-point responses

Referee: [Abstract and §3] Abstract and §3 (algorithm description): the central (φ-1) guarantee rests on the claim that the new procedure 'maintains the same main properties' as Amanatidis et al.'s Draft-and-Eliminate algorithm, thereby validating the improved subinstance bounds. The manuscript does not enumerate the precise properties (draft-round ordering, elimination rule, bundle-selection criterion, etc.) that are preserved. Because any alteration could invalidate the subinstance analysis used to derive the ratio, an explicit list together with a verification that each property survives the modifications is required.

Authors: We agree that an explicit enumeration of the preserved properties, together with a verification step, would strengthen the presentation and make the applicability of the subinstance analysis fully transparent. In the revised version we will add, in Section 3 immediately after the algorithm description, a short subsection that (i) lists the key structural properties inherited from Amanatidis et al. (draft-round ordering of agents, elimination rule based on bundle-value thresholds, and the specific bundle-selection criterion), (ii) states the precise modifications we introduce, and (iii) verifies that none of the listed properties are altered by those modifications. This addition will directly address the concern while preserving the flow of the existing proof. revision: yes

Circularity Check

0 steps flagged

Minor self-citation to base algorithm; new subinstance bounding provides independent improvement.

full rationale

The paper presents a constructive polynomial-time algorithm whose (φ-1) GMMS guarantee is obtained by preserving the main properties of the Draft-and-Eliminate procedure (Amanatidis et al. TCS 2020, overlapping authors) and then applying a new, tighter bounding argument inside every induced subinstance. The self-citation supplies only the base algorithmic invariants; the improved ratio is derived from fresh value bounds that do not reduce to those invariants by definition or by fitting. No prediction is statistically forced, no ansatz is smuggled, and the central claim remains an explicit algorithmic construction plus analysis that stands on its own stated assumptions. This is the normal, non-circular case for an approximation-algorithm paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard domain assumptions in fair division theory and the structural properties inherited from the prior Draft-and-Eliminate algorithm.

axioms (1)

domain assumption Agents have additive valuation functions over indivisible goods
Explicitly stated in the abstract as the setting for the allocation problem.

pith-pipeline@v0.9.1-grok · 5860 in / 1187 out tokens · 35365 ms · 2026-06-28T04:02:31.252236+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

11 extracted references · 1 canonical work pages

[2]

URLhttps://arxiv.org/abs/2602.15566. G. Amanatidis, G. Birmpas, and V. Markakis. Comparing approximate relaxations of envy-freeness. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, pages 42–48. ijcai.org,

Pith/arXiv arXiv 2018
[3]

Christoforidis and C

V. Christoforidis and C. Santorinaios. On the pursuit of EFX for chores: Non-existence and approxima- tions. InProceedings of the Thirty-Thirds International Joint Conference on Artificial Intelligence, IJCAI 2024, pages 2713–2721. ijcai.org,

2024
[4]

Farhadi, M

A. Farhadi, M. T. Hajiaghayi, M. Latifian, M. Seddighin, and H. Yami. Almost envy-freeness, envy-rank, and Nash social welfare matchings. In35th AAAI Conference on Artificial Intelligence, AAAI 2021, pages 5355–5362. AAAI Press,

2021
[5]

Heidari, A

E. Heidari, A. Kaviani, M. Seddighin, and A. Shahrezaei. Improved maximin share guarantee for additive valuations. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, pages 2239–2290. SIAM,

2026
[6]

Huang and S

X. Huang and S. Zhou. An FPTAS for 7/9-approximation to maximin share allocations.CoRR, abs/2511.13056,

arXiv
[7]

URLhttps://doi.org/10.48550/arXiv.2511.13056. D. Kurokawa.Fair Division in Game Theoretic Settings. PhD thesis, Carnegie Mellon University,

work page doi:10.48550/arxiv.2511.13056
[8]

R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. InProceedings 5th ACM Conference on Electronic Commerce (EC-2004), pages 125–131. ACM,

2004
[9]

Mancho, E

A. Mancho, E. Markakis, and N. Protopapas. Fairness under equal-sized bundles: Impossibility results and approximation guarantees. In18th International Symposium on Algorithmic Game Theory, SAGT 2025, pages 191–208,

2025
[10]

Markakis and C

E. Markakis and C. Santorinaios. Improved EFX approximation guarantees under ordinal-based as- sumptions. InProceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, page 591–599,

2023
[11]

Plaut and T

B. Plaut and T. Roughgarden. Almost envy-freeness with general valuations. InProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 2584–2603. SIAM,

2018
[12]

Algorithm 3:Envy-Cycle-Elimination(N,A, M ′) N: set of agents,A: initial partial allocation,M ′: set of unallocated goods 1foreveryg∈M ′ in lexicographic orderdo 2whilethere is no node of in-degree 0 inG A do 3Find a cyclej 1 →j 2 →. . .→j r →j 1 inG A 4B=A j1 5fork= 1tor−1do 6A jk =A jk+1 /*shift the bundles along the cycle*/ 7A jr =B 8Leti∈Nbe the lexic...

2004

[1] [2]

URLhttps://arxiv.org/abs/2602.15566. G. Amanatidis, G. Birmpas, and V. Markakis. Comparing approximate relaxations of envy-freeness. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, pages 42–48. ijcai.org,

Pith/arXiv arXiv 2018

[2] [3]

Christoforidis and C

V. Christoforidis and C. Santorinaios. On the pursuit of EFX for chores: Non-existence and approxima- tions. InProceedings of the Thirty-Thirds International Joint Conference on Artificial Intelligence, IJCAI 2024, pages 2713–2721. ijcai.org,

2024

[3] [4]

Farhadi, M

A. Farhadi, M. T. Hajiaghayi, M. Latifian, M. Seddighin, and H. Yami. Almost envy-freeness, envy-rank, and Nash social welfare matchings. In35th AAAI Conference on Artificial Intelligence, AAAI 2021, pages 5355–5362. AAAI Press,

2021

[4] [5]

Heidari, A

E. Heidari, A. Kaviani, M. Seddighin, and A. Shahrezaei. Improved maximin share guarantee for additive valuations. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, pages 2239–2290. SIAM,

2026

[5] [6]

Huang and S

X. Huang and S. Zhou. An FPTAS for 7/9-approximation to maximin share allocations.CoRR, abs/2511.13056,

arXiv

[6] [7]

URLhttps://doi.org/10.48550/arXiv.2511.13056. D. Kurokawa.Fair Division in Game Theoretic Settings. PhD thesis, Carnegie Mellon University,

work page doi:10.48550/arxiv.2511.13056

[7] [8]

R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. InProceedings 5th ACM Conference on Electronic Commerce (EC-2004), pages 125–131. ACM,

2004

[8] [9]

Mancho, E

A. Mancho, E. Markakis, and N. Protopapas. Fairness under equal-sized bundles: Impossibility results and approximation guarantees. In18th International Symposium on Algorithmic Game Theory, SAGT 2025, pages 191–208,

2025

[9] [10]

Markakis and C

E. Markakis and C. Santorinaios. Improved EFX approximation guarantees under ordinal-based as- sumptions. InProceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, page 591–599,

2023

[10] [11]

Plaut and T

B. Plaut and T. Roughgarden. Almost envy-freeness with general valuations. InProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 2584–2603. SIAM,

2018

[11] [12]

Algorithm 3:Envy-Cycle-Elimination(N,A, M ′) N: set of agents,A: initial partial allocation,M ′: set of unallocated goods 1foreveryg∈M ′ in lexicographic orderdo 2whilethere is no node of in-degree 0 inG A do 3Find a cyclej 1 →j 2 →. . .→j r →j 1 inG A 4B=A j1 5fork= 1tor−1do 6A jk =A jk+1 /*shift the bundles along the cycle*/ 7A jr =B 8Leti∈Nbe the lexic...

2004