pith. sign in

arxiv: 2605.21448 · v1 · pith:OCHUVYM7new · submitted 2026-05-20 · 💻 cs.GT

A Note on EFX Inapproximability for Chores

Vasilis Christoforidis This is my paper

Pith reviewed 2026-05-21 02:21 UTC · model grok-4.3

classification 💻 cs.GT
keywords EFXchoresinapproximabilitysubadditive costsfair divisionmonotone functionssubmodular costs
0
0 comments X

The pith

A three-agent six-chore instance with subadditive costs admits no allocation that is α-EFX for any α below about 1.26.

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

The paper constructs an explicit three-agent six-chore example with monotone subadditive cost functions to show that EFX allocations for chores cannot be approximated within any factor smaller than 2 to the power of one-third. This builds on known non-existence results by turning them into a concrete constant-factor lower bound on approximability. A sympathetic reader cares because EFX is a standard fairness target when dividing unwanted items, and the result shows that even simple cost functions block close-to-fair solutions. The work also supplies a weighted-coverage version that yields a 20/19 gap under the stricter submodular class.

Core claim

We present a three-agent, six-chore instance with monotone subadditive cost functions for which no α-EFX allocation exists whenever 1 ≤ α < 2^{1/3} ≈ 1.26. The instance is obtained by refining an earlier counterexample and applying a method that realizes the required ordinal preferences. We further realize the same preferences with weighted-coverage functions to obtain an inapproximability threshold of 20/19 under submodular costs.

What carries the argument

A refined three-agent six-chore instance whose monotone subadditive cost functions induce ordinal preferences that force any allocation to violate α-EFX below the 2^{1/3} threshold.

If this is right

  • No allocation can guarantee α-EFX for α below 2^{1/3} in the worst case when costs are monotone and subadditive.
  • The known 2-approximation for EFX chores leaves a narrowed gap down to approximately 1.26.
  • Even when costs are restricted to submodular functions, a constant inapproximability gap of 20/19 persists via weighted-coverage realizations.
  • Exact EFX allocations remain impossible for subadditive cost functions in at least some chore instances.

Where Pith is reading between the lines

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

  • Designers of allocation algorithms for chores may target approximation factors just above 1.26 or switch to alternative fairness measures such as maximin share.
  • The same preference profile might be used to derive hardness results for other complement-free cost classes or for instances with additional agents.
  • Checking whether the gap closes under further restrictions on the cost functions would be a direct next step.

Load-bearing premise

The cost functions remain monotone and subadditive while exactly producing the ordinal preferences that make every allocation violate the stated α-EFX condition.

What would settle it

An explicit allocation in the six-chore instance in which every agent values its own bundle at least α times any other bundle after removal of one chore, for some α strictly less than 2^{1/3}.

read the original abstract

We study the approximability of EFX allocations for indivisible chores under complement-free cost functions. The non-existence of exact EFX allocations for general monotone functions for chores is known from \cite{CS24}, and a result of \cite{akrami2026} transfers such comparison-based non-existence results to monotone submodular, and hence subadditive, functions. We strengthen this picture by giving explicit constant-factor inapproximability results for submodular and subadditive functions. Our main construction is a three-agent, six-chore instance with monotone subadditive cost functions for which no $\alpha$-EFX allocation exists for any $1\le \alpha<2^{1/3}\approx 1.26$, thus narrowing the gap with the known upper bound of $2$. The construction is obtained by refining the original counterexample of \cite{CS24} and using the approach of \cite{mackenzie2026}. We also give a weighted-coverage realization of the ordinal profile, yielding an instance in which no $\alpha$-EFX allocation exists for any $1\le \alpha<20/19$ under submodular costs. Thus, even within well-studied complement-free classes, EFX for chores admits nontrivial constant lower bounds on approximability.

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

1 major / 2 minor

Summary. The paper studies approximability of EFX allocations for indivisible chores under complement-free (monotone subadditive and submodular) cost functions. Building on the non-existence result of CS24 and its transfer to submodular functions, it gives two explicit constructions: a 3-agent 6-chore instance with monotone subadditive costs showing no α-EFX allocation exists for any 1 ≤ α < 2^{1/3} ≈ 1.26, obtained by refining the CS24 counterexample via the Mackenzie-style weighting approach; and a weighted-coverage realization of the same ordinal profile yielding no α-EFX for 1 ≤ α < 20/19 under submodular costs.

Significance. If the constructions are correct, the results supply the first explicit constant-factor inapproximability bounds for EFX with chores inside the well-studied complement-free classes, narrowing the gap to the known 2-approximation upper bound. The explicit finite instance, direct verification of monotonicity and subadditivity, and weighted-coverage realization for the submodular case are concrete strengths that make the lower bounds falsifiable and useful for future work.

major comments (1)
  1. [main construction section] Main construction (refinement of CS24 instance): the manuscript must explicitly verify that the assigned cost values remain subadditive after any necessary closure and that all critical ordinal comparisons (e.g., c_i({a,b}) vs. c_i({c,d,e}) and similar 2-chore vs. 3-chore bundles) used to rule out α-EFX allocations for α < 2^{1/3} are preserved. Subadditivity can relax some inequalities; without a table or lemma confirming the comparisons survive, the claimed gap is not yet load-bearing.
minor comments (2)
  1. [abstract] The abstract and introduction should more explicitly separate the two constructions and state their respective approximation thresholds (2^{1/3} vs. 20/19) in a single sentence for clarity.
  2. Add a short table listing the six chores, the three agents' cost values on all relevant bundles, and the resulting strict preferences to make the non-existence argument easier to follow.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment of the explicit constructions, and recommendation for minor revision. We address the major comment below.

read point-by-point responses

  1. Referee: [main construction section] Main construction (refinement of CS24 instance): the manuscript must explicitly verify that the assigned cost values remain subadditive after any necessary closure and that all critical ordinal comparisons (e.g., c_i({a,b}) vs. c_i({c,d,e}) and similar 2-chore vs. 3-chore bundles) used to rule out α-EFX allocations for α < 2^{1/3} are preserved. Subadditivity can relax some inequalities; without a table or lemma confirming the comparisons survive, the claimed gap is not yet load-bearing.

    Authors: We agree that explicit verification strengthens the argument. The construction refines the CS24 instance via the Mackenzie-style weighting approach, with costs assigned directly to ensure monotonicity and subadditivity without an intermediate closure step that would alter values. Nevertheless, to confirm that all critical ordinal comparisons (including 2-chore vs. 3-chore bundles) survive under subadditivity and support the 2^{1/3} gap, we will add a new lemma in the revised manuscript that enumerates and verifies each inequality used in the non-existence proof. We will also include a supplementary table of key bundle costs for the three agents to make the checks transparent and falsifiable. revision: yes

Circularity Check

0 steps flagged

Explicit finite-instance construction with verifiable cost functions

full rationale

The paper's central result is a direct, explicit construction of a three-agent six-chore instance together with concrete monotone subadditive cost functions. The non-existence claim for α-EFX below 2^{1/3} is verified by enumerating allocations against these fixed values rather than by any self-referential equation, fitted parameter, or load-bearing self-citation chain. Prior citations to CS24 and akrami2026 supply background context for exact-EFX non-existence and transfer lemmas but are not required for the new constant-factor gap; the weighted-coverage realization is likewise given explicitly. No step reduces the claimed lower bound to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard definitions of monotonicity, subadditivity, and EFX; no free parameters are fitted, no new entities are postulated, and the axioms are the usual background assumptions of fair-division theory.

axioms (2)
  • domain assumption Cost functions are monotone and subadditive (or submodular).
    Invoked throughout the abstract when stating the function classes for which the inapproximability holds.
  • standard math EFX is defined via the standard envy-free-up-to-one-chore condition for chores.
    Used as the target fairness notion whose approximability is studied.

pith-pipeline@v0.9.0 · 5757 in / 1442 out tokens · 35265 ms · 2026-05-21T02:21:11.140174+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

28 extracted references · 28 canonical work pages

  1. [1]

    Vasilis Christoforidis and Christodoulos Santorinaios , title =

    work page

  2. [2]

    2026 , eprint=

    A Counterexample to EFX n 3 Agents, m n + 5 Items, Submodular Valuations via SAT-Solving , author=. 2026 , eprint=

    work page 2026

  3. [3]

    2026 , eprint=

    Counterexamples to EFX for Submodular and Subadditive Valuations , author=. 2026 , eprint=

    work page 2026

  4. [4]

    2024 , eprint=

    Approximate EFX and Exact tEFX Allocations for Indivisible Chores: Improved Algorithms , author=. 2024 , eprint=

    work page 2024

  5. [5]

    The Unreasonable Fairness of Maximum Nash Welfare , journal =

    Ioannis Caragiannis and David Kurokawa and Herv. The Unreasonable Fairness of Maximum Nash Welfare , journal =

    work page

  6. [6]

    Bhaskar Ray Chaudhury and Jugal Garg and Kurt Mehlhorn , title =. J

    work page

  7. [7]

    George Christodoulou and Amos Fiat and Elias Koutsoupias and Alkmini Sgouritsa , title =

    work page

  8. [8]

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

    work page

  9. [9]

    Benjamin Plaut and Tim Roughgarden , title =

    work page

  10. [10]

    George Christodoulou and Vasilis Christoforidis , title =. Inf. Process. Lett. , volume =

    work page

  11. [11]

    Jugal Garg and Aniket Murhekar and John Qin , title =

    work page

  12. [12]

    Jugal Garg and Aniket Murhekar , title =

    work page

  13. [13]

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

    work page

  14. [14]

    Hannaneh Akrami and Noga Alon and Bhaskar Ray Chaudhury and Jugal Garg and Kurt Mehlhorn and Ruta Mehta , title =. Oper. Res. , volume =

    work page

  15. [15]

    Georgios Amanatidis and Evangelos Markakis and Apostolos Ntokos , title =. Theor. Comput. Sci. , volume =

    work page

  16. [16]

    Maximum Nash welfare and other stories about

    Georgios Amanatidis and Georgios Birmpas and Aris Filos. Maximum Nash welfare and other stories about. Theor. Comput. Sci. , volume =

    work page

  17. [17]

    Pushing the Frontier on Approximate

    Georgios Amanatidis and Aris Filos. Pushing the Frontier on Approximate

    work page

  18. [18]

    Moshe Babaioff and Tomer Ezra and Uriel Feige , title =

    work page

  19. [19]

    Evangelos Markakis and Christodoulos Santorinaios , title =

    work page

  20. [20]

    Fair division of indivisible goods: Recent progress and open questions , journal =

    Georgios Amanatidis and Haris Aziz and Georgios Birmpas and Aris Filos. Fair division of indivisible goods: Recent progress and open questions , journal =

    work page

  21. [21]

    Vishwa Prakash HV and Pratik Ghosal and Prajakta Nimbhorkar and Nithin Varma , title =

    work page

  22. [22]

    Ryoga Mahara , title =. Discret. Appl. Math. , volume =

    work page

  23. [23]

    Unified Fair Allocation of Goods and Chores via Copies , journal =

    Yotam Gafni and Xin Huang and Ron Lavi and Inbal Talgam. Unified Fair Allocation of Goods and Chores via Copies , journal =

    work page

  24. [24]

    Shengwei Zhou and Xiaowei Wu , title =. Artif. Intell. , volume =

    work page

  25. [25]

    Bo Li and Yingkai Li and Xiaowei Wu , title =

    work page

  26. [26]

    Haris Aziz and Jeremy Lindsay and Angus Ritossa and Mashbat Suzuki , title =

    work page

  27. [27]

    Yusuke Kobayashi and Ryoga Mahara and Souta Sakamoto , title =. Theor. Comput. Sci. , volume =

    work page

  28. [28]

    Narayan and Paritosh Verma , title =

    Siddharth Barman and Vishnu V. Narayan and Paritosh Verma , title =

    work page