EF2X Exists For Four Agents

Alkmini Sgouritsa; Arash Ashuri; Vasilis Gkatzelis

REVIEW 4 major objections 4 minor 23 references

EF2X Exists For Four Agents

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

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

Pith's one-line read An EF2X allocation is guaranteed for every four-agent instance with cancelable valuations, and it can be computed in pseudo-polynomial time.

desk verdict A genuine first EF2X guarantee for four agents with cancelable valuations; the existence proof looks solid but the pseudo-polynomial runtime claim needs an integrality assumption. read the letter →

arxiv 2412.00254 v2 pith:75IUD3BX submitted 2024-11-29 cs.GT

Arash Ashuri , Vasilis Gkatzelis , Alkmini Sgouritsa This is my paper · ORCID

classification cs.GT MSC 91B32

keywords EF2Xcancelablevaluationsfairdivisionindivisiblegoodsenvy-freeuptoanytwofouragentspseudo-polynomialalgorithmEFX

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that EF2X allocations always exist for instances with four agents, any number of indivisible goods, and cancelable valuations—a class that strictly contains additive valuations. The proof is constructive, following an algorithm that starts from an arbitrary partition and modifies it through a sequence of stages until each bundle is EF2X-feasible for the agent it is assigned to. A potential function based on agent 1's value for bundle 1 is shown to increase strictly on every progress step, which yields a pseudo-polynomial runtime. If the result stands, it closes the four-agent question for EF2X, a case that had remained open even for additive valuations, and it leaves the analogous EFX question as the next target.

What carries the argument

The load-bearing mechanism is a staged local-search algorithm on partitions of the good set. The algorithm uses EFkX-best bundles, meaning bundles that maximize the value after removing k of an agent's least-liked goods, plus a swap-optimization subroutine that exchanges goods between two bundles whenever both associated agents weakly prefer the other good. It also uses the Plaut-Roughgarden algorithm as a subroutine to make all bundles EFX-feasible for agent 1. The potential φ(X)=v1(X1) never decreases, and every transition that loops back to an in-stage partition strictly increases it, which bounds the number of strict increases and gives the pseudo-polynomial runtime.

What would settle it

A direct counterexample would be a four-agent instance with three cancelable valuations, one arbitrary monotone valuation, and a finite set of goods for which every complete allocation leaves some agent EF2X-envious of another; if such an instance exists, Theorem 3.1 is false. Short of that, one can test the runtime claim by checking whether the algorithm's strict potential increases can be made to grow faster than a polynomial in the input size on a family of small additive instances.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.1: for every instance with four agents, three of whom have cancelable valuations and one arbitrary monotone valuation, and any number of goods, there exists an EF2X allocation that can be computed in pseudo-polynomial time. The algorithm produces a full allocation, not a partial one, and often the returned allocation is actually EFX rather than merely EF2X. As a secondary contribution, the same techniques give a polynomial-time algorithm for EF2X with three cancelable agents.

Load-bearing premise

The running-time argument requires that agent 1's valuation has a positive minimum gap between any two distinct bundle values; for arbitrary real-valued inputs the paper does not explicitly justify where this gap comes from, so the pseudo-polynomial guarantee as stated is only fully supported under an integrality or bounded-gap assumption.

Editorial extensions

If this is right

For four agents, EF2X is guaranteed to exist in full generality, with only three of the four agents required to have cancelable valuations.
The algorithm's output is a completely allocated EF2X partition, so no goods are donated or thrown away.
The same constructive machinery gives a polynomial-time EF2X algorithm for three agents, where known EFX algorithms are only pseudo-polynomial.
Because the computed allocation is often EFX, the proof doubles as partial progress toward the still-open EFX existence question for four agents.
The result highlights EF2X as a meaningful relaxation that can be certified even when EFX is not yet available.

Reading between the lines

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

Editorial inference: if one restricts to rational or integer valuations, the δ-based potential bound becomes a genuine pseudo-polynomial guarantee; the real-valued statement needs a small additional hypothesis about the valuation gap.
Editorial inference: the stage framework identifies the final matching step as the main obstruction to four-agent EFX, and replacing the EF2X matching condition with an EFX one would settle that open problem.
Editorial inference: a testable extension is to run the same stage decomposition with a potential that tracks a different agent or a different bundle, which may make the approach scale beyond four agents.
Editorial inference: because cancelable valuations contain additive ones, the result immediately covers all additive four-agent instances and suggests that EF2X may hold for any fixed number of agents under cancelability.

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

Main takeaway: this is a real result. It proves EF2X exists for four agents with cancelable valuations, and only needs three of them cancelable. That is the first guarantee of this kind beyond very restricted additive classes, so it advances a question people care about. The proof is long, but it has a clear stage structure, and the case analysis is internally consistent as far as I can tell. The new techniques (EFkX-best bundles, swap-optimization) are genuinely useful and likely to outlive this application.

Where it gets soft: the pseudo-polynomial runtime claim in Theorem 3.1 is not justified as written. Section 3.9 defines δ and Δ as minimum gaps between distinct bundle values, then bounds PR iterations and cycle counts by v(M)/δ and v1(M)/Δ. But valuations are defined as real-valued in Section 2, and no integrality or bounded-precision assumption is stated. For real inputs those gaps can be exponentially small, so the bound is not pseudo-polynomial. This is a real flaw in the computational claim, but it does not touch the existence argument, which is the main contribution. The fix is straightforward: either state a rationality/integrality assumption or drop the pseudo-polynomial claim and say the algorithm terminates in finite time (which follows since potential is strictly increasing over a finite set). The 'not hard to verify' step about a polynomial number of PR executions per edge is minor; if the stage graph and the per-transition bounds check out, that will close.

I also want to note the paper cites the relevant recent work, including the parallel HV et al. result, and it doesn't oversell by claiming EFX. The 3-agent polynomial-time algorithm is a nice secondary result, though it depends on the same modified PR lemma, which is proven.

Bottom line: this deserves a serious referee. The existence theorem is likely correct and is a meaningful step in a notoriously hard area. The runtime claim needs a fix before publication, but that's a revision, not a rejection. If I were the editor, I'd send it out and expect the authors to add an integrality assumption or weaken the theorem statement.

Referee Report

4 major / 4 minor

Summary. The paper studies the existence and computation of EF2X allocations (envy-free up to any two goods) in discrete fair division. Its main result, Theorem 3.1, states that for every instance with four agents in which at least three agents have cancelable valuations (and one has an arbitrary monotone valuation), an EF2X allocation exists and can be computed in pseudo-polynomial time. The proof is constructive and organized as a staged algorithm: starting from an arbitrary partition, it applies a sequence of transformations (described in a flowchart with stages A, B, B1, B2, B2i, B2ii) driven by a potential function equal to agent 1's value for the first bundle. The paper also gives a secondary result, Theorem 4.1, claiming a polynomial-time algorithm for three agents with cancelable valuations.

Significance. If the existence proof is correct, this is a substantial advance for a central open direction in fair division. EF2X is a natural relaxation of EFX, and establishing existence for four agents under cancelable valuations—a strict generalization of additive valuations—significantly extends the frontier of known existence results. The paper introduces reusable techniques: EFkX-best bundles, swap-optimization, and partition-transformation lemmas based on the Plaut–Roughgarden local search, which may be useful for the still-open EFX problem. The central existential argument is a long case analysis that appears internally consistent; it does not rely on circular reasoning and explicitly builds on external results (e.g., cancelable valuations being MMS-feasible) rather than on the target theorem. The main weaknesses are in the computational claims: the pseudo-polynomial runtime proof is not fully justified for the stated model of real-valued valuations, and the polynomial-time three-agent construction has an under-specified initialization step.

major comments (4)

[Section 3.9, Theorem 3.49; Theorem 3.1] The pseudo-polynomial runtime guarantee is not justified under the paper's stated model. Section 2 defines valuations as real-valued functions vi: 2^M → R_{\ge 0}, with no integrality, rationality, or precision assumption. The proof in Section 3.9 defines δ = min_{S,T: v(S) ≠ v(T)} |v(S)-v(T)| for PR runs and Δ = min_{S,T: v1(S) ≠ v1(T)} |v1(S)-v1(T)| for the potential, and bounds the number of steps by m·n·v(M)/δ and the number of cycles by v1(M)/Δ. For arbitrary real inputs, δ and Δ can be arbitrarily small (e.g., 2^{-2^m}), and for degenerate valuations δ may be undefined. The paper needs an explicit assumption that valuations are integer-valued or rational with a bounded-precision input model, together with a lower bound on the minimum gap for the valuations on which PR is run. Without this, 'pseudo-polynomial' is not well-defined and the computational claim of Theorem 3.1 is overclaimed.
[Section 3.9, final paragraph] The runtime proof asserts without proof that 'it is not hard to verify that, except running time of PR algorithm, all other operations in every edge run in polynomial time. Also, every PR algorithm runs in pseudo-polynomial time, and we will have a polynomial number of executions of PR algorithm at every edge of Figure 1.' This is load-bearing for Theorem 3.49: the number of PR invocations per edge must be bounded explicitly. While the repeat loop in Theorem 3.33 runs at most m times, other edges (e.g., the PR calls in Lemmas 3.23 and 3.25) are not accompanied by analogous bounds. The proof should either supply per-edge bounds or state and prove a general lemma bounding PR invocations.
[Corollary A.4 and Section 3.9] The reduction to a non-degenerate agent 1 via Corollary A.4 conflicts with the runtime analysis. Lemma A.2 constructs a perturbed valuation v'_1(S) = v1(S) + ε Σ_{g∈S} 2^j, with ε 2^{m+1} < δ, where δ is the minimum gap of v1. If the algorithm is run on v'_1, then the quantity Δ in Section 3.9 must be the minimum gap of v'_1, which can be exponentially small in m, making the bound v1(M)/Δ exponential rather than pseudo-polynomial. If, instead, the algorithm is run on the original possibly degenerate v1, strict potential increases are not guaranteed, so the termination argument fails. The paper does not specify which valuation is actually used by the algorithm or how the pseudo-polynomial bound is preserved under the perturbation.
[Section 4 (Theorem 4.1)] The initialization of the three-agent algorithm is not justified. The text states: 'Using this modified version of the PR algorithm, we compute a partition (X1, X2) such that X1 and X2 are EFX-feasible for some distinct agents i and j, respectively.' However, the PR algorithm is run with a single valuation function v and returns a partition that is EFX-feasible for that same valuation. No argument is given for why one of the two bundles is EFX-feasible for a different agent j. This step is essential for the resulting partition to be in stage B (Definition 4.2), and therefore Theorem 4.1's proof is incomplete as written.

minor comments (4)

[Section 3.7] In the restated conditions of stage B2i, the text says 'We say partition X is in stage B2ii if all the following hold', but this should read 'stage B2i'.
[Section 3.9, Theorem 3.49] The sentence 'Since there are finitely many bundles (in fact, 2^|M|)' is imprecise: a partition contains only four bundles, while 2^|M| is the number of all possible bundles (subsets). The intended meaning is clear but the wording should be corrected.
[Lemma 3.21] The step 'Hence, agent 1 EFX-envies X'_4 relative to bundle X'_1' relies on the minimality of X'_2 and X'_3, which ensures that agent 1 does not EFX-envy those two bundles relative to X'_1. This minimality is used implicitly but never stated; adding a sentence would make the argument clearer.
[Section 2] The notation EF2XBest_i(X) is used in Observation 3.15 and elsewhere, but it is not formally defined in the preliminaries (only EFXBest_i is defined). The authors should add a definition of EF2X-best bundles or state explicitly that it is the natural analogue.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the EF2X existence proof is a self-contained constructive case analysis, and the only self-citation is in related work and is not load-bearing.

full rationale

The paper derives the existence of EF2X allocations for four agents with cancelable valuations from the formal definitions of cancelability, EFX-feasibility, EF2X-feasibility, and the monotone potential φ(X)=v1(X1). The main algorithm transforms partitions through explicit stages (A, B, B1, B2, B2i, B2ii), and each transition is justified by lemmas that manipulate the current partition without assuming the final allocation. External results are used: the Plaut-Roughgarden algorithm's monotonicity (Observation 2.1), the fact that cancelable valuations are MMS-feasible (attributed to Akrami et al., an independent reference not authored by the present paper's authors), and the perturbation argument in Lemma A.2 that makes agent 1's valuation non-degenerate. None of these external results contains the target theorem, and they are not fitted to the desired conclusion. The only self-citation in the paper, Ashuri and Gkatzelis [2024], appears in a related-work sentence about MXS and EFL and plays no role in the proof of Theorem 3.1 or Theorem 4.1. There is no step where a parameter is fitted to a subset of the data and then renamed as a prediction, and no uniqueness theorem from the authors' prior work is imported to force a choice. A separate correctness concern, not a circularity, is that the pseudo-polynomial runtime proof in Section 3.9 relies on positive minimum gaps δ and Δ between distinct bundle values, while valuations are defined as real-valued in Section 2; this affects the stated computational guarantee for arbitrary real inputs, but it does not make the existence argument circular or reduce the theorem to its assumptions by construction.

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

The existence proof rests on standard background theorems and on the structural properties of cancelable and MMS-feasible valuations. No free parameters are fitted to data, and no new entities are postulated. The only unstated input assumption is the positive minimum valuation gap needed for the pseudo-polynomial runtime statement.

assumptions (4)

domain assumption Every cancelable valuation is MMS-feasible.
Invoked in Lemmas 3.23, 3.25, 3.44, and 3.47 via Lemma 2 of Akrami et al. [2023], where the PR algorithm's output ordering requires the MMS-feasibility property.
domain assumption The Plaut-Roughgarden local search (PR algorithm) has the monotone minimum-value property stated in Observation 2.1.
Used in Lemmas 3.19 and 3.23 to guarantee potential increases; the proof cites prior work rather than re-proving termination and min-value monotonicity.
standard math Hall's marriage theorem.
Used in Lemma 3.38 to conclude that a perfect EF2X matching exists once the neighborhood condition is established for the bipartite agent-bundle graph.
domain assumption Valuations admit a positive minimum gap between unequal bundle values.
Section 3.9 defines δ and Δ to bound the number of potential increases; the paper never states an integrality or rationality assumption on the real-valued valuations, so this gap is implicitly assumed for the pseudopolynomial-time claim.

how reviews work

0 comments

Cite this review

Pith. "Pith review of EF2X Exists For Four Agents." pith.science (2026). https://pith.science/paper/75IUD3BX

@misc{pith2026241200254,
  author       = {Pith},
  title        = {Pith review of: EF2X Exists For Four Agents},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/75IUD3BX}},
  note         = {Machine review of arXiv:2412.00254}
}

read the original abstract

We study the fair allocation of indivisible goods among a group of agents, aiming to limit the envy between any two agents. The central open problem in this literature, which has proven to be extremely challenging, is regarding the existence of an EFX allocation, i.e., an allocation such that any envy from some agent i toward another agent j would vanish if we were to remove any single good from the bundle allocated to j. When the agents' valuations are additive, which has been the main focus of prior works, Chaudhury et al. [2024] showed that an EFX allocation is guaranteed to exist for all instances involving up to three agents. Subsequently, Berger et al. [2022] extended this guarantee to nice-cancelable valuations and Akrami et al. [2023] to MMS-feasible valuations. However, the existence of EFX allocations for instances involving four agents remains open, even for additive valuations. We contribute to this literature by focusing on EF2X, a relaxation of EFX which requires that any envy toward some agent vanishes if any two of the goods allocated to that agent were to be removed. Our main result shows that EF2X allocations are guaranteed to exist for any instance with four agents, even for the class of cancelable valuations, which is more general than additive. Our proof is constructive, proposing an algorithm that computes such an allocation in pseudopolynomial time. Furthermore, for instances involving three agents we provide an algorithm that computes an EF2X allocation in polynomial time, in contrast to EFX, for which the fastest known algorithm for three agents is only pseudopolynomial.

Figures

Figures reproduced from arXiv: 2412.00254 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 13 canonical work pages

[1]

An EF2X alloc ation protocol for restricted additive valuations

Hannaneh Akrami, Rojin Rezvan, and Masoud Seddighin. An EF2X alloc ation protocol for restricted additive valuations. In Proceedings of the Thirty-First International Joint Confe rence on Artiﬁ- cial Intelligence, IJCAI 2022 , pages 17–23. ijcai.org,

work page 2022
[5]

Simultaneously Satisfying MXS and EFL

doi: 10.48550/ARXIV.2412.00358. URL https://doi.org/10.48550/arXiv.2412.00358. Siddharth Barman, Arpita Biswas, Sanath Kumar Krishna Murthy, a nd Yadati Narahari. Groupwise max- imin fair allocation of indivisible goods. pages 917–924. AAAI Press, 20

work page Pith review arXiv doi:10.48550/arxiv.2412.00358
[7]

URL https://doi.org/10.1016/j.tcs.2024.114596

doi: 10.1016/J.TCS.2024.114596. URL https://doi.org/10.1016/j.tcs.2024.114596. Benjamin Aram Berendsohn, Simona Boyadzhiyska, and L´ aszl´ o Kozma. Fixed-point cycles and approximate EFX allocations. In 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, volume 241 of LIPIcs, pages 17:1–17:13. Schloss Dagstuhl - Leibni...

work page arXiv 2024
[8]

Almost full E FX exists for four agents

Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. Almost full E FX exists for four agents. In Thirty- Sixth AAAI Conference on Artiﬁcial Intelligence, AAAI 2022 , Thirty-Fourth Conference on Innovative Applications of Artiﬁcial Intelligence, IAAI 2022, The Twe lveth Symposium on Educational Advances in Artiﬁcial Intelligence, EAAI 2022 Virtual Event, ...

work page 2022
[12]

Fair allocation in graphs

George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgo uritsa. Fair allocation in graphs. In Proceedings of the 24th ACM Conference on Economics and Comp utation, EC 2023, London, United Kingdom, July 9-12, 2023 , pages 473–488. ACM,

work page 2023
[13]

On the pursuit of EFX for chores: Non-existence and approximations

Vasilis Christoforidis and Christodoulos Santorinaios. On the pursuit of EFX for chores: Non-existence and approximations. In Proceedings of the Thirty-Third International Joint Confe rence on Artiﬁcial In- telligence, IJCAI 2024, Jeju, South Korea, August 3-9, 2024 , pages 2713–2721. ijcai.org,

work page 2024
[14]

Alireza Farhadi, Mohammad Taghi Hajiaghayi, Mohamad Latiﬁan, Mas oud Seddighin, and Hadi Yami

URL https://www.ijcai.org/proceedings/2024/300. Alireza Farhadi, Mohammad Taghi Hajiaghayi, Mohamad Latiﬁan, Mas oud Seddighin, and Hadi Yami. Almost envy-freeness, envy-rank, and Nash social welfare matc hings. In Thirty-Fifth AAAI Conference on Artiﬁcial Intelligence, AAAI 2021 , pages 5355–5362. AAAI Press,

work page 2024
[16]

Fair allocation of a multiset of indivisible items

Pranay Gorantla, Kunal Marwaha, and Santhoshini Velusamy. Fair allocation of a multiset of indivisible items. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, Januar y 22-25, 2023 , pages 304–331. SIAM,

work page 2023

Show all 23 references

[17]

URL https://doi.org/10.1137/1.9781611977554.ch13

doi: 10.1137/1.9781611977554.CH13. URL https://doi.org/10.1137/1.9781611977554.ch13. Daniel Halpern, Ariel D. Procaccia, Alexandros Psomas, and Nisarg Shah. Fair division with binary valua- tions: One rule to rule them all. In Web and Internet Economics - 16th International Co...

doi
[18]

Param eterized guarantees for almost envy-free allocations

Siddharth Barman, Debajyoti Kar, and Shraddha Pathak. Param eterized guarantees for almost envy-free allocations. In Proceedings of the 23rd International Conference on Autono mous Agents and Multiagent Systems, AAMAS 2024, Auckland, New Zealand, May 6-10, 2024 , pages 151–159...

2024
[19]

doi: 10.1609/AAAI.V35I6.1

doi
[21]

doi: 10.5555/3545946. 3598632. URL https://dl.acm.org/doi/10.5555/3545946.3598632. Vishwa Prakash HV, Pratik Ghosal, Prajakta Nimbhorkar, and Nithin Varma. EFX exists for three types of agents. CoRR, abs/2410.13580,
[22]

URL https://doi.org/10.48550/arXiv.2410.13580

doi: 10.48550/ARXIV.2410.13580. URL https://doi.org/10.48550/arXiv.2410.13580. Shayan Chashm Jahan, Masoud Seddighin, Seyed Mohammad Seyed J avadi, and Mohammad Shariﬁ. Rain- bow cycle number and EFX allocations: (almost) closing the gap. In Proceedings of the Thirty-Second In...

doi arXiv
[23]

Richard J

URL https://arxiv.org/abs/2407.05139. Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Sa beri. On approximately fair alloca- tions of indivisible goods. In Proceedings 5th ACM Conference on Electronic Commerce (EC- 2004), pages 125–131. ACM,

2004 arXiv
[24]

Improved EFX approximation guarantees under ordinal- based assumptions

Evangelos Markakis and Christodoulos Santorinaios. Improved EFX approximation guarantees under ordinal- based assumptions. In Proceedings of the 2023 International Conference on Autono mous Agents and Multiagent Systems , pages 591–599. ACM,

2023
[2010]

Envy-freeness up to any item with high Nash welfare: The virtue of donating items

Ioannis Caragiannis, Nick Gravin, and Xin Huang. Envy-freeness up to any item with high Nash welfare: The virtue of donating items. In Anna R. Karlin, Nicole Immorlica, and Rame sh Johari, editors, Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2 019, ...

2019
[2019]

Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alk mini Sgouritsa

URL http://arxiv.org/abs/1905.09969. Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alk mini Sgouritsa. A little charity guarantees almost envy-freeness. SIAM J. Comput. , 50(4):1336–1358,

1905 arXiv
[2020]

Fair and eﬃc ient allocations under lex- icographic preferences

Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Fair and eﬃc ient allocations under lex- icographic preferences. In Thirty-Fifth AAAI Conference on Artiﬁcial Intelligence, A AAI 2021, Thirty-Third Conference on Innovative Applications of Art iﬁcial Intelligence, IAAI...

2021
[2021]

On optimal trad eoﬀs between EFX and Nash welfare

34 Michal Feldman, Simon Mauras, and Tomasz Ponitka. On optimal trad eoﬀs between EFX and Nash welfare. In Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence, AAAI 2024 , pages 9688–9695. AAAI Press,

2024
[2022]

URL https://doi.org/10.24963/ijcai.2022/3

doi: 10.24963/IJCAI.2022/3. URL https://doi.org/10.24963/ijcai.2022/3. Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg , Kurt Mehlhorn, and Ruta Mehta. EFX: A simpler approach and an (almost) optimal guarantee via rainb ow cycle number. In Proceedings of the 24th...

2022 doi
[2023]

Pus hing the frontier on approximate EFX allocations

Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. Pus hing the frontier on approximate EFX allocations. CoRR, abs/2406.12413,

arXiv
[2024]

Simultaneously satisfying MXS and EFL

Arash Ashuri and Vasilis Gkatzelis. Simultaneously satisfying MXS and EFL. CoRR, abs/2412.00358,

arXiv
[6689]

Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia

URL https://doi.org/10.1609/aaai.v35i6.16689. Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Fairly dividing mixtures of goods and chores under lexicographic preferences. In Noa Agmon, Bo An, Alessandro Ricci, and William Yeoh, editors, Proceedings of the 2023 Inter...

doi

Pith tools

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

[1] [1]

An EF2X alloc ation protocol for restricted additive valuations

Hannaneh Akrami, Rojin Rezvan, and Masoud Seddighin. An EF2X alloc ation protocol for restricted additive valuations. In Proceedings of the Thirty-First International Joint Confe rence on Artiﬁ- cial Intelligence, IJCAI 2022 , pages 17–23. ijcai.org,

work page 2022

[2] [5]

Simultaneously Satisfying MXS and EFL

doi: 10.48550/ARXIV.2412.00358. URL https://doi.org/10.48550/arXiv.2412.00358. Siddharth Barman, Arpita Biswas, Sanath Kumar Krishna Murthy, a nd Yadati Narahari. Groupwise max- imin fair allocation of indivisible goods. pages 917–924. AAAI Press, 20

work page Pith review arXiv doi:10.48550/arxiv.2412.00358

[3] [7]

URL https://doi.org/10.1016/j.tcs.2024.114596

doi: 10.1016/J.TCS.2024.114596. URL https://doi.org/10.1016/j.tcs.2024.114596. Benjamin Aram Berendsohn, Simona Boyadzhiyska, and L´ aszl´ o Kozma. Fixed-point cycles and approximate EFX allocations. In 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, volume 241 of LIPIcs, pages 17:1–17:13. Schloss Dagstuhl - Leibni...

work page arXiv 2024

[4] [8]

Almost full E FX exists for four agents

Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. Almost full E FX exists for four agents. In Thirty- Sixth AAAI Conference on Artiﬁcial Intelligence, AAAI 2022 , Thirty-Fourth Conference on Innovative Applications of Artiﬁcial Intelligence, IAAI 2022, The Twe lveth Symposium on Educational Advances in Artiﬁcial Intelligence, EAAI 2022 Virtual Event, ...

work page 2022

[5] [12]

Fair allocation in graphs

George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgo uritsa. Fair allocation in graphs. In Proceedings of the 24th ACM Conference on Economics and Comp utation, EC 2023, London, United Kingdom, July 9-12, 2023 , pages 473–488. ACM,

work page 2023

[6] [13]

On the pursuit of EFX for chores: Non-existence and approximations

Vasilis Christoforidis and Christodoulos Santorinaios. On the pursuit of EFX for chores: Non-existence and approximations. In Proceedings of the Thirty-Third International Joint Confe rence on Artiﬁcial In- telligence, IJCAI 2024, Jeju, South Korea, August 3-9, 2024 , pages 2713–2721. ijcai.org,

work page 2024

[7] [14]

Alireza Farhadi, Mohammad Taghi Hajiaghayi, Mohamad Latiﬁan, Mas oud Seddighin, and Hadi Yami

URL https://www.ijcai.org/proceedings/2024/300. Alireza Farhadi, Mohammad Taghi Hajiaghayi, Mohamad Latiﬁan, Mas oud Seddighin, and Hadi Yami. Almost envy-freeness, envy-rank, and Nash social welfare matc hings. In Thirty-Fifth AAAI Conference on Artiﬁcial Intelligence, AAAI 2021 , pages 5355–5362. AAAI Press,

work page 2024

[8] [16]

Fair allocation of a multiset of indivisible items

Pranay Gorantla, Kunal Marwaha, and Santhoshini Velusamy. Fair allocation of a multiset of indivisible items. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, Januar y 22-25, 2023 , pages 304–331. SIAM,

work page 2023