Almost EFX in Hypergraphs

Alkmini Sgouritsa; Ioannis Kakatelis; Minas Marios Sotiriou; Thanasis Lianeas

arxiv: 2606.26948 · v1 · pith:XPNYFGTTnew · submitted 2026-06-25 · 💻 cs.GT

Almost EFX in Hypergraphs

Ioannis Kakatelis , Thanasis Lianeas , Alkmini Sgouritsa , Minas Marios Sotiriou This is my paper

Pith reviewed 2026-06-26 02:03 UTC · model grok-4.3

classification 💻 cs.GT

keywords EFX allocationshypergraphsindivisible goodsfair divisionmonotone valuationsadditive valuationsenvy-free up to any good

0 comments

The pith

EF2X allocations exist for monotone valuations in hypergraphs with girth at least 3, and EF3X for additive valuations when each edge has multiplicity 2.

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

The paper establishes existence and efficient constructions of nearly envy-free allocations of indivisible goods in multi-hypergraph settings that restrict how goods connect agents. In hypergraphs with girth at least 3, an EF2X allocation can be found in polynomial time for any monotone valuations. When every edge appears exactly twice, the authors prove that EF3X allocations exist for additive valuations and that 2/3-EFX allocations exist, both constructible in polynomial or pseudo-polynomial time. A sympathetic reader cares because full EFX remains open in general, so these structural restrictions on the hypergraph make concrete progress toward fair division in models that capture limited value dependencies among agents.

Core claim

We provide a simpler construction of EF2X allocation for general monotone valuations in hypergraphs with girth at least 3. We extend our ideas when the multiplicity of each edge is 2 and show that an EF3X allocation always exists for additive valuations. We provide a simpler construction for sqrt(2)/2-EFX allocations in hypergraphs of girth at least 3 under subadditive valuations. We establish the existence of 2/3-EFX allocations for additive valuations when the edge multiplicity is 2. Both of the latter results can be constructed in pseudo-polynomial time.

What carries the argument

The multi-hypergraph model with vertices as agents and edges as goods (value nonzero only for incident endpoints), together with constructions that use girth at least 3 or exact multiplicity 2 to bound and resolve envy.

If this is right

Polynomial-time EF2X allocations exist for monotone valuations in girth-at-least-3 hypergraphs.
Polynomial-time EF3X allocations exist for additive valuations when edge multiplicity is exactly 2.
Pseudo-polynomial-time 2/3-EFX allocations exist for additive valuations when edge multiplicity is 2.
A simpler pseudo-polynomial-time construction yields sqrt(2)/2-EFX allocations for subadditive valuations in girth-at-least-3 hypergraphs.

Where Pith is reading between the lines

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

The girth restriction prevents short cycles of shared goods that could force unbounded envy propagation.
Exact multiplicity 2 creates a controlled form of repeated dependencies that the allocation algorithms can exploit to cap envy at a constant factor.
These two structural conditions may be combinable or relaxed to higher girth values while preserving the same approximation guarantees.

Load-bearing premise

The input hypergraph has girth at least 3 or every edge has multiplicity exactly 2.

What would settle it

A hypergraph with girth at least 3 together with monotone valuations for which no EF2X allocation exists, or a multiplicity-2 hypergraph with additive valuations for which no 2/3-EFX allocation exists.

read the original abstract

We study the existence of envy-free-up-to-any-good (EFX) allocations of indivisible goods among agents with heterogeneous monotone valuations. 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. Our work simplifies and extends previous results of Kaviani et al. (Alireza Kaviani, Masoud Seddighin, Amir Mohammad Shahrezaei. Almost Envy-Free Allocation of Indivisible Goods: A Tale of Two Valuations. WINE 2024) in this domain. First, we provide a simpler construction of EF2X allocation for general monotone valuations in hypergraphs with girth at least 3. We extend our ideas when the multiplicity of each edge is 2 and show that an EF3X allocation always exists for additive valuations. Both results can be constructed in polynomial time. Regarding EFX approximations, we provide a simpler construction for $\frac{\sqrt{2}}{2}$-EFX allocations in hypergraphs of girth at least 3 under subadditive valuations. We push the state-of-the-art by establishing the existence of $\frac{2}{3}$-EFX allocations for additive valuations when the edge multiplicity is 2. Both of the latter results can be constructed in pseudo-polynomial time. By addressing these multi-hypergraph settings, our work contributes to the ongoing effort to resolve the existence of EFX in increasingly general and applicable domains.

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

Incremental simplifications and a 2/3-EFX improvement under multiplicity-2 restrictions, but still scoped to narrow hypergraph cases.

read the letter

The paper gives simpler constructions for EF2X allocations under girth at least 3 for monotone valuations and shows EF3X existence plus a 2/3-EFX guarantee for additive valuations when every edge has multiplicity exactly 2. Both run in polynomial or pseudo-polynomial time. It also gives a simpler sqrt(2)/2-EFX result for subadditive valuations in the girth-3 case. These are framed as direct extensions of Kaviani et al. (WINE 2024).

What stands out is the clean scoping: the authors state the structural restrictions up front and do not pretend the results apply to arbitrary hypergraphs. The 2/3-EFX bound for multiplicity 2 is a modest but concrete improvement over prior approximation factors in that setting, and the claim of simpler constructions is at least plausible from the abstract.

The main limitation is that only the abstract is visible here, so the actual proofs and algorithm details cannot be checked. The girth and multiplicity conditions are load-bearing, which the paper acknowledges rather than hides. No internal contradictions or overclaims jump out from the description.

This is for people already working on fair division in graphs and hypergraphs. It is a small, honest step that does not solve the general EFX question but tightens some bounds in restricted models. It deserves peer review so the constructions can be verified.

Referee Report

0 major / 3 minor

Summary. The paper studies the existence of almost envy-free-up-to-any-good (EFX) allocations of indivisible goods in multi-hypergraph settings, where agents and goods correspond to vertices and edges with restricted valuations. It claims simpler constructions for EF2X allocations for general monotone valuations in hypergraphs with girth at least 3, EF3X allocations for additive valuations when each edge has multiplicity exactly 2, a √2/2-EFX guarantee for subadditive valuations under girth ≥3, and a 2/3-EFX guarantee for additive valuations under multiplicity 2, with the first two results in polynomial time and the approximation results in pseudo-polynomial time.

Significance. If the claimed constructions and existence proofs hold under the stated structural restrictions, the work simplifies prior results from Kaviani et al. (WINE 2024) and extends the domain of almost-EFX guarantees, contributing incremental progress toward resolving EFX existence in increasingly general settings. The explicit polynomial-time and pseudo-polynomial-time bounds, along with the open declaration of the girth and multiplicity restrictions, are strengths.

minor comments (3)

§1 (Introduction): the statement that the new EF2X construction is 'simpler' should be supported by a brief comparison of proof length or technique to Kaviani et al., rather than left as a qualitative claim.
The abstract and §3 claim polynomial-time construction for EF3X under multiplicity 2; the manuscript should explicitly state the dependence on the number of agents and goods (e.g., O(nm) or similar) to allow verification of the runtime bound.
Notation for hypergraph multiplicity and girth is introduced without a dedicated preliminary section; a short definitions paragraph before the main theorems would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript, accurate summary of the contributions, and recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents algorithmic existence proofs and constructions for approximate EFX allocations (EF2X, EF3X, 2/3-EFX, etc.) under explicit structural restrictions on the input hypergraph (girth >=3 or edge multiplicity exactly 2). These are scoped to monotone or additive valuations and rely on graph-theoretic matching or partitioning arguments rather than any fitted parameters, self-definitional reductions, or load-bearing self-citations. Cited prior work is by different authors and serves as independent foundation; no equations or ansatzes reduce the claimed results to their inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are introduced; the work consists of algorithmic constructions under standard assumptions on valuations and hypergraph structure.

pith-pipeline@v0.9.1-grok · 5826 in / 1212 out tokens · 33573 ms · 2026-06-26T02:03:15.395497+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

55 extracted references · 28 canonical work pages

[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, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. 2025. EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture. InAAMAS, Sanmay Das, Ann Nowé, and Yevgeniy V orobeychik (Eds.). International Foundation for Autonomous Agents and Multiagent Systems / ACM, 32–40. doi:10.5555/3709347.3743514

work page doi:10.5555/3709347.3743514 2025
[3]

Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. 2025. EFX: a simpler approach and an (almost) optimal guarantee via rainbow cycle number.Operations Research73, 2 (2025), 738–751

2025
[4]

Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, and Christoph Weidenbach. 2026. A Counterexample to EFX; 𝑛≥3 Agents,𝑚≥𝑛+5Items, Monotone Valuations; via SAT-Solving.arXiv preprint arXiv:2604.18216(2026)

Pith/arXiv arXiv 2026
[5]

Hannaneh Akrami, Rojin Rezvan, and Masoud Seddighin. 2022. An EF2X Allocation Protocol for Restricted Additive Valuations. InProceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, Luc De Raedt (Ed.). ijcai.org, 17–23. doi:10.24963/IJCAI.2022/3

work page doi:10.24963/ijcai.2022/3 2022
[6]

Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa

Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. V oudouris, and Xiaowei Wu. 2023. Fair division of indivisible goods: Recent progress and open questions.Artif. Intell.322 (Sept. 2023), 103965. doi:10.1016/J.ARTINT.2023.103965

work page doi:10.1016/j.artint.2023.103965 2023
[7]

V oudouris

Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. V oudouris. 2021. Maximum Nash welfare and other stories about EFX.Theor. Comput. Sci.863 (2021), 69–85. doi:10.1016/J.TCS.2021.02.020

work page doi:10.1016/j.tcs.2021.02.020 2021
[8]

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

2024
[9]

Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. 2020. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.Theor. Comput. Sci.841 (2020), 94–109. doi:10.1016/J.TCS.2020.07.006

work page doi:10.1016/j.tcs.2020.07.006 2020
[10]

Arash Ashuri, Vasilis Gkatzelis, and Alkmini Sgouritsa. 2025. EF2X Exists for Four Agents. InAAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 - March 4, 2025, Philadelphia, PA, USA, Toby Walsh, Julie Shah, and Zico Kolter (Eds.). AAAI Press, 13555–13563. doi:10.1609/AAAI.V39I13.33480

work page doi:10.1609/aaai.v39i13.33480 2025
[11]

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...

work page doi:10.1609/aaai.v35i6 2021
[12]

Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma. 2022. Fixed-point cycles and approximate EFX allocations. In47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022. Schloss Dagstuhl, 17

2022
[13]

1973.Graphs and Hypergraphs

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

1973
[14]

Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. 2022. Almost Full EFX Exists for Four Agents. InThirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Eve...

work page doi:10.1609/aaai.v36i5.20410 2022
[15]

Umang Bhaskar and Yeshwant Pandit. 2025. Extending EFX Allocations to Further Multi-Graph Classes. In45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 360), C. Aiswarya, Ruta Mehta, and Subhajit Roy (Eds.). Schloss Dagstuhl – Le...

work page doi:10.4230/lipics.fsttcs.2025.15 2025
[16]

Václav Blažej, Sushmita Gupta, MS Ramanujan, and Peter Strulo. 2025. Tractable graph structures in EFX orientation. InInternational Symposium on Algorithmic Game Theory. Springer, 175–190

2025
[17]

1996.Fair Division: From cake-cutting to dispute resolution

Steven J Brams and Alan D Taylor. 1996.Fair Division: From cake-cutting to dispute resolution. Cambridge University Press. Manuscript submitted to ACM Almost EFX in Hypergraphs 31

1996
[18]

2016.Handbook of computational social choice

Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. 2016.Handbook of computational social choice. Cambridge University Press

2016
[19]

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 Dror and Greys Sosic (Eds.). ACM, 74:1. doi:10.1145/1807406.1807480

work page doi:10.1145/1807406.1807480 2010
[20]

Eric Budish and Estelle Cantillon. 2010. The Multi-Unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard.American Economic Review102 (01 2010). doi:10.1257/aer.102.5.2237

work page doi:10.1257/aer.102.5.2237 2010
[21]

Jaroslaw Byrka, Franciszek Malinka, and Tomasz Ponitka. 2026. Probing EFX via PMMS:(Non-) Existence Results in Discrete Fair Division. In Proceedings of the AAAI Conference on Artificial Intelligence, V ol. 40. 16735–16742

2026
[22]

Ioannis Caragiannis, Nick Gravin, and Xin Huang. 2019. Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, Anna R. Karlin, Nicole Immorlica, and Ramesh Johari (Eds.). ACM, 527–545. doi:10.1145/3328526.3329574

work page doi:10.1145/3328526.3329574 2019
[23]

Economics and Comput.7, 3 (2019), 12:1–12:32.https://doi.org/10.1145/3355902 Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2019. The Unreasonable Fairness of Maximum Nash Welfare.ACM Trans. Economics and Comput.7, 3 (2019), 12:1–12:32. doi:10.1145/3355902

work page doi:10.1145/3355902 2019
[24]

Hau Chan, Jing Chen, Bo Li, and Xiaowei Wu. 2019. Maximin-Aware Allocations of Indivisible Goods. InProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019, Edith Elkind, Manuela Veloso, Noa Agmon, and Matthew E. Taylor (Eds.). International Foundation for Autonomous Ag...

2019
[25]

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-23, Edith Elkind (Ed.). International Joint Conferences on Artificial Intelligence Organizati...

work page doi:10.24963/ijcai.2023/286 2023
[26]

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

work page doi:10.1145/3616009 2024
[27]

Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. 2024. Improving envy freeness up to any good guarantees through rainbow cycle number.Mathematics of Operations Research49, 4 (2024), 2323–2340

2024
[28]

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

work page doi:10.1137/20m1359134 2021
[29]

George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. 2023. Fair allocation in graphs. InProceedings 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 Larry Samuelson (Eds.). ACM, 473–488. doi:10.1145/3580507.3597764

work page doi:10.1145/3580507.3597764 2023
[30]

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 Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20-...

work page doi:10.1609/aaai.v40i20.38719 2026
[31]

Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, and Viktoriia Korchemna. 2025. EF1 and EFX Orientations. InProceedings of the Thirty- Fourth International Joint Conference on Artificial Intelligence, IJCAI-25(Montreal, Canada)(IJCAI ’25). International Joint Conferences on Artificial Intelligence Organization, Article 7, 8 pages. doi:10.24963/ijcai...

work page doi:10.24963/ijcai.2025/7 2025
[32]

Uriel Feige. 2025. From multi-allocations to allocations, with subadditive valuations.CoRRabs/2506.21493 (2025). arXiv:2506.21493 doi:10.48550/ ARXIV .2506.21493

arXiv 2025
[33]

Aris Filos-Ratsikas, Georgios Kalantzis, and Fangxiao Wang. 2026. Approximate Envy-Free Allocations up to any𝑘 Goods. arXiv:2605.10371 [cs.GT] https://arxiv.org/abs/2605.10371

Pith/arXiv arXiv 2026
[34]

1966.Resource allocation and the public sector

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

1966
[35]

Gamow and M

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

1958
[36]

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 - Including Prestigious Applications of Intelligent Systems (PAIS 2014) (Frontiers in Artificial Intelligence and Applications, Vol. 263), Torsten Schaub, Gerhard F...

work page doi:10.3233/978-1- 2014
[37]

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

arXiv 2024
[38]

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 York, NY , USA, 101–128. doi:10.1145/3736252.3742509

work page doi:10.1145/3736252.3742509 2025
[39]

Vishwa Prakash HV , Ruta Mehta, and Prajakta Nimbhorkar. 2025. Almost and Approximate EFX for Few Types of Agents.arXiv preprint arXiv:2508.15380(2025)

arXiv 2025
[40]

Sotiris Kanellopoulos, Edouard Nemery, Christos Pergaminelis, Minas Marios Sotiriou, and Manolis Vasilakis. 2025. EF (X) Orientations: A Parameterized Complexity Perspective.arXiv preprint arXiv:2512.25033(2025)

arXiv 2025
[41]

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 Manuscript submitted to ACM 32 Kakatelis et al

arXiv 2025
[42]

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
[43]

Thanasis Lianeas, Alkmini Sgouritsa, and Minas Marios Sotiriou. 2026. EFX Allocation in (Multi)Hypergraphs. InFortieth AAAI Conference on Artificial Intelligence, Thirty-Eighth Conference on Innovative Applications of Artificial Intelligence, Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20-27, 2026,...

work page doi:10.1609/aaai.v40i20.38759 2026
[44]

InProceedings 5th ACM Conference on Electronic Commerce (EC-2004), New York, NY, USA, May 17-20, 2004, Jack S

Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. InEC, Jack S. Breese, Joan Feigenbaum, and Margo I. Seltzer (Eds.). ACM, 125–131. doi:10.1145/988772.988792

work page doi:10.1145/988772.988792 2004
[45]

Simon Mackenzie and Mashbat Suzuki. 2026. Counterexamples to EFX for Submodular and Subadditive Valuations. arXiv:2605.06451 [cs.GT] https://arxiv.org/abs/2605.06451

Pith/arXiv arXiv 2026
[46]

Ryoga Mahara. 2024. Extension of Additive Valuations to General Valuations on the Existence of EFX.Math. Oper. Res.49, 2 (2024), 1263–1277. doi:10.1287/MOOR.2022.0044

work page doi:10.1287/moor.2022.0044 2024
[47]

Evangelos Markakis and Christodoulos Santorinaios. 2023. Improved EFX Approximation Guarantees under Ordinal-based Assumptions. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, London, United Kingdom, 29 May 2023 - 2 June 2023, Noa Agmon, Bo An, Alessandro Ricci, and William Yeoh (Eds.). ACM, 591...

work page doi:10.5555/3545946.3598689 2023
[48]

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

work page doi:10.1137/19m124397x 2020
[49]

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
[50]

1998.Cake-cutting algorithms: Be fair if you can

Jack Robertson and William Webb. 1998.Cake-cutting algorithms: Be fair if you can. AK Peters/CRC Press

1998
[51]

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

2025
[52]

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

1948
[53]

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

work page doi:10.1016/0022-0531(74)90075-1 1974
[54]

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
[55]

Yu Zhou, Tianze Wei, Minming Li, and Bo Li. 2024. A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna. In IJCAI, Kate Larson (Ed.). International Joint Conferences on Artificial Intelligence Organization, Jeju, Korea, 3049–3056. doi:10.24963/ijcai.2024/338 Main Track. Manuscript submitted to ACM Almost EFX in Hypergraphs 33 A ...

work page doi:10.24963/ijcai.2024/338 2024

[1] [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] [2]

Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. 2025. EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture. InAAMAS, Sanmay Das, Ann Nowé, and Yevgeniy V orobeychik (Eds.). International Foundation for Autonomous Agents and Multiagent Systems / ACM, 32–40. doi:10.5555/3709347.3743514

work page doi:10.5555/3709347.3743514 2025

[3] [3]

Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. 2025. EFX: a simpler approach and an (almost) optimal guarantee via rainbow cycle number.Operations Research73, 2 (2025), 738–751

2025

[4] [4]

Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, and Christoph Weidenbach. 2026. A Counterexample to EFX; 𝑛≥3 Agents,𝑚≥𝑛+5Items, Monotone Valuations; via SAT-Solving.arXiv preprint arXiv:2604.18216(2026)

Pith/arXiv arXiv 2026

[5] [5]

Hannaneh Akrami, Rojin Rezvan, and Masoud Seddighin. 2022. An EF2X Allocation Protocol for Restricted Additive Valuations. InProceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, Luc De Raedt (Ed.). ijcai.org, 17–23. doi:10.24963/IJCAI.2022/3

work page doi:10.24963/ijcai.2022/3 2022

[6] [6]

Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa

Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. V oudouris, and Xiaowei Wu. 2023. Fair division of indivisible goods: Recent progress and open questions.Artif. Intell.322 (Sept. 2023), 103965. doi:10.1016/J.ARTINT.2023.103965

work page doi:10.1016/j.artint.2023.103965 2023

[7] [7]

V oudouris

Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. V oudouris. 2021. Maximum Nash welfare and other stories about EFX.Theor. Comput. Sci.863 (2021), 69–85. doi:10.1016/J.TCS.2021.02.020

work page doi:10.1016/j.tcs.2021.02.020 2021

[8] [8]

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

2024

[9] [9]

Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. 2020. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.Theor. Comput. Sci.841 (2020), 94–109. doi:10.1016/J.TCS.2020.07.006

work page doi:10.1016/j.tcs.2020.07.006 2020

[10] [10]

Arash Ashuri, Vasilis Gkatzelis, and Alkmini Sgouritsa. 2025. EF2X Exists for Four Agents. InAAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 - March 4, 2025, Philadelphia, PA, USA, Toby Walsh, Julie Shah, and Zico Kolter (Eds.). AAAI Press, 13555–13563. doi:10.1609/AAAI.V39I13.33480

work page doi:10.1609/aaai.v39i13.33480 2025

[11] [11]

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...

work page doi:10.1609/aaai.v35i6 2021

[12] [12]

Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma. 2022. Fixed-point cycles and approximate EFX allocations. In47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022. Schloss Dagstuhl, 17

2022

[13] [13]

1973.Graphs and Hypergraphs

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

1973

[14] [14]

Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. 2022. Almost Full EFX Exists for Four Agents. InThirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Eve...

work page doi:10.1609/aaai.v36i5.20410 2022

[15] [15]

Umang Bhaskar and Yeshwant Pandit. 2025. Extending EFX Allocations to Further Multi-Graph Classes. In45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 360), C. Aiswarya, Ruta Mehta, and Subhajit Roy (Eds.). Schloss Dagstuhl – Le...

work page doi:10.4230/lipics.fsttcs.2025.15 2025

[16] [16]

Václav Blažej, Sushmita Gupta, MS Ramanujan, and Peter Strulo. 2025. Tractable graph structures in EFX orientation. InInternational Symposium on Algorithmic Game Theory. Springer, 175–190

2025

[17] [17]

1996.Fair Division: From cake-cutting to dispute resolution

Steven J Brams and Alan D Taylor. 1996.Fair Division: From cake-cutting to dispute resolution. Cambridge University Press. Manuscript submitted to ACM Almost EFX in Hypergraphs 31

1996

[18] [18]

2016.Handbook of computational social choice

Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. 2016.Handbook of computational social choice. Cambridge University Press

2016

[19] [19]

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 Dror and Greys Sosic (Eds.). ACM, 74:1. doi:10.1145/1807406.1807480

work page doi:10.1145/1807406.1807480 2010

[20] [20]

Eric Budish and Estelle Cantillon. 2010. The Multi-Unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard.American Economic Review102 (01 2010). doi:10.1257/aer.102.5.2237

work page doi:10.1257/aer.102.5.2237 2010

[21] [21]

Jaroslaw Byrka, Franciszek Malinka, and Tomasz Ponitka. 2026. Probing EFX via PMMS:(Non-) Existence Results in Discrete Fair Division. In Proceedings of the AAAI Conference on Artificial Intelligence, V ol. 40. 16735–16742

2026

[22] [22]

Ioannis Caragiannis, Nick Gravin, and Xin Huang. 2019. Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, Anna R. Karlin, Nicole Immorlica, and Ramesh Johari (Eds.). ACM, 527–545. doi:10.1145/3328526.3329574

work page doi:10.1145/3328526.3329574 2019

[23] [23]

Economics and Comput.7, 3 (2019), 12:1–12:32.https://doi.org/10.1145/3355902 Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2019. The Unreasonable Fairness of Maximum Nash Welfare.ACM Trans. Economics and Comput.7, 3 (2019), 12:1–12:32. doi:10.1145/3355902

work page doi:10.1145/3355902 2019

[24] [24]

Hau Chan, Jing Chen, Bo Li, and Xiaowei Wu. 2019. Maximin-Aware Allocations of Indivisible Goods. InProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019, Edith Elkind, Manuela Veloso, Noa Agmon, and Matthew E. Taylor (Eds.). International Foundation for Autonomous Ag...

2019

[25] [25]

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-23, Edith Elkind (Ed.). International Joint Conferences on Artificial Intelligence Organizati...

work page doi:10.24963/ijcai.2023/286 2023

[26] [26]

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

work page doi:10.1145/3616009 2024

[27] [27]

Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. 2024. Improving envy freeness up to any good guarantees through rainbow cycle number.Mathematics of Operations Research49, 4 (2024), 2323–2340

2024

[28] [28]

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

work page doi:10.1137/20m1359134 2021

[29] [29]

George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. 2023. Fair allocation in graphs. InProceedings 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 Larry Samuelson (Eds.). ACM, 473–488. doi:10.1145/3580507.3597764

work page doi:10.1145/3580507.3597764 2023

[30] [30]

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 Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20-...

work page doi:10.1609/aaai.v40i20.38719 2026

[31] [31]

Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, and Viktoriia Korchemna. 2025. EF1 and EFX Orientations. InProceedings of the Thirty- Fourth International Joint Conference on Artificial Intelligence, IJCAI-25(Montreal, Canada)(IJCAI ’25). International Joint Conferences on Artificial Intelligence Organization, Article 7, 8 pages. doi:10.24963/ijcai...

work page doi:10.24963/ijcai.2025/7 2025

[32] [32]

Uriel Feige. 2025. From multi-allocations to allocations, with subadditive valuations.CoRRabs/2506.21493 (2025). arXiv:2506.21493 doi:10.48550/ ARXIV .2506.21493

arXiv 2025

[33] [33]

Aris Filos-Ratsikas, Georgios Kalantzis, and Fangxiao Wang. 2026. Approximate Envy-Free Allocations up to any𝑘 Goods. arXiv:2605.10371 [cs.GT] https://arxiv.org/abs/2605.10371

Pith/arXiv arXiv 2026

[34] [34]

1966.Resource allocation and the public sector

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

1966

[35] [35]

Gamow and M

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

1958

[36] [36]

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 - Including Prestigious Applications of Intelligent Systems (PAIS 2014) (Frontiers in Artificial Intelligence and Applications, Vol. 263), Torsten Schaub, Gerhard F...

work page doi:10.3233/978-1- 2014

[37] [37]

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

arXiv 2024

[38] [38]

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 York, NY , USA, 101–128. doi:10.1145/3736252.3742509

work page doi:10.1145/3736252.3742509 2025

[39] [39]

Vishwa Prakash HV , Ruta Mehta, and Prajakta Nimbhorkar. 2025. Almost and Approximate EFX for Few Types of Agents.arXiv preprint arXiv:2508.15380(2025)

arXiv 2025

[40] [40]

Sotiris Kanellopoulos, Edouard Nemery, Christos Pergaminelis, Minas Marios Sotiriou, and Manolis Vasilakis. 2025. EF (X) Orientations: A Parameterized Complexity Perspective.arXiv preprint arXiv:2512.25033(2025)

arXiv 2025

[41] [41]

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 Manuscript submitted to ACM 32 Kakatelis et al

arXiv 2025

[42] [42]

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

[43] [43]

Thanasis Lianeas, Alkmini Sgouritsa, and Minas Marios Sotiriou. 2026. EFX Allocation in (Multi)Hypergraphs. InFortieth AAAI Conference on Artificial Intelligence, Thirty-Eighth Conference on Innovative Applications of Artificial Intelligence, Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20-27, 2026,...

work page doi:10.1609/aaai.v40i20.38759 2026

[44] [44]

InProceedings 5th ACM Conference on Electronic Commerce (EC-2004), New York, NY, USA, May 17-20, 2004, Jack S

Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. InEC, Jack S. Breese, Joan Feigenbaum, and Margo I. Seltzer (Eds.). ACM, 125–131. doi:10.1145/988772.988792

work page doi:10.1145/988772.988792 2004

[45] [45]

Simon Mackenzie and Mashbat Suzuki. 2026. Counterexamples to EFX for Submodular and Subadditive Valuations. arXiv:2605.06451 [cs.GT] https://arxiv.org/abs/2605.06451

Pith/arXiv arXiv 2026

[46] [46]

Ryoga Mahara. 2024. Extension of Additive Valuations to General Valuations on the Existence of EFX.Math. Oper. Res.49, 2 (2024), 1263–1277. doi:10.1287/MOOR.2022.0044

work page doi:10.1287/moor.2022.0044 2024

[47] [47]

Evangelos Markakis and Christodoulos Santorinaios. 2023. Improved EFX Approximation Guarantees under Ordinal-based Assumptions. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, London, United Kingdom, 29 May 2023 - 2 June 2023, Noa Agmon, Bo An, Alessandro Ricci, and William Yeoh (Eds.). ACM, 591...

work page doi:10.5555/3545946.3598689 2023

[48] [48]

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

work page doi:10.1137/19m124397x 2020

[49] [49]

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

[50] [50]

1998.Cake-cutting algorithms: Be fair if you can

Jack Robertson and William Webb. 1998.Cake-cutting algorithms: Be fair if you can. AK Peters/CRC Press

1998

[51] [51]

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

2025

[52] [52]

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

1948

[53] [53]

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

work page doi:10.1016/0022-0531(74)90075-1 1974

[54] [54]

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

[55] [55]

Yu Zhou, Tianze Wei, Minming Li, and Bo Li. 2024. A Complete Landscape of EFX Allocations on Graphs: Goods, Chores and Mixed Manna. In IJCAI, Kate Larson (Ed.). International Joint Conferences on Artificial Intelligence Organization, Jeju, Korea, 3049–3056. doi:10.24963/ijcai.2024/338 Main Track. Manuscript submitted to ACM Almost EFX in Hypergraphs 33 A ...

work page doi:10.24963/ijcai.2024/338 2024