| paper | Existence of 2-EFX Allocations of Chores |
| authors | J. Garg, Aniket Murhekar |
| venue | AAAI 2026 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 6
statement extracted from the paper’s text layer
Given rational \(k\ge1\), finite agent types \(\Theta\) with masses \(\mu_\theta\), finite chore types \(Q\) with rational per-capita supplies \(b_q\), and \(d_{\theta q}\in\{1,k\}\), compute a finite-support distribution \(\pi_{\theta,B}\) over integral bundles \(B\in\mathbb Z_{\ge0}^{Q}\) satisfying \(\sum_B\pi_{\theta,B}=\mu_\theta\), \(\sum_{\theta,B}\pi_{\theta,B}B_q=b_q\), pointwise \((2-1/k)\)-EFX across every supported pair, and \(PO_\infty\), in time polynomial in the compressed input size.
A high-multiplicity configuration model: \(\mu\) is agent mass over complete disutility types, \(b\) is per-capita chore supply, and \(\pi_{\theta,B}\) assigns mass to integral bundle configurations; the objective is to find a pointwise \((2-1/k)\)-EFX and \(PO_\infty\) allocation without unfolding the population.
Exact support-wise EFX is not closed under mixing: type-level averages lose cross-support constraints, while retaining \(\pi_{\theta,B}\) may require exponentially many configurations and no polynomial separation method is supplied.
fatal: False
The mirror covers the bivalued computational guarantee of Theorem 6; it leaves the existence-only Theorem 4, the conditional framework results, the ER-equilibrium-dependent Theorem 5, and the small-instance result Theorem 7 without continuous computational formulations.
The strongest positive case is a high-multiplicity chore-allocation mirror, with Theorem 6 as the lead anchor.
Take a finite set of agent types \(\Theta\) and chore types \(Q\). A type \(\theta\) is a complete disutility vector \(d_{\theta q}\) over chore types. The society is a rational mass distribution \(\mu\) over \(\Theta\), while \(b_q\) is the number of chores of type \(q\) per unit population. Thus an \(N\)-agent realization has \(N\mu_\theta\) agents of type \(\theta\) and \(Nb_q\) copies of chore \(q\).
The population remains continuous only in aggregate. Each individual still receives an integral bundle \(B\in\mathbb Z_{\ge0}^{Q}\). An aggregate allocation is a finite-support distribution \(\pi_{\theta,B}\), where
\[ \sum_B\pi_{\theta,B}=\mu_\theta \qquad\text{and}\qquad \sum_{\theta,B}\pi_{\theta,B}B_q=b_q. \]
Thus \(\pi_{\theta,B}\) is the mass of type-\(\theta\) agents receiving the integral bundle \(B\). The disutility is additive:
\[ d_\theta(B)=\sum_{q\in Q}d_{\theta q}B_q. \]
The continuous EFX condition is pointwise over the support: whenever \(\pi_{\theta,B}>0\), \(\pi_{\theta',B'}>0\), and \(q\in B\),
\[ d_\theta(B-\{q\})\le \lambda d_\theta(B'). \]
This is not fractionalizing chores or replacing EFX by an average inequality. Every unit of agent mass receives an indivisible bundle; only the frequencies of integral bundles are fractional.
For Pareto optimality, one can require that no feasible reassignment admits a measure-preserving coupling in which every agent’s disutility weakly decreases and a positive mass strictly decreases. This is the direct atomless analogue of the paper’s integral PO notion.
The regime is plausible, for example, in a large hospital, municipality, or facilities organization with millions of workers but relatively few recurring worker profiles and chore classes. A worker type might encode physical ability, training, and risk tolerance; a chore type might encode a recurring task. In the bivalued case, every worker-task disutility is either \(1\) or \(k\). The relevant comparison is \(N\) enormous versus \(|\Theta|\) and \(|Q|\) modest. This is precisely a high-multiplicity regime, not a claim that every small household chore instance should be continuized.
The lead anchor is Theorem 6, explicitly attributed to Wu et al. and reproved through the paper’s framework. It states in full:
For every chore-division instance with \(\{1,k\}\)-bivalued disutilities, there exists a \((2-1/k)\)-EFX and PO allocation, and such an allocation can be computed in polynomial time.
The present paper’s route is to compute an MPB allocation that is price-EF1, prove in Lemma 3 that it is weakly \((2-1/k)\)-EFX-friendly, and then apply Theorem 3’s swap framework. The paper also argues that the swaps preserve PO in the bivalued setting.
The corresponding continuous problem is:
Bivalued-\((2-1/k)\)-EFX Population Allocation. Given rational \(\mu\), rational per-capita chore supplies \(b\), a rational \(k\ge1\), and a disutility matrix satisfying \(d_{\theta q}\in\{1,k\}\), output a finite-support aggregate allocation \(\pi\) that is \((2-1/k)\)-EFX and \(PO_\infty\) in the sense above.
The objective is feasibility/search: find one such allocation, with running time measured in \(|\Theta|\), \(|Q|\), and the encoding length of the masses, supplies, and \(k\), rather than in the unfolded number \(N\) of agents.
I would tentatively expect this to be Class A. The paper’s price-EF1/MPB construction and chore-swap procedure are exactly the sort of operations that should admit compression by type and bundle class. In the bivalued case, the relevant disutility and price distinctions are especially limited, suggesting a flow, matching, or configuration-LP formulation. The real proof obligation is to show that the compressed representation has a polynomial-size pricing or separation procedure and that aggregate swaps preserve pointwise EFX and \(PO_\infty\). That is a substantial theorem, but it is recognisably the paper’s problem rather than a softened surrogate.
The second anchor is Theorem 4, proved in this paper. It states:
For every chore-division instance with additive disutilities, a \(2\)-EFX allocation always exists.
The continuous counterpart is:
Additive-\(2\)-EFX Population Allocation. Given arbitrary rational agent-type masses \(\mu\), rational per-capita chore supplies \(b\), and arbitrary positive additive disutilities \(d_{\theta q}\), output a finite-support aggregate allocation \(\pi\) satisfying the pointwise \(2\)-EFX inequalities.
This is also a natural mirror of the authors’ question. The paper’s proof starts from an MPB, price-EF1 allocation, proves in Lemma 2 that it is \(2\)-EFX-friendly, and then invokes the swap framework of Theorem 2. In the continuous version, those ingredients become a mass allocation, a price vector, and transfers of mass between integral bundle configurations.
I would again expect the constructive version to be Class A, at least for a fixed finite type/chore-type universe, but this is less secure than the bivalued anchor. Rational instances can be unfolded to finite instances by clearing denominators, so Theorem 4 immediately implies continuous existence. The genuinely new computational question is whether one can find and represent the witness in time polynomial in the compressed description, without expanding to an exponentially large \(N\). The paper itself says that the required price-EF1/PO starting allocation is not known to be polynomial-time computable, so I would not claim that Theorem 4 already gives a polynomial continuous algorithm.
The high-multiplicity dictionary is exact for rational data: an allocation of \(N\mu_\theta\) agents and \(Nb_q\) chores induces \(\pi\) by normalization, and any rational \(\pi\) can be unfolded into such a finite allocation. This makes the mirror mathematically faithful while still shifting the computational parameter from the number of named agents to the number of distinct types and the encoding length of the masses.
The paper contains no named NP-hardness, coNP-hardness, W[1]-hardness, or other negative computational result of its own. The hardness and polynomial-time statements in the related-work discussion are citations, not anchors. Consequently, this paper cannot support a Class B or Class C claim directly. Its positive opportunity is instead that its bivalued algorithmic theorem and its general \(2\)-EFX existence theorem invite compressed configuration and mass-transport formulations.
The weakest point is the unrestricted additive case. EFX is a support condition over integral bundles, not merely a constraint on type-level averages, and the support may be exponentially large. Moreover, the paper’s initial price-EF1/PO allocation is nonconstructive in general. An opposing analyst could therefore argue that the continuous model only inherits existence by denominator clearing and has no established computational gain. That objection does not defeat the mirror itself, but it means the strongest honest claim is: the bivalued theorem is a credible Class A continuous-computation target; the general \(2\)-EFX theorem gives a broader, currently more conjectural target.
The negative case is ultimately weak, because Theorem 6 survives it. But the strongest objection is that the proposed continuous formulation must choose between ceasing to mirror EFX and ceasing to be a useful continuous-computation problem.
Theorem 4 is not itself a computational result. It asserts existence of a \(2\)-EFX allocation, while the required starting price-EF1/PO allocation is obtained non-constructively; the paper explicitly says that polynomial-time computation of this starting point is open. Theorem 2 is only a conditional algorithm. Thus the proposed “Additive-\(2\)-EFX Population Allocation” is a new high-multiplicity search problem, not the continuization of a computational theorem proved in this paper. Denominator clearing transfers existence, but gives no algorithm polynomial in the compressed encoding.
Theorem 6 is the serious anchor. A naive continuous formulation using only average disutility, such as \(x_{\theta q}\), is not a mirror: EFX depends on the integral bundle received by each individual. Two populations with identical type-level averages can differ completely in whether every agent satisfies EFX.
The proponent’s improved formulation using \(\pi_{\theta,B}\) repairs that defect, but exposes the deeper difficulty. EFX is support-sensitive:
\[ \pi_{\theta,B}>0,\ \pi_{\theta',B'}>0 \quad\Longrightarrow\quad d_\theta(B-\{q\})\le \lambda d_\theta(B') \]
for every \(q\in B\). It is not a constraint on expected bundles. Mixing two individually valid aggregate allocations can introduce cross-support pairs that violate EFX. Consequently, the natural mass variables do not form the sort of linear population model that makes continuization computationally attractive. To preserve the paper’s notion exactly, one must retain a configuration support of integral bundles and enforce pairwise conditions across that support. The paper’s swap algorithm likewise acts on particular bundles and particular high-cost chores, not merely on type masses.
This leaves two alternatives. If one keeps only aggregate or average inequalities, the problem is tractable-looking but is no longer EFX. If one keeps exact support-wise EFX, the “continuous” object is essentially a frequency encoding of an integral allocation, with the difficult combinatorics still residing in the bundle support. Every rational \(\pi\) can indeed be unfolded into a finite instance, but that establishes high-multiplicity faithfulness rather than a genuine continuous relaxation or an evident computational gain.
That objection does not amount to a collision, and it cannot honestly rule out a worthwhile configuration algorithm. In fact, the proposed bivalued model is a sensible high-multiplicity regime: repeated agent and chore types are plausible, and Theorem 6 is a named polynomial-time result whose compressed version is not already solved by denominator clearing. Existing high-multiplicity structure would support, not undermine, the mirror.
So I can defeat Theorem 4 as a computational anchor, and I can show that the obvious continuous EFX formulations are either inexact or support-sensitive. I cannot honestly defeat the best version of the Theorem 6 mirror. The universal claim that no worthwhile continuous mirror exists is therefore not supportable; the strongest negative conclusion is that the bivalued mirror is a credible but technically nontrivial Class A target, while the general \(2\)-EFX mirror is only a speculative new problem.
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.