| paper | On the Pursuit of EFX for Chores: Non-existence and Approximations |
| authors | Vasilis Christoforidis, Christodoulos Santorinaios |
| venue | IJCAI 2024 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given a finite chore-category set \(M\), rational additive costs \(c_t(S)=\sum_{e\in S}w_{t,e}\) for \(t\in\{1,2,3\}\), population masses \(\mu_t=1/3\), and per-capita chore supplies \(\rho_e=1/3\), find nonnegative masses \(x_{t,S}\) over whole bundles \(S\subseteq M\) satisfying \(\sum_{S\subseteq M}x_{t,S}=1/3\) and \(\sum_{t=1}^3\sum_{S\ni e}x_{t,S}=1/3\), such that whenever \(x_{t,S}>0\), \(x_{u,R}>0\), and \(e\in S\), \(c_t(S\setminus\{e\})\le2c_t(R)\).
Three additive cost types \(t\in\{1,2,3\}\) with masses \(\mu_t=1/3\), repeated indivisible chore copies with normalized supplies \(\rho_e=1/3\), configuration masses \(x_{t,S}\), and the objective of computing a support allocation satisfying \(2\)-EFX.
The opponent's strongest point is that scaling chore supply and restricting configurations to at most one copy of each category per household is not the literal fixed-item clone limit, so the mirror requires an explicit repeated-chore regime.
fatal: False
The mirror covers Theorem 5's polynomial-time \(2\)-EFX result for three additive agents. It leaves Theorem 1's non-existence and inapproximability, Theorem 2's NP-completeness, Theorem 3's few-chores existence theorem, Theorem 4's general approximation framework, and Corollary 1 without a transferred result.
The strongest honest mirror is a high-multiplicity version of the paper’s additive three-agent result, Theorem 5. It is proved in this paper and states that a \(2\)-EFX allocation for three additive agents exists and can be computed in polynomial time.
The natural regime is a large network of standardized households or service teams. There are three complete cost types—say three recurring profiles of disutility over chore categories—and \(K\) households of each type. Chores are repeated task copies: each chore category has \(K\) indistinguishable copies. Thus the population has \(3K\) agents but only \(\tau=3\) types. This is a genuine high-multiplicity regime, not a claim that every fair-division instance has few types.
The continuous problem I would name
\[ \textsc{3-Type-2EFX}_{\infty} \]
is as follows. The input consists of chore categories \(M=\{1,\ldots,m\}\), rational additive costs
\[ c_t(S)=\sum_{e\in S}w_{t,e} \qquad (t\in\{1,2,3\}), \]
and population masses \(\mu_t=1/3\). Each chore category has per-capita supply \(\rho_e=1/3\). A configuration is a whole indivisible bundle \(S\subseteq M\), and \(x_{t,S}\) denotes the mass of type-\(t\) households receiving that bundle. Feasibility requires
\[ \sum_{S\subseteq M}x_{t,S}=\frac13 \]
for every \(t\), and
\[ \sum_{t=1}^3\sum_{S\ni e}x_{t,S}=\frac13 \]
for every chore \(e\). The allocation is \(2\)-EFX if, whenever \(x_{t,S}>0\) and \(x_{u,R}>0\),
\[ c_t(S\setminus\{e\})\le 2c_t(R) \]
for every \(e\in S\). The optimization version minimizes the smallest \(\alpha\) satisfying these inequalities; the decision version asks for a feasible \(x\) with \(\alpha\le2\).
This is not fractional chore allocation. Every supported configuration \(S\) is an indivisible bundle; \(x\) records how much population receives whole bundles. Clearing denominators gives exactly a finite instance with \(K\) agents of each type and \(K\) copies of every chore category. Conversely, every such repeated finite instance yields rational masses. The bridge is therefore genuine high multiplicity.
Theorem 5 solves this continuous problem immediately. Apply its polynomial-time algorithm to the three cost functions and obtain bundles \(X_1,X_2,X_3\). Set
\[ x_{t,X_t}=\frac13 \]
and set all other \(x_{t,S}\) to zero. The supply constraints hold because each chore is assigned to exactly one of the three bundles, and the support-wise EFX inequalities are exactly the inequalities in the original three-agent instance. The running time is polynomial in \(m\) and the cost encoding length, independent of \(K\). I would classify this mirror as Class A.
The authors should recognize this as their problem: the fairness predicate, additive disutilities, indivisible bundles, and approximation factor are unchanged. Only named agents have been replaced by repeated cost types, and chore supply has been scaled with population so that chores do not become zero-mass anomalies. That scaling is necessary: keeping six fixed chores while letting the population grow would make almost every agent empty-handed and turn EFX into a vacuous statement.
The paper’s Theorem 2, proved here, suggests a more ambitious second question: whether exact EFX existence remains difficult for three superadditive cost types under rational population masses and per-capita supplies. I would not claim that its NP-completeness proof transfers automatically. Repetition allows mass to split across many whole-bundle configurations, potentially converting the paper’s three-way partition obstruction into a rational configuration or packing problem. That is precisely a useful follow-up: does the hardness remain Class B because the combinatorics live in chore identities and complementarities, or does the population relaxation create a Class C problem of its own?
My weakest point is that the lead mirror is a structured clone slice: three types, equal masses, and matched chore supply. It demonstrates a faithful and computationally meaningful mirror, but it does not yet continuize the paper’s full arbitrary-agent, arbitrary-supply setting. The broader configuration problem may be substantially harder, and the paper’s other results—especially Theorem 1’s non-existence construction—should not be presented as already transferred.
The negative case is that the proposed mirror is not a population-only continuization of the paper’s problem. In the paper, \(M\) is a finite set of indivisible chores. If we create \(K\) clones of each agent while keeping \(M\) fixed, only finitely many agents receive chores; almost all agents receive \(\varnothing\). In the nonatomic limit, the nonempty allocations have measure zero, so EFX becomes either vacuous or an artefact of exceptional agents. The interesting finite problem has disappeared.
The proponent avoids this by introducing \(K\) copies of every chore and per-capita supplies \(\rho_e=1/3\). But that changes the resource side of the model. The variables \(x_{t,S}\) describe a fractional allocation of chore copies across a population, namely a configuration or outcome-space relaxation. Saying that each supported \(S\) is an indivisible bundle does not remove this: a mass \(x_{t,S}\) of households receives that bundle, so the supply of each chore category is being continuously divided among households. This is precisely the kind of outcome continuity that ChoCo places outside scope.
Nor is the claimed finite equivalence exact. A repeated finite instance with \(K\) copies of a chore can assign several identical copies to one household, whereas \(S\subseteq M\) permits at most one copy of each category per bundle. Allowing multisets would repair that mismatch, but then the configuration space and the EFX predicate change with \(K\), and Theorem 5 no longer lifts immediately.
Under the proponent’s restricted model, Theorem 5 does give a valid certificate: put mass \(1/3\) of each type on one of three bundles. But this is merely the three-agent allocation copied \(K\) times. The population has no role in the construction, and the optimization version they state is not solved: Theorem 5 proves only that the optimum is at most \(2\), not what the minimum achievable factor is. The decision problem with threshold \(2\) is universally yes on this specially matched supply slice, so it is a clone corollary rather than a new continuous computational question.
The same obstruction defeats the proposed Theorem 2 mirror. With the original six-item set, cloning agents again produces a degenerate population. With replicated chores, the reduction’s three-way partition gadget is no longer the same object: a positive mass of each cost type may receive different bundles and different marker chores. To preserve the reduction, one would have to impose that every clone of a type receives the same bundle. That is an extra homogeneity constraint, and it collapses the question back to the original three-agent problem. If clones may split, the resulting configuration problem may well be interesting, but it is a new fair-division problem involving replicated resources, not the high-multiplicity version of the paper’s NP-completeness theorem.
A more ambitious version with arbitrary type masses, multiset bundles, and arbitrary per-capita chore supplies is mathematically definable. It might even produce a worthwhile result. But it combines population continuization with a new resource-scaling and configuration-allocation model, so it cannot serve as evidence that this paper has a worthwhile continuous mirror within ChoCo’s stated scope.
This negative case is therefore not airtight: if ChoCo permits chore supplies to scale with population, the proponent’s Theorem 2 question becomes a legitimate research direction. Under the programme’s stricter population-only reading, however, Theorem 5 is only a replicated finite theorem, while the genuinely nontrivial repair leaves the paper’s model behind.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.