Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Improved Approximate EFX Guarantees for Multigraphs

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For additive valuations over multigraph goods — where each good is relevant to at most two agents — a complete allocation that is (1/√2)-EFX always exists, improving the previous (2/3) guarantee.

desk verdict New 1/√2 EFX constant for multigraphs, but the proof rests on a false imported lemma about basic feasible allocations. read the letter →

arxiv 2506.09288 v2 pith:JNHZQV2G submitted 2025-06-10 cs.GT

Alireza Kaviani , Alireza Keshavarz , Masoud Seddighin , AmirMohammad Shahrezaei This is my paper · ORCID
classification cs.GT MSC 91B3268W25
keywords fairdivisionEFXapproximateenvy-freeness(pq)-boundedvaluationsmultigraphgoodsadditiveNashsocialwelfareweightedenvygraph
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that in any fair-division instance where each good is valued positively by at most two agents (a multigraph whose vertices are agents and whose edges are goods), a complete allocation satisfying a 1/√2-approximate notion of envy-freeness up to any good (EFX) always exists. This improves the previous best guarantee of 2/3 for the same class. The result matters because EFX is a leading fairness notion for indivisible goods, and proving existence for structured but broad classes is the main avenue of progress while the general existence question remains open. The proof is constructive: an algorithm with five updating rules returns the allocation.

What carries the argument

The argument is carried by the weighted envy graph $G_X$, with edge weights $w_X(i,j)=v_i(X_j)/v_i(X_i)$; an edge is heavy when its weight exceeds $1/\sqrt{2}$ and light otherwise. The algorithm maintains a partition of agents into finalized and remaining groups, together with five invariants, of which the crucial one is that every remaining agent's bundle is relevant only to itself and at most one other remaining agent — this forces the zero-value envy graph to be a disjoint union of cycles. Five rules then resolve these cycles: pool-envy elimination (Rule 1), finalizing agents with no out-edges (Rule 2), handling 2-cycles via a two-agent EFX completion theorem of Mahara (2023) or a choice protocol (Rule 3), rotating bundles in homogeneous cycles and assigning relevant pool goods (Rule 4), and breaking heterogeneous cycles through a heavy/light three-agent pattern (Rule 5). Leftover goods are given to the last finalized agent.

What would settle it

Enumerate all small (2,∞)-bounded additive instances (say, multigraphs with n ≤ 4 vertices and up to 8 edges with arbitrary positive weights), run Algorithm 1 as specified, and check whether any output contains agents i,j and a good g ∈ X_j with √2 · v_i(X_i) < v_i(X_j \ {g}). One such instance would disprove Theorem 4.9. Independently, search for any (2,∞)-bounded instance where no one-good-per-agent allocation maximizing Nash social welfare gives every agent a positive-value good; that would break the initialization and the entire proof.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 4.9: for additive (2,∞)-bounded valuations — each good is relevant to at most two agents, with no bound on how many goods a pair shares — Algorithm 1 returns a complete (1/√2)-EFX allocation. Since every agent receives all goods, this shows the existence of complete allocations in which no agent β-strongly envies another for β=√2, i.e., after deleting any single good from a rival's bundle, the agent's own bundle is at least 1/√2 as valuable. This establishes 1/√2 ≈ 0.707 as the best known universal approximation factor for EFX over multigraph goods, improving the (2/3)-EFX guarantee of Amanatidis et al. (2024).

Load-bearing premise

The initialization relies on a lemma from Kaviani et al. (2024) — not re-proved here — that a maximum-Nash-welfare one-good-per-agent allocation can be chosen so that every agent receives a good of positive value; if that lemma fails for some (2,∞)-bounded instance, the invariants that the whole algorithm depends on can fail at the very first step.

Editorial extensions

If this is right

  • Any additive instance on a multigraph — including parallel edges, i.e., multiple goods shared by the same pair — now has a guaranteed complete allocation that is $(1/\sqrt{2})$-EFX, improving the previous $2/3$ factor.
  • The two-agent completion theorem enters as a black box in Rule 3, so whenever only two agents remain the algorithm actually produces an exact EFX allocation between them, not just an approximate one.
  • The invariant framework — finalized agents never $\sqrt{2}$-envy the union of remaining bundles, and remaining bundles have in-degree at most one — is a reusable template for other approximate-EFX existence proofs.
  • The result closes one gap in the $(p,q)$-bounded landscape: for $p=2$, $q=\infty$, the guarantee jumps from $2/3$ to $1/\sqrt{2}$; exact EFX itself remains open even for this class.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The technique likely extends to $(p,q)$-bounded instances with $p>2$, but the in-degree-at-most-one invariant that drives the cycle structure would need a different justification, so the constant would probably degrade with $p$.
  • The basic feasible allocation lemma is used as a black box; a direct proof or a counterexample for $(2,\infty)$-bounded valuations would be the simplest way to test the robustness of the whole construction.
  • The paper gives no lower bound: it remains possible that the true best factor for this class is better than $1/\sqrt{2}$; a brute-force search over small multigraphs could suggest whether the constant is tight.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies fair allocation of indivisible goods with additive (2,∞)-bounded valuations, equivalently represented as multigraphs. It presents Algorithm 1, which maintains five invariants while applying five update rules, and claims in Theorem 4.9 that the algorithm always returns a complete (1/√2)-EFX allocation, improving the previous 2/3-approximation for this class. The proof is built on a weighted envy graph, a cycle classification, and an imported 'basic feasible allocation' lemma from the authors' earlier work (Kaviani et al., 2024), used to initialize the algorithm with one positive-valued good per agent.

Significance. If the main theorem is correct, it is a meaningful quantitative improvement for a natural bounded-valuation fair-division model and gives a concrete, structural algorithm rather than a nonconstructive existence argument. The invariant framework and the detailed case analysis for cycles are valuable ingredients. However, the proof currently rests on an initialization lemma that is false as stated, and the proof of Rule 4 contains an unjustified claim about rotated heavy edges; as a result, the central theorem is not established by the manuscript in its present form. The paper does not provide machine-checked proofs or code, so the correctness of the lengthy case analysis rests entirely on the written arguments.

major comments (2)
  1. [Section 2, Algorithm 1 initialization] The assertion that the basic feasible allocation can be chosen so that every agent receives a positive-valued good is false as stated. Consider N={1,2,3}, M={g,h,i}, with v1(g)=v2(g)=1, v3(h)=v3(i)=1, and all other singleton values 0. This instance is additive and (2,∞)-bounded. In any one-good-per-agent allocation, g is assigned to exactly one of agents 1 and 2, and the other receives h or i, which he values at 0. Hence every NSW-maximizing one-good-per-agent allocation gives some agent value 0, contradicting the initialization premise. Since the weighted envy graph G_X is defined via ratios vi(Xj)/vi(Xi), this makes the graph undefined at initialization and prevents Properties (iii)–(v), and therefore Lemmas 4.2–4.8 and Theorem 4.9, from being applied to the instance. The theorem may still be true, but the proof as written does not cover all (2,∞)-bounded instances.
  2. [Lemma 4.7, Rule 4] The proof of Property (i) for Rule 4 contains an unjustified step about rotated heavy edges. The text says that after the rotation, for the incoming edge j→i, 'i receives j's previous bundle' and 'since j→i is a heavy edge', j does not √2-envy i. After a rotation, however, the new edge j→i has weight v_j(X_i^new)/v_j(X_j^new), which equals v_j(X_j^old)/v_j(X_h^old) for the predecessor h of j; this is not the reciprocal of the old edge i→j, and the heaviness of the old edge i→j does not by itself bound this ratio. The conclusion may be recoverable from a different edge, but the argument as written is a gap in the proof that Rule 4 preserves the invariants.
minor comments (4)
  1. [Section 2, paragraph on (p,q)-bounded valuations] The text says 'we focus on the special case where p=2 and q=1', but the abstract and Theorem 4.9 claim (2,∞)-bounded instances. This should be corrected to q=∞, since the algorithm and lemmas do not appear to use q≤1.
  2. [Algorithm 3, lines 8–10] In the case vi(A)<vi(B), the pseudocode first assigns X_i* ← B and then immediately overwrites X_i* ← A. The intended else-branch is missing; as written, the algorithm does not implement the described choice of the more valuable bundle.
  3. [Section 3, Rule 3 footnote] The reduction to Mahara (2023) via dummy agents with infinite-valued dummy goods is outside the additive real-valuation model stated in the paper. Please replace it with a valid reduction or a direct two-agent argument (e.g., using known complete EFX guarantees for two agents).
  4. [Theorem 4.4 restatement] The restatement says the agents have 'at most two distinct valuation functions' but the footnote refers to an additional assumption in Mahara (2023) that each valuation is shared by at least two agents; the relationship between these statements should be clarified.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the (1/sqrt(2))-EFX existence proof is an invariant-based algorithm argument, and the imported basic-feasible-allocation lemma from the authors' prior work is an input dependency rather than a restatement of the target result.

full rationale

The paper's central claim is Theorem 4.9: Algorithm 1 returns a (1/sqrt(2))-EFX allocation for additive (2,infinity)-bounded valuations. The derivation is an invariant-based algorithm proof: it defines five update rules, proves that each preserves Properties (i)-(v), and then derives the guarantee from those invariants. No parameter is fitted to data and no output quantity is used as an input. The only self-citation is the initialization step in Section 2, which imports a basic feasible allocation lemma from Kaviani et al. (2024), where all four authors overlap. That lemma is load-bearing for the weighted envy graph denominators, but it is an input dependency rather than a restatement of the target result; whether the lemma is true is a correctness question, not circularity. The terminal two-agent case invokes Mahara (2023), an external theorem. Therefore no circular step is present and the score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters or invented entities appear; the claim is an existential guarantee. The central dependencies are two imported theorems: the self-cited basic feasible allocation lemma and Mahara's two-agent EFX completion. Both are plausible but not verified inside the paper.

assumptions (4)
  • domain assumption Additive valuation functions and (2,∞)-bounded relevance graph, meaning each good is relevant to at most two agents and there is no bound on shared goods.
    The proof is restricted to this model, defined in Section 2; the result may not extend beyond it.
  • domain assumption Basic feasible allocation gives every agent a good of positive value, as stated in Kaviani et al. (2024).
    Invoked in Section 3 to initialize Algorithm 1; imported from a paper with overlapping authorship and not proved here.
  • domain assumption Theorem 4.4 of Mahara (2023): any partial EFX allocation for agents with at most two distinct valuation functions extends to a complete EFX allocation without decreasing utility.
    Used in Rule 3 for the two-remaining-agents terminal case; the dummy-agent reduction with infinite value is asserted in a footnote and not verified.
  • standard math Standard finiteness and positivity properties of the discrete allocation space, used for termination arguments.
    Background used throughout the algorithm; no new mathematical system is introduced.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Approximate EFX Guarantees for Multigraphs." pith.science (2026). https://pith.science/paper/JNHZQV2G

@misc{pith2026250609288,
  author       = {Pith},
  title        = {Pith review of: Improved Approximate EFX Guarantees for Multigraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JNHZQV2G}},
  note         = {Machine review of arXiv:2506.09288}
}
abstract

In recent years, a new line of work in fair allocation has focused on EFX allocations for \((p, q)\)-bounded valuations, where each good is relevant to at most \(p\) agents, and any pair of agents share at most \(q\) relevant goods. For the case \(p = 2\) and \(q = \infty\), such instances can be equivalently represented as multigraphs whose vertices are the agents and whose edges represent goods, each edge incident to exactly the one or two agents for whom the good is relevant. A recent result of \citet{amanatidis2024pushing} shows that for additive $(2,\infty)$ bounded valuations, a \((\nicefrac{2}{3})\)-EFX allocation always exists. In this paper, we improve this bound by proving the existence of a \((\nicefrac{1}{\sqrt{2}})\)-\(\efx\) allocation for additive \((2,\infty)\)-bounded valuations.

Figures

Figures reproduced from arXiv: 2506.09288 by the authors.

Figure 1
Figure 1. An example of an allocation and its weighted envy graph. See Table [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. A schematic overview of the properties. Dashed arcs: No Strongly envy. Solid black arc: [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. EFX Allocation In (Multi)Hypergraphs

    cs.GT 2026-08 conditional novelty 7.0 of 10

    Any hypergraph with girth at least 4 admits an EFX allocation under general monotone valuations, and a restricted class of multi-hypergraphs admits one in pseudo-polynomial time.

Reference graph

Works this paper leans on

30 extracted references · 28 canonical work pages · cited by 1 Pith paper

  1. [1]

    Afshinmehr, M., Danaei, A., Kazemi, M., Mehlhorn, K., and Rathi, N. (2024). Efx allocations and orientations on bipartite multi-graphs: A complete picture. arXiv preprint arXiv:2410.17002

    arXiv 2024

  2. [2]

    R., Garg, J., Mehlhorn, K., and Mehta, R

    Akrami, H., Alon, N., Chaudhury, B. R., Garg, J., Mehlhorn, K., and Mehta, R. (2023). Efx: a simpler approach and an (almost) optimal guarantee via rainbow cycle number. In Proceedings of the 24th ACM Conference on Economics and Computation (EC) , pages 61--61

    work page 2023

  3. [3]

    Epistemic EFX Allocations Exist for Monotone Valuations

    Akrami, H. and Rathi, N. (2024). Epistemic efx allocations exist for monotone valuations. arXiv preprint arXiv:2405.14463

    work page Pith review arXiv 2024

  4. [4]

    Akrami, H., Rezvan, R., and Seddighin, M. (2022). An ef2x allocation protocol for restricted additive valuations. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI) , pages 17--23

    work page 2022

  5. [5]

    Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Hollender, A., and Voudouris, A. A. (2021). Maximum nash welfare and other stories about efx. Theoretical Computer Science , 863:69--85

    work page 2021

  6. [6]

    Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Voudouris, A., et al. (2022). Fair division of indivisible goods: A survey. In International Joint Conference on Artificial Intelligence (IJCAI) , pages 5385--5393

    work page 2022

  7. [7]

    Amanatidis, G., Filos-Ratsikas, A., and Sgouritsa, A. (2024). Pushing the frontier on approximate efx allocations. arXiv preprint arXiv:2406.12413

    work page Pith review arXiv 2024

  8. [8]

    Amanatidis, G., Markakis, E., and Ntokos, A. (2020). Multiple birds with one stone: Beating 1/2 for efx and gmms via envy cycle elimination. Theoretical Computer Science , 841:94--109

    work page 2020

Show all 30 references
  1. [9]

    Ashuri, A., Gkatzelis, V., and Sgouritsa, A. (2024). Ef2x exists for four agents

    2024

  2. [10]

    Aziz, H., Li, B., Moulin, H., and Wu, X. (2022). Algorithmic fair allocation of indivisible items: A survey and new questions. ACM SIGecom Exchanges , 20(1):24--40

    2022

  3. [11]

    Babaioff, M., Ezra, T., and Feige, U. (2021). Fair and truthful mechanisms for dichotomous valuations. In Proceedings of the Thirty-Third Conference on Innovative Applications of Artificial Intelligence (AAAI) , pages 5119--5126

    2021

  4. [12]

    Barman, S., Biswas, A., Krishnamurthy, S., and Narahari, Y. (2018). Groupwise maximin fair allocation of indivisible goods. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 32

    2018

  5. [13]

    Berger, B., Cohen, A., Feldman, M., and Fiat, A. (2022). Almost full efx exists for four agents. In Proceedings of the Thirty-Third Conference on Innovative Applications of Artificial Intelligence (AAAI) , pages 4826--4833

    2022

  6. [14]

    Brams, S. J. and Taylor, A. D. (1996). Cake-Cutting Algorithms: Be Fair If You Can . Cambridge University Press

    1996

  7. [15]

    Budish, E. (2011). The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy , 119(6):1061--1103

    2011

  8. [16]

    Caragiannis, I., Gravin, N., and Huang, X. (2019). Envy-freeness up to any item with high nash welfare: The virtue of donating items. In Proceedings of the ACM Conference on Economics and Computation (EC) , pages 527--545

    2019

  9. [17]

    D., Shah, N., and Wang, J

    Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., and Wang, J. (2016). The unreasonable fairness of maximum nash welfare. In Proceedings of the 2016 ACM Conference on Economics and Computation (EC) , pages 305--322

    2016

  10. [18]

    Chan, H., Chen, J., Li, B., and Wu, X. (2019). Maximin-aware allocations of indivisible goods. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI) , pages 137--143

    2019

  11. [19]

    R., Garg, J., and Mehlhorn, K

    Chaudhury, B. R., Garg, J., and Mehlhorn, K. (2024). Efx exists for three agents. Journal of the ACM , 71(1):1--27

    2024

  12. [20]

    R., Garg, J., Mehlhorn, K., Mehta, R., and Misra, P

    Chaudhury, B. R., Garg, J., Mehlhorn, K., Mehta, R., and Misra, P. (2021a). Improving efx guarantees through rainbow cycle number. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC) , pages 310--311

    2021

  13. [21]

    R., Kavitha, T., Mehlhorn, K., and Sgouritsa, A

    Chaudhury, B. R., Kavitha, T., Mehlhorn, K., and Sgouritsa, A. (2021b). A little charity guarantees almost envy-freeness. SIAM Journal on Computing , 50(4):1336--1358

    2021

  14. [22]

    Christodoulou, G., Fiat, A., Koutsoupias, E., and Sgouritsa, A. (2023). Fair allocation in graphs. In Proceedings of the 24th ACM Conference on Economics and Computation (EC) , pages 473--488

    2023

  15. [23]

    Farhadi, A., Hajiaghayi, M., Latifian, M., Seddighin, M., and Yami, H. (2021). Almost envy-freeness, envy-rank, and nash social welfare matchings. In Proceedings of the Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, (AAAI) , pages 5355--5362

    2021

  16. [24]

    Ghosal, P., Nimbhorkar, P., Varma, N., et al. (2024). Efx exists for three types of agents. arXiv preprint arXiv:2410.13580

    2024 arXiv

  17. [25]

    C., Seddighin, M., Seyed-Javadi, S.-M., and Sharifi, M

    Jahan, S. C., Seddighin, M., Seyed-Javadi, S.-M., and Sharifi, M. (2023). Rainbow cycle number and efx allocations: (almost) closing the gap. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI) , pages 2572--2580

    2023

  18. [26]

    Kaviani, A., Seddighin, M., and Shahrezaei, A. (2024). Almost envy-free allocation of indivisible goods: A tale of two valuations. In Proceedings of the 20th Conference on Web and Internet Economics (WINE)

    2024

  19. [27]

    D., and Wang, J

    Kurokawa, D., Procaccia, A. D., and Wang, J. (2018). Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM (JACM) , 65(2):8

    2018

  20. [28]

    Mahara, R. (2023). Existence of efx for two additive valuations. Discrete Applied Mathematics , 340:115--122

    2023

  21. [29]

    and Roughgarden, T

    Plaut, B. and Roughgarden, T. (2020). Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics , 34(2):1039--1068

    2020

  22. [30]

    Procaccia, A. D. (2015). Cake cutting: Not just child's play. Communications of the ACM , 58(7):78--87

    2015

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.