Approximately EFX and fPO Allocations for Bivalued Chores

There is a defensible mirror, but it is an extension rather than a literal fixed-\(M\) limit. The strongest anchor is Theorem 3.14, proved in this paper.

The natural regime is a large workforce assigning recurring indivisible chores: municipal maintenance, hospital cleaning, or a comparable operation. There are many workers but relatively few complete cost types. A type \(t\) is a complete cost vector over a finite set of chore kinds \(Q\), with \(s_t(e)\in\{1,k\}\). The population is \(\mu=(\mu_t)_{t\in\mathcal T}\), where \(\mu_t\) is the fraction of workers of type \(t\). Workers with the same skill, physical-capacity, and task-cost profile are genuinely interchangeable.

Resource scaling must accompany population scaling. Let \(q_e\in[0,1]\) be the number of copies of chore kind \(e\) per unit population. In a finite \(N\)-worker clone, there are \(N\mu_t\) workers of type \(t\) and \(Nq_e\) indivisible copies of \(e\). Thus the continuous model is not giving an individual a fractional chore: a mass of workers receives whole chore bundles. Clearing denominators recovers ordinary finite instances with repeated chore copies.

My lead problem is Continuous Bivalued Approximate-EFX-fPO. An instance consists of \(Q\), \(\mathcal T\), \(k>1\), rational \(\mu_t\), and rational \(q_e\). Let \(B\subseteq Q\) be an integral bundle and \(c_t(B)=\sum_{e\in B}s_t(e)\). The allocation variable is \(\lambda_{t,B}\ge 0\), the mass of type-\(t\) workers receiving the whole bundle \(B\), subject to

\[ \sum_B\lambda_{t,B}=\mu_t \]

for every type \(t\), and

\[ \sum_{t,B:e\in B}\lambda_{t,B}=q_e \]

for every chore kind \(e\).

The allocation is \(\beta\)-EFX if, whenever \(\lambda_{t,B}>0\) and \(\lambda_{u,D}>0\),

\[ c_t(B\setminus\{e\})\le \beta\,c_t(D) \]

for every \(e\in B\). This is the paper’s individual EFX condition applied support-wise to the continuum population.

For fPO, retain the paper’s fractional benchmark: no alternative fractional assignment of the chore supply may weakly reduce every worker’s cost and strictly reduce the cost of a positive-mass set of workers. A convenient certificate is a payment vector \(p_e>0\) such that every chore received by type \(t\) minimizes \(s_t(e)/p_e\) for that type. This is the continuum version of the Fisher-equilibrium certificate used throughout the paper.

The computational task is to minimize \(\beta\), or decide whether a feasible allocation exists with \(\beta\le 2-\frac1k\), together with an fPO certificate. The expected classification is Class A. Theorem 3.14 proves that every finite \(\{1,k\}\)-instance admits a polynomial-time \((2-\frac1k)\)-EFX and fPO allocation. Its proof is especially suitable for continuization: the pEF1 equilibrium, payment levels, MPB conditions, and the low/high-group reallocation argument depend on cost and payment classes rather than on the names of individual workers. In the mass model, those reallocations become transfers between positive masses of type-bundle configurations. The remaining research problem is to perform them in time polynomial in \(|Q|\), \(\tau\), and the encoding length of \(\mu\) and \(q\), rather than in the denominator-cleared population size.

The second, stronger special case is Continuous Bivalued Exact-EFX-fPO\(_2\). It is the same precisely defined problem with \(k=2\), but the target is \(\beta=1\): find \(\lambda\) and an fPO certificate satisfying

\[ c_t(B\setminus\{e\})\le c_t(D) \]

for every pair of bundles in the support and every \(e\in B\). This mirrors Theorem 4.1, stated by the authors here and proved in the deferred full version rather than fully detailed in the proceedings text. The expected classification is again Class A. The paper’s \(k=2\) analysis compresses earnings into three levels \(z,z+1,z+2\), and its reallocation argument involves only finitely many mass classes. That makes a type-mass implementation particularly plausible.

The authors should recognize these as their problems: the costs remain additive and bivalued, chores remain indivisible for each worker, EFX still means “up to any item,” and fPO retains exactly their fractional efficiency benchmark. The paper’s own Fisher-market methodology also naturally invites a high-multiplicity formulation.

The weakest point is substantial. With a fixed finite set of unique chores and a continuum of workers, almost everyone receives nothing, so EFX becomes largely vacuous. The per-capita chore supply \(q\) is therefore essential, but it means this is an extension with joint population/resource scaling, not a direct replacement of \(n\) by a continuum. A second unresolved issue is that \(\lambda\)-support EFX is not an ordinary linear constraint, and strict Pareto improvement must mean improvement on positive mass. If those changes are judged to alter the problem too much, the mirror fails. If high-multiplicity repeated chores are accepted as the relevant instance regime, however, Theorems 3.14 and 4.1 give a credible Class-A continuous allocation programme, with open questions about compressed equilibrium computation, configuration separation, exact tie handling, and whether the support constraints themselves ever create a continuum-specific hardness barrier.