pith. sign in

arxiv: 2606.18665 · v1 · pith:HM2A5FZCnew · submitted 2026-06-17 · 💻 cs.GT

EFX Allocations Exist on Multi-Graphs

Mahyar Afshinmehr , Arash Ashuri , Pouria Mahmoudkhan , Kurt Mehlhorn , Amir Mohammad Shahrezaei This is my paper

Pith reviewed 2026-06-26 19:13 UTC · model grok-4.3

classification 💻 cs.GT
keywords EFX allocationsmultigraph valuationsfair divisioncancelable valuationsindivisible goodsenvy-freenessalgorithmic existence
0
0 comments X

The pith

EFX allocations exist for multigraph instances under cancelable valuations.

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

The paper proves that when goods correspond to edges in a multigraph and each agent's valuation function is cancelable, an allocation always exists such that any envy between agents disappears after removing any single good from the envied bundle. Cancelable valuations strictly contain the additive class and allow the proof to handle multiple goods valued by the same pair of agents. The result closes the existence question for this setting after earlier work succeeded only for simple graphs or narrower valuation classes. An explicit algorithm finds such an allocation in polynomial time for any number of agents. Readers care because EFX is among the strongest practical fairness notions for indivisible goods, and multigraphs capture settings with repeated connections between the same parties.

Core claim

For any multigraph valuation instance where the functions are cancelable, an EFX allocation exists and an algorithm computes one in polynomial time. This holds with an arbitrary number of agents and resolves the open problem left after results for simple graphs and partial multigraph cases.

What carries the argument

An algorithmic construction that iteratively assigns goods while maintaining the EFX property, using the cancelable condition to manage parallel edges between the same agent pair.

If this is right

  • EFX allocations can be computed in polynomial time whenever valuations are cancelable.
  • Existence extends to a valuation class strictly larger than additive functions.
  • The guarantee applies to arbitrary numbers of agents.
  • The result covers multigraphs, closing the gap from simple-graph proofs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If many practical preferences satisfy cancelability, the algorithm could be deployed directly on network-structured allocation problems.
  • The technique might be tested on valuations that barely violate cancelability to map the exact boundary of the result.
  • Similar algorithmic ideas could be explored for other fairness criteria such as MMS on the same multigraph domain.

Load-bearing premise

The valuation functions must be cancelable.

What would settle it

A concrete multigraph instance whose valuations are cancelable but admits no EFX allocation would disprove the existence result.

Figures

Figures reproduced from arXiv: 2606.18665 by Amir Mohammad Shahrezaei, Arash Ashuri, Kurt Mehlhorn, Mahyar Afshinmehr, Pouria Mahmoudkhan.

Figure 1
Figure 1. Figure 1: This is an example of how the envy graph may look after phase two. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: This figure illustrates an example of the allocation proposed in Phase Three. In this example, [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: This figure illustrates an example of the allocation proposed in the dumping phase of [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
read the original abstract

We study the fair allocation of indivisible goods among agents, with a focus on limiting envy. A central fairness notion is envy-freeness up to any good (EFX), which requires that any envy toward another agent vanishes after the removal of any single good from the latter's bundle. The existence of EFX allocations is considered a major open problem in fair division. So far, it has only been established in limited settings. Christodoulou et al. [2023] proved the existence of EFX allocations for graphical valuations. In this setting, the agents correspond to the nodes of an underlying graph, and the goods correspond to the edges, and any good has positive value only for the endpoints of the corresponding edge. Their proof crucially relies on the restriction that the graph is simple, meaning that for any pair of agents, there is at most one good that has value to both. For multigraph valuations, where multiple goods may be valued by the same pair of agents, only partial results are known. Amanatidis et al. [2024] and Kaviani et al. [2025] obtained 2/3 and sqrt(2)/2 approximations of EFX, respectively; Kaviani et al. [2024] established existence under restricted additive valuations; and Afshinmehr et al. [2025a] proved existence under the assumption that the shortest cycle containing non-parallel edges has length at least 4. In this paper, we resolve this open problem by proving the existence of EFX allocations for multigraph instances under cancelable valuations, a strict superclass of additive valuation functions. Our proof is algorithmic and computes such allocations in polynomial time when the valuation functions are cancelable. This work contributes to the small number of EFX existence results that apply to an arbitrary number of agents.

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.

Referee Report

0 major / 1 minor

Summary. The paper proves existence of EFX allocations for multigraph fair division instances (goods as edges, possibly multiple between the same agent pair) when agents have cancelable valuations, a strict superclass of additive valuations. The proof is algorithmic and yields a polynomial-time procedure to compute such an allocation; this resolves the open problem left after Christodoulou et al. (2023) for simple graphs and improves on the approximation and restricted-existence results known for multigraphs.

Significance. If correct, the result is a notable advance: it supplies the first EFX existence proof (with poly-time algorithm) that applies to arbitrary numbers of agents on multigraphs under a natural valuation class strictly larger than additive. The algorithmic nature and explicit scope to cancelable valuations are strengths that make the contribution falsifiable and potentially extensible.

minor comments (1)
  1. The abstract and introduction would benefit from an explicit statement of the running time (e.g., O(n^k) or similar) rather than the generic claim of 'polynomial time'.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our results on EFX allocations for multigraph instances under cancelable valuations, as well as their recommendation to accept the paper.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents a direct algorithmic proof establishing existence of EFX allocations for multigraph instances restricted to cancelable valuations. No equations or steps in the provided abstract reduce a claimed prediction or result to a fitted input, self-definition, or self-citation chain. Self-citations to prior work (including Afshinmehr et al. [2025a]) address narrower cases and are not invoked as load-bearing uniqueness theorems for the current result. The derivation is therefore self-contained as an independent construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that valuations are cancelable and on the standard multigraph model; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Valuation functions are cancelable
    The existence proof and algorithm are stated to hold only under this property, which is a strict superclass of additive valuations.

pith-pipeline@v0.9.1-grok · 5882 in / 1119 out tokens · 24105 ms · 2026-06-26T19:13:28.395633+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    A Counterexample to EFX $n \ge 3$ Agents, $m \ge n + 5$ Items, Submodular Valuations via SAT-Solving

    International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2025b. Hannaneh Akrami and Jugal Garg. Breaking the 3/4 barrier for approximate maximin share. InProceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, pages 74–91. SIAM, 2024. Hannaneh Akrami and Nidhi Rathi. Achieving maximin share and EFX/EF1 guarantees ...

    work page internal anchor Pith review doi:10.48550/arxiv.2604.18216 2024

  2. [2]

    In other words, all goods that are transferred betweenxandyare transferred fromY 2 ∪xtoY 1 \x

    Also sinceY ′ 1 ⊔Y ′ 2 = (Y1 \x)⊔(Y 2 ∪x), we get thatY ′ 2 ⊆Y 2 ∪x. In other words, all goods that are transferred betweenxandyare transferred fromY 2 ∪xtoY 1 \x. We consider two cases based on which set,Y ′ 1 orY ′ 2,ybelongs to. •Case 1. y∈Y ′ 1: Sinceyis being transferred fromY ′ 1, by the definition of PR algorithm, we have that y=ℓ(Y ′ 1), so for ev...

  3. [3]

    Ifx≺y, thenℓ(Y ′ 1)̸=y

    Recall thatx⪯y. Ifx≺y, thenℓ(Y ′ 1)̸=y. Therefore,xhas equal value toy, which means 29 thatY ′ 2 \yandY ′ 2 \xhave the same value 6. Moreover, sinceY ′ 2 ⊆Y 2 ∪x, we getY ′ 2 \x⊆Y 2, which implies Y ′ 2 \x⪯Y 2, and therefore,Y ′ 2 \y⪯Y 2. Thus, Y ′ 2 \y⪯Y 2 ≺Y 1 \x⪯Y ′ 1 , where the last inequality is due toY 1 \x⊆Y ′

  4. [4]

    So we haveY ′ 2 \y≺Y ′ 1, which is a contradiction, since in the PR algorithm, when the algorithm removes some goodyfromY ′ 2 and adds it toY ′ 1, it should be that Y ′ 2 \y≻Y ′

  5. [5]

    Lemma A.3.[Ashuri et al., 2025] The modified PR algorithm runs in polynomial time when the input is a set of two disjoint bundles and a cancelable valuation function

    Hence, the proof is complete. Lemma A.3.[Ashuri et al., 2025] The modified PR algorithm runs in polynomial time when the input is a set of two disjoint bundles and a cancelable valuation function. Proof.Suppose we execute the modified PR algorithm given (Y 1, Y2) as input. During the execution of the modified PR algorithm, there can be at mostmconsecutive...

    2025

  6. [6]

    Ifmin(v(B 1), v(B2))<min(v(A 1), v(A2)), thenmax(v(A 1), v(A2))≤max(v(B 1), v(B2))

  7. [7]

    If|v(B 1)−v(B 2)| ≤ |v(A 1)−v(A 2)|, thenmin(v(A 1), v(A2))≤min(v(B 1), v(B2)), and max(v(A1), v(A2))≥max(v(B 1), v(B2)). Proof.1. First, assume that min(v(B 1), v(B2))<min(v(A 1), v(A2)). Without loss of generality assume v(B1) = min(v(B1), v(B2)), soB 1 ≺A 1 andB 1 ≺A 2. Leti, j∈ {1,2}andi̸=j. We showB 1 ∩A i ≺B 2 ∩A j. Towards a contradiction, supposeB...

  8. [8]

    Assume min(v(B 1), v(B2))<min(v(A 1), v(A2)) for the sake of getting a contradiction

    Suppose|v(B 1)−v(B 2)| ≤ |v(A 1)−v(A 2)|. Assume min(v(B 1), v(B2))<min(v(A 1), v(A2)) for the sake of getting a contradiction. Then, by the first part of the lemma, we get max(v(A 1), v(A2))≤ max(v(B1), v(B2)), which results in|v(B 1)−v(B 2)|>|v(A 1)−v(A 2)|, which is a contradiction. Hence, min(v(A1), v(A2))≤min(v(B 1), v(B2)). If min(v(A1), v(A2)) = mi...

  9. [9]

    Next, we provide the algorithm that we use to compute unit bundles in polynomial time

    By combining max(v(A 1), v(A2))≤max(v(B 1), v(B2)) and min(v(B 1), v(B2))≤min(v(A 1), v(A2)), we get|v(A 1)−v(A 2)| ≤ |v(B 1)−v(B 2)|. Next, we provide the algorithm that we use to compute unit bundles in polynomial time. Algorithm 5:Computing Unit Bundles ofE i,j 1t←1; 2(Z (t) 1 , Z(t) 2 )←PR(E i,j,∅, v i) ; 3(Y (t) 1 , Y (t) 2 )←PR(Z (t) 1 , Z(t) 2 , vj...

  10. [10]

    The pair(Y (t) 1 , Y (t) 2 )isEFX-feasiblefor agentj

  11. [11]

    The pair(Z (t) 1 , Z(t) 2 )isEFX-feasiblefor agenti. 3. vj(Y (t) 1 )−v j(Y (t) 2 ) ≤ vj(Z (t) 1 )−v j(Z (t) 2 ) . Proof.The first two are because the bundles are the output of PR algorithm. For the last one, we either have vj(Y (t) 1 )−v j(Y (t) 2 ) ≤ vj(Z (t) 1 )−v j(Z (t) 2 ) or: (Y (t) 1 , Y (t) 2 )←PR(Z (t) 1 , Z(t) 2 , vj), so by Lemma A.5, we get vj...

  12. [12]

    The pair{a j,i, bj,i}is anEFX-feasiblecut for agenti

  13. [13]

    3.v i(aij)≥max(v i(aji), vi(bji))≥min(v i(aji), vi(bji))≥v i(bij), i.e., the(a j,i, bj,i)-partition is at least as balanced forias the(a i,j, bi,j)-partition

    The pair{a i,j, bi,j}is anEFX-feasiblecut for agentj. 3.v i(aij)≥max(v i(aji), vi(bji))≥min(v i(aji), vi(bji))≥v i(bij), i.e., the(a j,i, bj,i)-partition is at least as balanced forias the(a i,j, bi,j)-partition. 4.v j(aji)≥max(v j(aij), vj(bij))≥min(v j(aij), vj(bij))≥v j(bji),, i.e., the(a i,j, bi,j)-partition is at least as balanced forjas the(a j,i, b...

  14. [14]

    3.h 0 is non-resented

    Agentp’s bundle is a unit bundle inE p,h0, and agentpdoes not resent anyone. 3.h 0 is non-resented

  15. [15]

    Every agent inN\Honly holds one unit bundle. The execution ofReduce Trees(X, h 0)terminates after at mostniterations of the while loop, and at the end, the agents inHstill hold their initial bundle, every agent inN\Hpossesses exactly one unit bundle, andh 0 remains non-resented. Proof.LetU=H, p=p, andj=h 0 at first. Then, during the execution ofReduce Tre...

  16. [16]

    Agentp’s bundle is a unit bundle inE p,j, and agentpdoes not resent anyone

  17. [17]

    Every agentt∈N\Upossesses exactly one unit bundle

  18. [18]

    By the assumptions of the lemma, all invariants hold before the first iteration of the while loop

    Allocation remains basic. By the assumptions of the lemma, all invariants hold before the first iteration of the while loop. Assume inductively that the invariants hold at the beginning of some iteration, and we show that they also hold at the beginning of the next iteration. LetU 0,p 0, andj 0 denote the values ofU,p, andjat the start of the iteration, a...

  19. [19]

    Then, after execution ofReduce Trees(X, h 0), we get an allocation such that: •The allocation is height-one

    Every agent inN\Honly holds one unit bundle. Then, after execution ofReduce Trees(X, h 0), we get an allocation such that: •The allocation is height-one. •The agents inHstill hold their initial bundle, and ifh∈H\pwas non-resented, she remains non- resented. •For everyh∈H, and for everyt /∈ {h, h 0}, no allocated unit bundle inE h,t gets unallocated. •h 0 ...

  20. [20]

    Thus, after the iteration, any resent path of length greater than one must start at jℓ, and the induction invariant is preserved

    Therefore, after receivinga jℓ,i1, agentj ℓ cannot be part of any resent path of length greater than one. Thus, after the iteration, any resent path of length greater than one must start at jℓ, and the induction invariant is preserved. Consequently, whenReduce Trees(X, h 0) terminates, every resent tree has height at most one, and hence the resulting allo...

  21. [21]

    For every agentp, we haveX ′ p ⪰p Xp, whereX ′ is the allocation after the dumping

  22. [22]

    If agentqis resented inX, thenqis not strongly envied by any agent inX ′

  23. [24]

    Proof.LetXandX ′ denote the allocation before and after the dumping phase

    For any support pair(s, t)used by the dumping phase, at the end, no one envies agents, and agents does not strongly envy anyone. Proof.LetXandX ′ denote the allocation before and after the dumping phase. We prove each statement separately: (1) Ifpwas resented before, we haveX ′ p =X p by property 5. Ifpwas not resented before, properties 3a, 3b guarantee ...

  24. [25]

    For every agentp, we haveX ′ p ⪰i Xp

  25. [28]

    No one envies agentss 1 ands 2, and agentss 1 ands 2 do not strongly envy anyone. For any other non-resented agentp /∈ {s1, s2}, and for any other agentqnot resented byp, we have that X ′ p ∩E q is a unit bundle, which was either possessed by agentpor was unallocated before the dumping phase. In the first case,qdoes not envy this unit bundle because she d...

  26. [31]

    For every resentp→qbefore the dumping phase, agentqdoes not envy agentpafter the dumping phase

  27. [32]

    To prove that the final allocation isEFX, we show that any agentp̸=swho was non-resented inX, cannot be strongly envied inX ′

    No one envies agents, and agentsdoes not strongly envy anyone. To prove that the final allocation isEFX, we show that any agentp̸=swho was non-resented inX, cannot be strongly envied inX ′. To do so, we prove the following: •No one enviest, andtenvies no one.For every agenti,X t ∩E i is a unit bundle inE t,u; hence, X ′ t ⪯i ai,t ⪯i Xi ⪯i X ′ i, where the...

  28. [33]

    The resulting allocation ˆXis simple height-one

  29. [34]

    3.q k weak most-resents agentp

    For any agentt̸=q k, agenttdoes not resent anyone. 3.q k weak most-resents agentp

  30. [35]

    , qk are non-resented

    Agentsq 1, . . . , qk are non-resented. Proof.Let ˆXbe the allocation after Update D. Sincepresentedq k inX, we haveX qk =a qk,p. Moreover, qk did not resent anyone inX, and thereforea qk,p ⪰qk aqk,j for every agentj. Agentpdoes not resent anyone in ˆXsince by the ordering of theq i’s, we havea p,qk ⪰p ap,j for any other agentj. Every agentt /∈ {p, qk}kee...

  31. [36]

    For every agentt, we haveX ′ t ⪰t ˆXt

  32. [37]

    Nobody strongly envies agentp

  33. [38]

    For everyi < k,q k does not envyq i sinceX ′ i ∩E qk =b qk,qi ⪯qk aqk,qi ⊆X ′ qk

    Agentpdoes not envy agentqafter the dumping phase. For everyi < k,q k does not envyq i sinceX ′ i ∩E qk =b qk,qi ⪯qk aqk,qi ⊆X ′ qk. Agentq k is not envied by q1 because, by case 1 condition, we have: X ′ q1 ⪰q1 aq1,p ∪b qk,q1 ⪰q1 bq1,p ∪a qk,q1 =X ′ qk ∩E q1 . By Lemma E.1, sincea qi,qk ⊆A qi(X), for every 1< i < k, we have aqi,p ⪰qi bp,qi ∪A qi(X)⪰ qi a...

  34. [39]

    2.X s ⪰s as,t ∪D s(X)

    For every resented agenth, we haveX h ≻h bh,t ∪A h(X)andX h ≻h ah,s ∪(A h(X)\E h,s). 2.X s ⪰s as,t ∪D s(X)

  35. [40]

    Then, there exists a completeEFXallocation

    For every non-resented agenti /∈ {s, t}, eitherX i ∩E i,t =a i,t orX i ∩E i,s =a i,s. Then, there exists a completeEFXallocation. Proof.We allocate the unallocated unit bundles in the dumping phase. (i)Root to root.Letpandrbe two distinct roots. If at least one of the unit bundles is already allocated to one of the roots, allocate the other unit bundle to...

  36. [42]

    Nobody strongly envies any agent who was resented at the start of the dumping phase

  37. [43]

    A resented agenthdoes not envy anyone.By the previous argument, we knowhdoes not envy agent tor any other resented agent

    For every agenthwho was resented inX, agenthdoes not envy agenttafter the dumping phase. A resented agenthdoes not envy anyone.By the previous argument, we knowhdoes not envy agent tor any other resented agent. So letp̸=tbe an agent who was non-resented inX. Ifp̸=s, then we getX ′ p ∩E h =a p,h ⪯h ah,p ⪯h ah,t =X ′ h, where the first inequality follows fr...

  38. [46]

    For every resentp→qinX, agentqdoes not envy agentpinX ′

  39. [47]

    To prove that the final allocation isEFX, we show that any agentp̸=swho was non-resented inX, cannot be envied inX ′

    No one envies agents, and agentsdoes not strongly envy anyone. To prove that the final allocation isEFX, we show that any agentp̸=swho was non-resented inX, cannot be envied inX ′. To do so, we prove the following. Note that by the fourth statement of Lemma 5.4, we do not need to consider envies from or toward agents. •Agentkis not strongly envied by any ...

  40. [48]

    For every agentp, we haveX ′ p ⪰p Xp

  41. [49]

    Nobody strongly envies any agent who was resented inX

  42. [50]

    To prove that the final allocation isEFX, we show that any agentpwho was non-resented inX, cannot be envied inX ′

    For every resentp→qinX, agentqdoes not envy agentpinX ′. To prove that the final allocation isEFX, we show that any agentpwho was non-resented inX, cannot be envied inX ′. To do so, we prove the following. 63 •Agentkis not envied by any agent.First, we show thatudoes not envykinX ′. By property FP5, we have that X ′ u ⪰u Xu ⪰u ak,u ∪(A u(X))\(E u,k ∪E u,i...

  43. [51]

    For every agentp,X ′ p ⪰p Xp

  44. [52]

    Nobody strongly envies any agent who was resented at the start of dumping

  45. [53]

    For every resent edgep→qinX, agentqdoes not envy agentpinX ′

  46. [54]

    No one envies agents, and agentsdoes not strongly envy anyone. By the second statement of Lemma 5.4, in order to prove that the final allocation isEFX, it suffices to show that any agentp̸=swho was non-resented inX, cannot be strongly envied inX ′. Letqbe a resented agent andrbe the unique root such thatr→qinX. By the third statement of Lemma 5.4, we can ...