Approximately EFX Allocations for Indivisible Chores

The most credible mirror is a high-multiplicity workforce with recurring, still-indivisible chores. Imagine \(N\) cleaners and \(m\) chore categories. There are \(Nq_e\) copies of category \(e\), where \(q_e\) is a fixed per-capita supply. A type \(t\) is a complete additive cost vector \(c_t=(c_t(e))_{e\in M}\): for example, a cleaner’s physical limitations, training, and burden for every chore category. The society is described by \(\mu_t\), the fraction of cleaners of type \(t\), with \(N\gg\tau\) and \(\tau\) fixed or moderate.

A bundle is an integer vector \(b\in\mathbb Z_{\ge0}^m\), so every individual still receives an integral bundle and every chore copy is assigned whole. A continuous allocation is a finite-support distribution \(x_{t,b}\), where \(x_{t,b}\) is the mass of type-\(t\) cleaners receiving bundle \(b\). It must satisfy \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}b_e x_{t,b}=q_e\) for every chore category \(e\). Write \(c_t(b)=\sum_e b_e c_t(e)\).

The allocation is \(\alpha\)-EFX if, whenever \(x_{t,b}>0\) and \(x_{u,b'}>0\), then for every \(e\) with \(b_e>0\), \(c_t(b-\mathbf 1_e)\le\alpha c_t(b')\). The objective is to minimize \(\alpha\), or to decide whether an allocation exists for a specified \(\alpha\). This is population continuity only: \(x\) is a mass distribution over integral bundles. For rational data, multiplying by a common denominator recovers an ordinary finite instance with \(N\mu_t\) agents and \(Nq_e\) indivisible chore copies.

My lead anchor is Theorem 19, proved in this paper. It gives a polynomial-time \((n-1)\)-EFX allocation for \(n\ge4\) agents with bi-valued cost functions. Its continuous counterpart is:

\(\textsf{Bivalent-Mass-}(\tau-1)\textsf{-EFX}\): given rational \(\mu\), rational chore supplies \(q\), and types satisfying \(c_t(e)\in\{a,b\}\), find a mass allocation \(x\) satisfying the constraints above and \((\tau-1)\)-EFX.

This is not claiming that the paper’s \(n-1\) bound automatically becomes \(\tau-1\). That replacement is precisely the continuization question: can the dependence on the number of named agents be replaced by dependence on the number of distinct complete cost profiles? The bivalued setting is especially plausible. A type is simply the heavy-chore set \(H_t\subseteq M\), and a large workforce may genuinely contain many cleaners with the same heavy/light profile. The paper’s heavy-item classification and its round-robin structure should have type-level analogues.

I would initially expect the stated approximation problem to be Class A for fixed \(\tau\), perhaps through a configuration or flow formulation whose pricing problem exploits the heavy/light structure. The exact version, \(\alpha=1\), is a valuable boundary question: it may be Class C even if the coarse approximation is tractable. Further questions include whether a constant independent of \(\tau\) is possible, and whether the continuous optimum can be rounded to a finite \(N\)-agent allocation with controlled additive error.

The second anchor is Theorem 8, also proved here. It gives a polynomial-time \(3n^2\)-EFX allocation for arbitrary additive costs and any number of agents. Its continuous problem is:

\(\textsf{Additive-Mass-}3\tau^2\textsf{-EFX}\): given rational \(\mu\), rational supplies \(q\), and arbitrary rational additive type costs \(c_t(e)\ge0\), find a mass allocation \(x\) that is \(3\tau^2\)-EFX.

Again, the point is to ask whether the theorem’s dependence on headcount \(n\) can disappear in a high-multiplicity regime and be replaced by dependence on \(\tau\). The proof gives a credible starting point: its large-item sets, common small-item partition, and assignment of exceptional items can all be reformulated over cost types rather than named individuals. The main unresolved issue is whether the resulting configuration problem has an efficient pricing procedure. I would forecast Class A for the coarse type-parameterized approximation if that pricing problem can be controlled; exact mass-EFX is a plausible continuum-specific hardness candidate.

A narrower exact anchor is Theorem 15, proved here: three agents with bi-valued costs admit an EFX allocation in polynomial time. The corresponding question is \(\textsf{Three-Type-Bivalent-Mass-EFX}\): take exactly three positive-mass cost types, arbitrary rational \(\mu\), bi-valued costs, and discrete chore supplies \(q\); does there exist an \(x\) satisfying the above constraints with \(\alpha=1\), and can it be found efficiently? This is a meaningful test of whether the paper’s exact three-agent phenomenon survives when each of the three profiles is represented by a large population. I would regard it as an open boundary between a possible Class A result and continuum-specific hardness, not as a filler anchor.

The paper contains no named NP-hardness, coNP-hardness, or parameterized-hardness theorem, so there is no honest Class B hardness anchor here. The positive case therefore rests on its proved algorithmic structure: large-versus-small chores, heavy/light type profiles, and balanced partitions. The mirror covers the paper’s EFX-computation results, not its unrelated discussion of goods, MMS, or PROPX.

The weakest point is the need for repeated chore copies. If one keeps exactly one copy of each of the paper’s \(m\) chores while letting \(N\) grow, almost every agent receives nothing and EFX becomes degenerate. Allowing chores to be fractionally assigned would instead continuize the outcome, which is outside ChoCo’s scope. The repeated-copy workforce is therefore necessary for a nondegenerate population mirror, but it does change the instance regime. Its defense is that every finite realization remains exactly an indivisible additive-chore allocation problem; it is simply a high-multiplicity regime with many agents and repeated item signatures.