EFX Allocation In (Multi)Hypergraphs

Alkmini Sgouritsa; Minas Marios Sotiriou; Thanasis Lianeas

REVIEW 2 major objections 6 minor 47 references

EFX Allocation In (Multi)Hypergraphs

T0 review · 2 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read The paper proves that EFX allocations always exist for hypergraphs of girth at least 4, under arbitrary monotone valuations, and can be built in polynomial time; a generalized result covers multi-hypergraphs under a multiplicity bound.

desk verdict Solid EFX frontier result with a real but repairable hole in the pseudo-polynomial claim of Theorem 2. read the letter →

arxiv 2608.03171 v1 pith:6IN2EPXI submitted 2026-08-04 cs.GT cs.AI

Thanasis Lianeas , Alkmini Sgouritsa , Minas Marios Sotiriou This is my paper · ORCID

classification cs.GTcs.AI MSC 91B3205C65

keywords EFXallocationenvy-freeuptoanygoodhypergraphmulti-hypergraphgirthmonotonevaluationsfairdivisionalgorithmicgametheory

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 attacks the open problem of whether envy-free-up-to-any-good (EFX) allocations always exist. It establishes that on hypergraphs whose shortest cycle has length at least 4, an EFX allocation always exists for any number of agents with general monotone valuations that only increase with more goods, and it can be constructed in polynomial time. For multi-hypergraphs, where several goods may sit on the same set of vertices, the same conclusion holds in pseudo-polynomial time provided at least one vertex has all its incident edges of multiplicity at most the edge size minus 2. The significance is that these are among the broadest settings in which exact EFX, rather than an approximation, is guaranteed; the previous best for hypergraphs of girth at least 3 was only an approximate guarantee.

What carries the argument

The load-bearing structure is the girth-at-least-4 condition on the underlying simple hypergraph. It yields two facts: any two vertices lie together in at most one edge (Observation 2.1), and two vertices that share an edge have no common neighbor outside that edge (Observation 2.2). These make a vertex's incident edges nearly private, which lets the algorithm designate vertex 0 as a parking spot for all edges that cannot be oriented to an endpoint without creating envy, and lets the completion phase hand a newly allocated edge to a non-envied vertex knowing that only its intended recipient values it. The second mechanism is the subroutine from [19] that finds an inclusion-wise minimal subset from a patch of identical-copy edges such that no agent envies a proper subset of it, together with a social-welfare potential that strictly increases at every step, which bounds the running time as pseudo-polynomial in the multi-hypergraph case.

What would settle it

Exhibit one finite hypergraph of girth at least 4 with agents holding arbitrary monotone valuations and prove that no complete EFX allocation exists; the paper predicts every such instance has one. For the multi-hypergraph theorem, apply the paper's own Lemma 4.1 reduction to any instance of the open almost-full EFX problem: the resulting multi-hypergraph has a vertex whose single violating edge has multiplicity exactly one above the bound, so an instance of that open problem with no almost-full EFX allocation would directly contradict Theorem 2's conclusion.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 1, is that every instance on a hypergraph of girth at least 4 — where agents are vertices, goods are edges, and a good matters only to the agents incident to it — admits a complete EFX allocation for arbitrary monotone valuations, producible in time polynomial in the number of agents and goods. The proof is constructive: it first builds a partial EFX orientation in which a specially designated vertex 0 stays non-envied while all difficult edges are parked on it, then completes the allocation by giving every remaining edge either to a non-envied vertex or to vertex 0. Theorem 2 extends the same template to multi-hypergraphs in which edges may repeat, requiring only that some vertex have incident edge multiplicities bounded by the edge size minus 2, in which case the construction runs in pseudo-polynomial time. The paper also shows the multiplicity condition is not an artifact: if a single vertex is allowed one incident edge of multiplicity one more than the bound, the problem becomes as hard as the open almost-full EFX problem of existence with at most one unallocated good.

Load-bearing premise

The entire construction assumes the underlying simple hypergraph has girth at least 4, so any two vertices share at most one edge and two vertices of a shared edge have no outside common neighbor, and, in the multi-hypergraph case, that some one vertex has all incident edge multiplicities at most the edge size minus 2; if either fails, the parking argument that prevents new envy collapses.

Editorial extensions

If this is right

Every simple hypergraph with girth at least 4, including every 3-cycle-free graph, admits a complete EFX allocation for general monotone valuations, constructible in polynomial time.
The same guarantee holds in multi-hypergraphs with girth at least 4 as soon as one vertex meets the multiplicity bound $|\mathcal{P}_e| \le |e|-2$ for all incident patches, though the construction is only pseudo-polynomial.
A designated non-envied parking vertex can absorb all non-orientable edges without creating envy, so the absence of an EFX orientation is not an obstacle to an exact EFX allocation.
Relaxing the multi-hypergraph condition by allowing a single incident edge of multiplicity one larger than the bound makes the existence problem at least as hard as the open almost-full EFX problem, so the bound is tight relative to that open problem.

Reading between the lines

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

The proof's reliance on the two girth-4 observations suggests girth 4 is not merely sufficient for this technique but likely necessary for it; testing exact EFX on small girth-3 hypergraphs would reveal whether the girth restriction can be relaxed at all.
The pseudo-polynomial runtime in the multi-hypergraph case is driven by a social-welfare potential that can take exponentially many values; a combinatorial lexicographic potential might give a polynomial bound in this restricted setting, which would be a testable improvement.
The reduction in Lemma 4.1 connects the multiplicity bound to the almost-full EFX problem: progress on EFX with bounded charity would automatically imply EFX existence for a wider class of multi-hypergraphs, and a counterexample in that class would refute a natural relaxation.
The park-on-vertex-0 template may transfer to other structured markets, such as goods with limited externalities described by interval or geometric graphs, wherever a small set of hub vertices can absorb all edges that cannot be oriented.

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.

Desk Editor's Note

read the letter

Colleague,

The paper is a genuine step forward for EFX on hypergraphs: it turns the known sqrt(2)/2-EFX approximation for girth-at-least-3 hypergraphs into exact EFX for girth-at-least-4, under general monotone valuations, and adds a multi-hypergraph generalization with a single restricted vertex. The parking-vertex approach is a real idea, and Lemma 4.1 gives a nice tightness argument: if you allow one incident patch of multiplicity |e|-1 at the special vertex, you are solving the almost-full EFX problem with one unallocated good. I read the core invariants carefully and they hold up. Observations 2.1 and 2.2 do the girth work, Properties 1–4 are checked in the lemmas, and there's no circularity: Subroutine 7 is imported from a published paper and has nothing to do with the claims here.

The soft spot is Theorem 2's complexity statement. Section 2 lets valuations be arbitrary reals, and pseudo-polynomial time isn't defined for real-valued input. Lemma 4.9 argues termination by social-welfare potential, "following [19]"; that only yields a pseudo-poly bound if each increment is bounded away from zero, i.e., if valuations are integer or fixed-precision rational. With reals, the same social welfare can climb by 1/2, 1/4, ... over an exponential number of allocations. So as stated, the pseudo-polynomial claim is not quite a theorem. The existence part of Theorem 2 survives: the algorithm still terminates in finite time because there are finitely many allocations and the potential strictly increases. And the polynomial-time claim in Theorem 1 is unaffected—that bound (Lemma 3.6) counts actual reallocations of edges, not potential increments, and appears robust.

There's also a confusing sentence before Lemma 4.9 about Subroutine 7 running in time "polynomial on the number of different values of the social welfare"—that's garbled and should be cleaned up, but it doesn't affect the mathematics.

Who should read this: anyone tracking the EFX frontier in graphical and hypergraph settings. It deserves a serious referee. If I were refereeing, I'd ask for the valuation-encoding assumption to be stated, or the complexity claim downgraded to finite termination, plus a clarification of that garbled sentence. I wouldn't block acceptance on the existence theorems.

Referee Report

2 major / 6 minor

Summary. The paper studies the existence and computation of EFX allocations in a graphical fair-division setting where agents are vertices of a (multi)hypergraph and goods are edges; each agent may value only the edges incident to it. The first main result (Theorem 1) states that for hypergraphs with girth at least 4 and arbitrary monotone valuations, an EFX allocation always exists and can be constructed in polynomial time. The second main result (Theorem 2) extends this to multi-hypergraphs of girth at least 4 under an additional structural condition: there is a vertex whose incident edge-multiplicities are at most the corresponding edge size minus 2; for this case the construction is claimed to run in pseudo-polynomial time. The proofs maintain a partial EFX orientation satisfying four invariants, use a distinguished vertex 0 to 'park' non-oriented edges, and in the multi-hypergraph case import a minimal-envy-patch subroutine from Chaudhury et al. [19]. A reduction (Lemma 4.1) is given to indicate that dropping the multiplicity restriction is at least as hard as the almost-full EFX problem.

Significance. If correct, Theorem 1 is a solid advance: it establishes exact EFX existence for hypergraphs of girth at least 4 under fully general monotone valuations, going beyond the previously known approximate guarantee for girth-3 hypergraphs and complementing the triangle-free multigraph results in the literature. The four-property framework and the use of a single parking vertex are clean, and the girth observations (Observations 2.1-2.2) are simple but effective in limiting how many edges can be visible to a pair of agents. The paper is also honest about the boundary of its technique: Theorem 2 requires a restrictive multiplicity condition, and Lemma 4.1 connects the relaxed condition to the hard almost-full EFX problem. The main weaknesses are formal: the complexity claims are not fully pinned down with respect to the valuation model, and the polynomial-time proof of Lemma 3.6 contains a misstatement that needs a corrected argument to support the claimed bound.

major comments (2)

[Section 2, Lemma 4.9, Theorem 2] The pseudo-polynomial time claim in Theorem 2 is not well-defined for the valuation model stated in Section 2. There, valuations are arbitrary monotone functions vi: 2^M -> R_{\ge 0}; for real-valued inputs, 'pseudo-polynomial time' has no standard meaning because there is no integer parameter with respect to which the running time can be measured. Moreover, the proof of Lemma 4.9 argues termination by the social-welfare potential strictly increasing, 'following the analysis of [19]'. That argument yields an iteration bound only if each increase of the potential is bounded away from zero, which holds for integer-valued (or fixed-precision rational) valuations but not for arbitrary reals. As written, Lemma 4.9 establishes only finite termination. I recommend adding an explicit integrality or bounded-precision assumption to Theorem 2 and the abstract, or replacing the pseudo-polynomial claim with a finite-termination statement. This issue does not affect the existence part of Theorem 2, but it is load-bearing for the stated complexity guarantee.
[Lemma 3.6, Algorithm 2] The proof that Algorithm 2 runs in O(n^6) time contains an incorrect statement. It says: 'every envied vertex receives a single edge' and uses this to conclude that each vertex can be updated at most n times. However, line 4 of Algorithm 2 sets X_i <- U_i(X), which may contain many edges, not a single edge. The intended bound can likely be repaired by arguing that whenever a vertex's bundle changes, its value strictly increases, and therefore a vertex can never receive the same edge twice; this would bound the number of allocations per vertex by its degree. But this argument is not given, and the stated reason ('it has at most n relevant edges') does not by itself bound the number of updates of the form U_i(X). As written, Lemma 3.6 does not establish the polynomial-time claim of Theorem 1, so the proof of that central theorem is incomplete at this point.

minor comments (6)

[Abstract and Theorem statements] The phrase 'polynomial time to the number of agents and goods' should read 'polynomial in the number of agents and goods'.
[Algorithm 4, line 3] The line 'k = arg max_j {v_j(Z) > v_j(X_j)}' is ambiguous: it should specify that k is the highest-index vertex satisfying the condition, since the proofs of Property (2) in Lemmas 4.6 and 4.7 rely on that tie-breaking rule.
[Lemma 4.8] The assertion that 'vertex 0 may be only allocated edges from a single patch' is used critically in Algorithm 6 but is not explicitly proven; it follows because FixProp3Gen replaces the whole bundle (X_k <- Z) rather than appending to it, so the last allocation to vertex 0 always comes from a single patch. Please state this justification explicitly.
[Section 2] The heading 'Envy - EFX allocation' has a typographical issue, and the definition of an allocation is introduced before the graphical model; consider reorganizing so that an allocation is defined after the hypergraph setting.
[Lemma 4.3] The sentence 'k defined in line 3 belongs to e since v_k(Z) > v_k(X_k) \ge 0' is terse; it relies on the fact that a positive value for a set Z implies positive value for at least one edge in it, and all edges in a patch share the same vertex set, so k must be in e.
[Introduction] In the discussion of Christodoulou et al., the phrase 'construct an EFX allocation by orienting the edges' would be clearer as 'construct an EFX orientation', as that is the standard term used later in the paper.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorems 1 and 2 are proved constructively from the girth and multiplicity assumptions, with no fitted input or result assumed by construction.

full rationale

The derivation chain is self-contained. Theorem 1 is constructive: Algorithm 2 builds a partial EFX orientation satisfying Properties (1)-(4) (Lemmas 3.1-3.4), and Algorithm 3 completes it to a full EFX allocation using those properties (Lemma 3.5). Properties are established from the girth-at-least-4 Observations 2.1-2.2 and monotonicity, not from the target conclusion, and the polynomial bound in Lemma 3.6 is a combinatorial count. Theorem 2 similarly derives Properties (1)-(4) for multi-hypergraphs from the stated multiplicity restriction and the same girth observations; the only external import is Subroutine 7 (an inclusion-wise minimal envied subset procedure from [19]), which appears verbatim in Appendix A and whose correctness is a routine monotonicity argument. Although [19] shares an author with this paper, it does not assume EFX existence in (multi)hypergraphs and is independent published work, so it does not create circularity. The pseudo-polynomial-time claim in Lemma 4.9 is under-specified because valuations are defined as arbitrary real numbers and the social-welfare potential argument requires an integrality or precision assumption to bound increments; this is a complexity/correctness gap, not circularity, and does not affect the circularity score.

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

No free parameters, because the paper proves existence theorems rather than fitting data. No invented entities, because the parking-vertex role is an algorithmic device, not a new object with independent evidence requirements. The assumptions are the hypergraph valuation model, girth at least 4, the multiplicity condition, and the correctness of a cited subroutine.

assumptions (4)

domain assumption Each agent's valuation is monotone, normalized, nonnegative, and each agent values only hyperedges incident to its vertex.
This defines the hypergraph fair-division model (Section 2) and is used throughout all proofs.
domain assumption The underlying simple hypergraph has girth at least 4.
Observations 2.1 and 2.2 depend on girth at least 3 and at least 4, and every later lemma uses these structural facts. If girth is 3, the paper's approach only yields an approximate guarantee.
domain assumption In the multi-hypergraph setting, there exists a vertex whose incident edge patches have multiplicity at most the edge size minus 2.
Lemma 4.8 needs two non-envied vertices j1 and j2 that hold no copies of the special patch; the multiplicity bound guarantees they exist. Lemma 4.1 shows that dropping this restriction makes the problem as hard as the open almost-full EFX problem.
standard math Subroutine 7 from Chaudhury et al. [19] returns a set Z such that no vertex envies a proper subset of Z.
This is imported as a published black box (Appendix A, cited [19]) and is used to preserve EFX in FixProp3Gen. It is a prior peer-reviewed result, not the target of this paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of EFX Allocation In (Multi)Hypergraphs." pith.science (2026). https://pith.science/paper/6IN2EPXI

@misc{pith2026260803171,
  author       = {Pith},
  title        = {Pith review of: EFX Allocation In (Multi)Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6IN2EPXI}},
  note         = {Machine review of arXiv:2608.03171}
}

read the original abstract

We study fair allocations of indivisible goods among agents with heterogeneous monotone valuations. As fair we consider the allocations that are envy-free-up-to-any-good (EFX). Finding if EFX alloca- tions always exist, even for agents with additive valuations, is a major open problem in Fair Division. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph, respectively, and only the endpoints of an edge may have non-zero marginal value for it. We show that for hypergraphs with girth at least 4 and agents with general monotone valuations there always exists an EFX allocation and can be constructed in polynomial time. We generalize our approach to also show that multi-hypergraphs with girth (on the simple hypergraph) at least 4 always admit an EFX allocation, as long as there exists a single vertex whose incident edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 23 canonical work pages

[19]

Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. 2021. A Little Charity Guarantees Almost Envy-Freeness.SIAM J. Comput.50, 4 (2021), 1336–1358. doi:10.1137/20M1359134

doi:10.1137/20m1359134 2021
[1]

Mahyar Afshinmehr, Arash Ashuri, Pouria Mahmoudkhan, and Kurt Mehlhorn. 2025. EFX Allocations Exist on Triangle-Free Multi-Graphs. arXiv:2512.21644 [cs.GT]https://arxiv.org/abs/2512.21644

arXiv 2025
[2]

Mahyar Afshinmehr, Arash Ashuri, Pouria Mahmoudkhan, Kurt Mehlhorn, and Amir Mohammad Shahrezaei

work page
[3]

Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. 2025. EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture. InAAMAS. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 32–40

work page 2025
[5]

V oudouris

Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. V oudouris

work page
[6]

Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. 2024. Pushing the Frontier on Approximate EFX Allocations. InProceedings of the 25th ACM Conference on Economics and Computation, EC

work page 2024
[7]

Haris Aziz and Simon Mackenzie. 2016. A discrete and bounded envy-free cake cutting protocol for four agents. InProceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Daniel Wichs and Yishay Mansour (Eds.). ACM.https://doi.org/10.1145/2897518.2897522

arXiv 2016
[8]

Moshe Babaioff, Tomer Ezra, and Uriel Feige. 2021. Fair and Truthful Mechanisms for Dichotomous Valuations. InThirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Vir...

doi:10.1609/aaai.v35i6 2021

Show all 47 references

[9]

Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma. 2022. Fixed-Point Cycles and Approx- imate EFX Allocations. In47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria (LIPIcs, Vol. 241), Stefa...

2022 doi
[10]

1973.Graphs and Hypergraphs

Claude Berge. 1973.Graphs and Hypergraphs. North-Holland, Amsterdam

1973
[11]

Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. 2022. Almost Full EFX Exists for Four Agents. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Sy...

2022
[12]

Umang Bhaskar and Yeshwant Pandit. 2025. Extending EFX Allocations to Further Multi-Graph Classes. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) (Leibniz International Proceedings in Informatics (LIPIcs), V...

2025 doi
[13]

Václav Blažej, Sushmita Gupta, M. S. Ramanujan, and Peter Strulo. 2025. Tractable Graph Structures in EFX Orientation. InAlgorithmic Game Theory: 18th International Symposium, SAGT 2025, Bath, UK, September 2–5, 2025, Proceedings(Bath, United Kingdom). Springer-Verlag, Be...

2025 doi
[14]

Eric Budish. 2010. The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. InProceedings of the Behavioral and Quantitative Game Theory - Conference on Future Directions, BQGT ’10, Newport Beach, California, USA, May 14-16, 2010, Moshe Dro...

2010
[15]

Ioannis Caragiannis, Nick Gravin, and Xin Huang. 2019. Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items. InProceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, Anna R. Karlin, Nicole ...

2019
[16]

Procaccia, Nisarg Shah, and Junxing Wang

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang
[17]

Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. 2024. EFX Exists for Three Agents.J. ACM71, 1 (2024), 4:1–4:27. doi:10.1145/3616009 13

2024 doi
[18]

Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. 2021. Improving EFX Guarantees through Rainbow Cycle Number. InEC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, Péter Biró, Shuchi Chawla, and ...

2021
[20]

George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. 2023. Fair allocation in graphs. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, Kevin Leyton-Brown, Jason D. Hartline, and Larr...

2023
[21]

George Christodoulou and Symeon Mastrakoulis. 2026. Exact and Approximate Maximin Share Allocations in Multi-Graphs. InFortieth AAAI Conference on Artificial Intelligence, Thirty-Eighth Conference on Innovative Applications of Artificial Intelligence, Sixteenth Symposium on Ed...

2026 doi
[22]

Giorgos Christodoulou, Symeon Mastrakoulis, Alkmini Sgouritsa, and Minas Marios Sotiriou. 2026. EFX allocations on multigraphs. InProceedings of the 27th ACM Conference on Economics and Computation(Rome, Italy)

2026
[23]

Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, and Viktoriia Korchemna. 2025. EF1 and EFX Orien- tations. InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. International Joint Conferences on Artificial Intelligence ...

2025 doi
[24]

Uriel Feige. 2025. From multi-allocations to allocations, with subadditive valuations. arXiv:2506.21493 [cs.GT] https://arxiv.org/abs/2506.21493

2025 arXiv
[25]

1966.Resource allocation and the public sector

Duncan Karl Foley. 1966.Resource allocation and the public sector. Yale University

1966
[26]

Gamow and M

G. Gamow and M. Stern. 1958.Puzzle-math. Viking Press. https://books.google.gr/books?id= _vdytgAACAAJ

1958
[27]

Laurent Gourvès, Jérôme Monnot, and Lydia Tlilane. 2014. Near Fairness in Matroids. InECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic - Includ- ing Prestigious Applications of Intelligent Systems (PAIS 2014) (Frontiers...

2014 doi
[28]

Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. 2021. Fair and Efficient Allocations under Lex- icographic Preferences. InThirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence...

2021 doi
[29]

Kevin Hsu. 2024. EFX Orientations of Multigraphs. arXiv:2410.12039 [cs.GT] https://arxiv.org/abs/ 2410.12039

2024
[30]

Vishwa Prakash Hv, Pratik Ghosal, Prajakta Nimbhorkar, and Nithin Varma. 2025. EFX Exists for Three Types of Agents. InProceedings of the 26th ACM Conference on Economics and Computation(Stanford University, Stanford, CA, USA)(EC ’25). Association for Computing Machinery, New ...

2025
[31]

Shayan Chashm Jahan, Masoud Seddighin, Seyed Mohammad Seyed Javadi, and Mohammad Sharifi. 2023. Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap. InProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25...

2023 doi
[32]

Sotiris Kanellopoulos, Edouard Nemery, Christos Pergaminelis, Minas Marios Sotiriou, and Manolis Vasilakis
[33]

Alireza Kaviani, Alireza Keshavarz, Masoud Seddighin, and AmirMohammad Shahrezaei. 2025. Improved Approximate EFX Guarantees for Multigraphs. arXiv:2506.09288 [cs.GT] https://arxiv.org/abs/2506. 09288 14

2025 arXiv
[34]

Alireza Kaviani, Masoud Seddighin, and AmirMohammad Shahrezaei. 2024. Almost Envy-Free Allocation of Indivisible Goods: A Tale of Two Valuations. InWINE (Lecture Notes in Computer Science, Vol. 15534). Springer, 261–276

2024
[35]

Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi

Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. InEC. ACM, 125–131

2004
[36]

Benjamin Plaut and Tim Roughgarden. 2020. Almost Envy-Freeness with General Valuations.SIAM J. Discret. Math.34, 2 (2020), 1039–1068. doi:10.1137/19M124397X

2020 doi
[37]

Procaccia

Ariel D. Procaccia. 2020. An answer to fair division’s most enigmatic question: technical perspective.Commun. ACM63, 4 (2020), 118. doi:10.1145/3382131

2020 doi
[38]

Alkmini Sgouritsa and Minas Marios Sotiriou. 2025. On the Existence of EFX Allocations in Multigraphs. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems(Detroit, MI, USA)(AAMAS ’25). International Foundation for Autonomous Agents a...

2025
[39]

Hugo Steinhaus. 1948. The problem of fair division.Econometrica16 (1948), 101–104

1948
[40]

Stromquist

Walter R. Stromquist. 1980. How to Cut a Cake Fairly.Amer. Math. Monthly87 (1980), 640–644. https: //doi.org/10.1080/00029890.1980.11995109

1980
[41]

Hal R Varian. 1974. Equity, envy, and efficiency.Journal of Economic Theory9, 1 (1974), 63–91. doi: 10.1016/ 0022-0531(74)90075-1

1974
[42]

D.R Woodall. 1980. Dividing a cake fairly.J. Math. Anal. Appl.78, 1 (1980), 233–247. doi: 10.1016/ 0022-247X(80)90225-5

1980
[43]

Zeng and Ruta Mehta

Jinghan A. Zeng and Ruta Mehta. 2025. On the Structure of EFX Orientations on Graphs. InAAMAS. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2309–2316

2025
[44]

Yu Zhou, Tianze Wei, Minming Li, and Bo Li. 2024. A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna. InIJCAI. 3049–3056. A Subroutine 7 (Algorithm 3 of [19]) Subroutine 7Finding an inclusion-wise minimal envied subset from a patch (Algorithm 3 [1...

2024
[2019]

Economics and Comput.7, 3 (2019), 12:1–12:32

The Unreasonable Fairness of Maximum Nash Welfare.ACM Trans. Economics and Comput.7, 3 (2019), 12:1–12:32. doi:10.1145/3355902

2019 doi
[2021]

Maximum Nash welfare and other stories about EFX.Theor. Comput. Sci.863 (2021), 69–85. https: //doi.org/10.1016/j.tcs.2021.02.020

2021 doi
[2025]

arXiv:2512.25033 [cs.DS] https: //arxiv.org/abs/2512.25033

EF(X) Orientations: A Parameterized Complexity Perspective. arXiv:2512.25033 [cs.DS] https: //arxiv.org/abs/2512.25033

arXiv
[2026]

InProceedings of the 27th ACM Conference on Economics and Computation(Rome, Italy)

EFX Allocations Exist on Multi-Graphs. InProceedings of the 27th ACM Conference on Economics and Computation(Rome, Italy). 12

Pith tools

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

[1] [19]

Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. 2021. A Little Charity Guarantees Almost Envy-Freeness.SIAM J. Comput.50, 4 (2021), 1336–1358. doi:10.1137/20M1359134

doi:10.1137/20m1359134 2021

[2] [1]

Mahyar Afshinmehr, Arash Ashuri, Pouria Mahmoudkhan, and Kurt Mehlhorn. 2025. EFX Allocations Exist on Triangle-Free Multi-Graphs. arXiv:2512.21644 [cs.GT]https://arxiv.org/abs/2512.21644

arXiv 2025

[3] [2]

Mahyar Afshinmehr, Arash Ashuri, Pouria Mahmoudkhan, Kurt Mehlhorn, and Amir Mohammad Shahrezaei

work page

[4] [3]

Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. 2025. EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture. InAAMAS. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 32–40

work page 2025

[5] [5]

V oudouris

Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. V oudouris

work page

[6] [6]

Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. 2024. Pushing the Frontier on Approximate EFX Allocations. InProceedings of the 25th ACM Conference on Economics and Computation, EC

work page 2024

[7] [7]

Haris Aziz and Simon Mackenzie. 2016. A discrete and bounded envy-free cake cutting protocol for four agents. InProceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Daniel Wichs and Yishay Mansour (Eds.). ACM.https://doi.org/10.1145/2897518.2897522

arXiv 2016

[8] [8]

Moshe Babaioff, Tomer Ezra, and Uriel Feige. 2021. Fair and Truthful Mechanisms for Dichotomous Valuations. InThirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Vir...

doi:10.1609/aaai.v35i6 2021