pith. sign in

arxiv: 2606.08872 · v1 · pith:FQDA5B6Nnew · submitted 2026-06-07 · 💻 cs.GT · econ.TH

EFX for Additive Chores: Nonexistence, Pareto Incompatibility, and Bi-Valued Existence

Wentao He , Biaoshuai Tao This is my paper

Pith reviewed 2026-06-27 17:17 UTC · model grok-4.3

classification 💻 cs.GT econ.TH
keywords EFXfair divisionindivisible choresadditive costsPareto optimalityexistencecounterexamples
0
0 comments X

The pith

For additive chore division, no EFX allocation exists in some instances with four or more agents even when costs take only three values.

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

The paper settles the open question of whether EFX allocations always exist for indivisible chores under additive costs by giving explicit counterexamples. For any number of agents n at least four, it produces a tri-valued instance in which no allocation satisfies the EFX condition. The same instances are used to show that, when costs are restricted to two values, every EFX allocation fails to be Pareto optimal once n reaches four. The constructions are tight in two ways: EFX is already known to exist for two cost types, and EFX plus Pareto optimality are known to be compatible for three or fewer agents. The paper also proves that an EFX allocation is guaranteed to exist when there are exactly four agents and only two cost values.

Core claim

Even for tri-valued additive cost functions, for every n≥4, there exists an instance with n agents where no EFX allocation exists. For bi-valued instances, for every n≥4, there exists an instance with n agents where every EFX allocation is not Pareto-optimal. An EFX allocation is guaranteed to exist for n=4.

What carries the argument

Explicit counterexample instances using only three (respectively two) distinct positive chore costs that force violations of the EFX condition or of Pareto optimality under additive valuations.

Load-bearing premise

The cost of any bundle equals the sum of the costs of the items it contains.

What would settle it

An explicit EFX allocation for one of the paper's n=4 tri-valued counterexample instances.

read the original abstract

We consider the fair division problem of indivisible chores and resolve the long-standing open problem for the existence of EFX allocations with additive cost functions. We show that, even for tri-valued additive cost functions, for every $n\geq 4$, there exists an instance with $n$ agents where no EFX allocation exists. Our counterexample only uses three types of chores, which is also tight on the number of types, as an EFX allocation is known to exist for two types of chores. We then consider bi-valued instances. We show that, for every $n\geq 4$, there exists an instance with $n$ agents where every EFX allocation is not Pareto-optimal. This is also the first example showing the incompatibility of EFX and Pareto-optimality when the costs of items are positive: existing examples showing the incompatibility of EFX and Pareto-optimal exploit items with $0$ costs. Our result shows such an example exists even for bi-valued instances. The number of agents $n$ is also tight: for $n\leq 3$, it is known that EFX is compatible with Pareto-optimality. Finally, we also show that an EFX allocation is guaranteed to exist for $n=4$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper resolves the long-standing open problem on EFX existence for indivisible chores with additive costs. It constructs explicit counterexamples showing that, even for tri-valued additive costs using only three chore types, no EFX allocation exists for any n≥4. It further shows that for bi-valued instances with n≥4 every EFX allocation fails Pareto optimality (first such example with strictly positive costs), while EFX and PO are compatible for n≤3, and proves that an EFX allocation always exists when n=4.

Significance. If the constructions and proofs hold, the results are significant: they settle the existence question for additive chores, establish tightness on the number of distinct cost values (three is tight) and on the agent threshold (n=4), and give the first positive-cost incompatibility between EFX and Pareto optimality. The explicit, minimal-type counterexamples and the small-n existence result are concrete contributions to the fair-division literature.

minor comments (1)
  1. [Abstract] Abstract, final sentence: the claim that 'an EFX allocation is guaranteed to exist for n=4' should explicitly state whether the guarantee is for bi-valued instances (the setting of the preceding paragraph) or holds more generally.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive recommendation to accept and for the accurate summary of our results on EFX existence, Pareto incompatibility, and the tightness results for additive chore instances.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central results consist of explicit counterexample constructions showing non-existence of EFX allocations for tri-valued additive chore costs when n≥4, plus a separate existence proof for bi-valued instances at n=4 and a Pareto-incompatibility example. These are direct combinatorial constructions and proofs that stand on their own without reducing to fitted parameters, self-definitional loops, or load-bearing self-citations. The derivations are self-contained against the additive-cost model and do not invoke any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces no new entities or fitted parameters; it relies on standard definitions from the fair-division literature to construct counterexamples.

axioms (1)
  • standard math Standard mathematical definitions of EFX, Pareto optimality, and additive cost functions
    Invoked as the problem setting throughout the abstract.

pith-pipeline@v0.9.1-grok · 5756 in / 1145 out tokens · 39073 ms · 2026-06-27T17:17:03.933344+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

15 extracted references · 4 canonical work pages · 1 internal anchor

  1. [1]

    Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa

    doi: 10.1016/j.artint.2023.103965. Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. Pushing the frontier on approximate EFX allocations. InProceedings of the 25th ACM Conference on Economics and Computation, pages 1268–1286,

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

  2. [2]

    Fair allocation of two types of chores

    Haris Aziz, Jeremy Lindsay, Angus Ritossa, and Mashbat Suzuki. Fair allocation of two types of chores. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 143–151,

    2023

  3. [3]

    Fair division with indivisible goods, chores, and cake.arXiv preprint arXiv:2511.04891,

    Haris Aziz, Xinhang Lu, Simon Mackenzie, and Mashbat Suzuki. Fair division with indivisible goods, chores, and cake.arXiv preprint arXiv:2511.04891,

    arXiv

  4. [4]

    Fair chore division under binary supermodular costs

    26 Siddharth Barman, Vishnu Narayan, and Paritosh Verma. Fair chore division under binary supermodular costs. InProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 2863–2865,

    2023

  5. [5]

    Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat

    doi: 10.1016/j.artint.2020.103436. Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. Almost full EFX exists for four agents. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4826–4833,

    work page doi:10.1016/j.artint.2020.103436 2020

  6. [6]

    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. InProceedings of the 2019 ACM Conference on Economics and Computation, pages 527–545, 2019a. Ioannis Caragiannis, David Kurokawa, Herv´ e Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of ...

    2019

  7. [7]

    The fairness of leximin in allocation of indivisible chores.arXiv preprint arXiv:2005.04864,

    Xingyu Chen and Zijie Liu. The fairness of leximin in allocation of indivisible chores.arXiv preprint arXiv:2005.04864,

    arXiv 2005

  8. [8]

    New algorithms for the fair and efficient allocation of indivisible chores

    27 Jugal Garg, Aniket Murhekar, and John Qin. New algorithms for the fair and efficient allocation of indivisible chores. In32nd International Joint Conference on Artificial Intelligence, IJCAI 2023, pages 2710–2718. International Joint Conferences on Artificial Intelligence,

    2023

  9. [9]

    Fairly dividing mixtures of goods and chores under lexicographic preferences

    Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Fairly dividing mixtures of goods and chores under lexicographic preferences. InProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, volume 2023, pages 152–160. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS),

    2023

  10. [10]

    Almost (weighted) proportional allocations for indivisible chores

    Bo Li, Yingkai Li, and Xiaowei Wu. Almost (weighted) proportional allocations for indivisible chores. In Proceedings of the ACM Web Conference 2022, pages 122–131,

    2022

  11. [11]

    Allocating chores with restricted additive costs: Achieving EFX, MMS, and efficiency simultaneously

    Zehan Lin, Xiaowei Wu, and Shengwei Zhou. Allocating chores with restricted additive costs: Achieving EFX, MMS, and efficiency simultaneously. InProceedings of the ACM Web Conference 2026, pages 146– 156,

    2026

  12. [12]

    Counterexamples to EFX for Submodular and Subadditive Valuations

    doi: 10.1613/jair.1.15800. Simon Mackenzie and Mashbat Suzuki. Counterexamples to EFX for submodular and subadditive valuations. arXiv preprint arXiv:2605.06451,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1613/jair.1.15800

  13. [13]

    Existence of fair and efficient allocation of indivisible chores

    Ryoga Mahara. Existence of fair and efficient allocation of indivisible chores. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 6742–6766. SIAM,

    2026

  14. [14]

    Connections between fairness criteria and efficiency for allocating indivisible chores

    Ankang Sun, Bo Chen, and Xuan Vinh Doan. Connections between fairness criteria and efficiency for allocating indivisible chores. InProceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021), pages 1281–1289. ACM,

    2021

  15. [15]

    A Proof of Theorem 1 for Generaln In this section, we prove Theorem 1 for an arbitrary fixedn≥4

    doi: 10.24963/ijcai.2024/338. A Proof of Theorem 1 for Generaln In this section, we prove Theorem 1 for an arbitrary fixedn≥4. A.1 The construction Fix an integern≥4. Partition the agents into two groupsT 1 andT 2 such that |T1|= j n 2 k ,|T 2|= l n 2 m . Lett 1 =|T 1|andt 2 =|T 2|. Lets= 2t 2 +

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