| paper | When is Truthfully Allocating Chores No Harder Than Goods? |
| authors | Bo Li, Biaoshuai Tao, Fang-Xiao Wang, Xiao-Wei Wu, Mingwei Yang, Shengwei Zhou |
| venue | SAGT 2025 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5.1
statement extracted from the paper’s text layer
Given finite chore classes \(O=\{o_1,\ldots,o_m\}\), complete bi-valued cost types \(T\), rational masses \(\mu\in\mathbb{Q}^{T}\), common \(p>q>0\), and rational per-capita supplies \(s_o\in[0,1]\), construct in time \(\operatorname{poly}(m,|T|,L)\) a truthful menu of lotteries \(P_r\) over integral bundles and a feasible joint coupling such that \(z_r(o)=\Pr_{B\sim P_r}[o\in B]\), \(\sum_t\mu_tz_t(o)=s_o\), truthfulness and ex-ante envy-freeness hold, the allocation is ex-ante Pareto optimal, and every realized integral assignment is EF1 almost everywhere.
Types are complete bi-valued cost vectors over chore classes; \(\mu_t\) is agent mass and \(s_o\) is per-capita chore supply. Decision variables are menu lotteries, bundle/type coupling variables, and marginals \(z_r(o)\); the objective is exact feasible construction with truthfulness, ex-ante Pareto optimality and envy-freeness, and support-wise EF1.
The marginal variables \(z_t(o)\) alone cannot certify ex-post EF1, so the mirror needs a joint coupling over integral bundle assignments and type masses whose computational complexity is unresolved.
fatal: False
The mirror covers Theorem 5.1 and its Lemmas 5.2–5.3 construction and rounding machinery; it leaves the two-agent characterizations, efficiency-ratio impossibility, and other goods-to-chores transfers untouched.
The strongest honest positive case is narrow but real: mirror Theorem 5.1 through a high-multiplicity population of agents with repeated chore classes. The paper’s own continuity in Section 4 is only continuity of item allocation, so it is not itself a collision with ChoCo; the proposed mirror makes the population continuous while keeping each individual’s bundle integral.
The lead anchor is Theorem 5.1, proved in this paper. It states that, for indivisible chores with any number of agents whose additive costs are bi-valued—there are common \(p>q>0\) such that every \(c_i(o)\in\{p,q\}\)—there exists a randomized mechanism that is ex-ante truthful, ex-ante Pareto optimal, ex-ante envy-free, and ex-post EF1. The authors additionally state immediately after the theorem that their mechanism can be implemented in polynomial time, although this is not packaged as a separate complexity theorem. The proof uses their Lemma 5.2, together with the rounding machinery of Lemma 5.3.
A natural mirror is Bi-Valued Chore Allocation over a Continuum. There is a finite catalogue \(O=\{o_1,\ldots,o_m\}\) of chore classes and a finite set \(T\) of complete cost types. Each \(t\in T\) has \(c_t(o)\in\{p,q\}\), and the society is a rational distribution \(\mu\in\mathbb{Q}^{T}\). Chore class \(o\) has per-capita supply \(s_o\in\mathbb{Q}\), with \(0\le s_o\le1\). Thus \(\mu_t\) is the mass of agents of type \(t\), while \(s_o\) is the fraction of the population receiving a copy of chore \(o\). The supply scaling is essential: \(K\) copies of each chore class are assigned to \(K\) times as many agents, so the problem does not degenerate into finitely many chores and infinitely many empty agents.
The solution is a truthful menu of lotteries \(P_r\) over integral bundles \(B\subseteq O\), one for each possible report \(r\in T\), together with a mass assignment realizing the truthful lotteries. Writing \(z_r(o)=\Pr_{B\sim P_r}[o\in B]\), feasibility requires \(\sum_t\mu_tz_t(o)=s_o\) for every \(o\). Truthfulness requires, for every true type \(t\) and report \(r\), \(c_t(z_t)\le c_t(z_r)\). Ex-ante EF requires \(c_t(z_t)\le c_t(z_r)\) for every positive-mass type \(r\). Ex-ante PO means that no other feasible type-level allocation weakly lowers every positive-mass type’s expected cost and strictly lowers one. Finally, every realized integral mass assignment must be EF1: for almost every pair of agents \(a,b\), with \(a\) receiving bundle \(A_a\), there is \(o\in A_a\) such that \(c_a(A_a\setminus\{o\})\le c_a(A_b)\).
This is recognisably the same underlying problem as Theorem 5.1. The agents still have additive bi-valued chore costs; chores remain indivisible for each individual; randomization is still used to obtain ex-ante properties; and EF1 is still required on every integral realization. The only change is that repeated identical types and repeated chore classes are represented by masses. A finite instance with \(N\) agents and \(k_o\) copies of class \(o\) maps exactly to \(\mu_t=n_t/N\) and \(s_o=k_o/N\).
The plausible classification is Class A. Probabilistic serial can be run at type masses rather than agent-by-agent, and the rounding step should become a finite transportation or matching problem over the \(\tau\) types. The natural target theorem would be an exact algorithm running in \(\operatorname{poly}(m,\tau,L)\), independent of the enormous population size \(N\), together with a two-way rounding theorem for rational \(\mu\) and \(s\). This is not proved by the paper, but Theorem 5.1 gives a substantive algorithmic starting point rather than merely suggesting a fractional relaxation.
The weakest point is that the paper contains no numbered NP-hardness, tractability, or parameterized-complexity theorem. Strictly speaking, Theorem 5.1 is a mechanism-existence theorem accompanied by an unnumbered polynomial-time claim, not a formal \(P\)-classification. Moreover, in a nonatomic population a single agent cannot change \(\mu\), so strategic truthfulness loses the finite-population externality present in the original model. The menu formulation keeps individual misreporting meaningful, but a referee could regard it as a large-market variant rather than a literal limit. Even so, it is a credible continuous-population analogue of the paper’s strongest algorithmic construction, and it generates a precise ChoCo question rather than merely observing that the paper already allows fractional allocations.
The strongest negative case is the missing computational anchor. Theorem 5.1 is a mechanism-existence and guarantee theorem, not a numbered complexity result. The paper explicitly says that it “skips the discussion on time complexity” and merely observes that the mechanism can be implemented in polynomial time. It gives no input encoding, bit-complexity bound, succinct-output model, or high-multiplicity running-time claim. The other relevant results are structural transfers, characterizations, fairness guarantees, and efficiency-ratio impossibilities. Under ChoCo’s computational-anchor requirement, the proposed problem is therefore a new research direction inspired by the paper, not a continuous mirror of one of its computational results.
The proposed scaling also exposes the gap. With the original finite set of chores, increasing the population makes almost everyone receive the empty bundle, so the fairness requirements degenerate. The proponent correctly repairs this by scaling chore supplies per capita. But then the model contains \(K s_o\) copies of every chore class for \(K\) agents: it is a new repeated-resource fair-division model. Clearing denominators recovers finite instances, but the paper’s informal polynomial implementation is polynomial in the expanded value of \(K\), not necessarily in the binary encoding of the masses. The source proves nothing about the compressed high-multiplicity problem that ChoCo would actually study.
More seriously, the displayed variables \(z_t(o)\) retain only marginal probabilities. They cannot express ex-post EF1. Two lotteries can have identical \(z_t(o)\) for every type and chore while differing in whether their support contains an EF1 allocation. To preserve the theorem, one must retain a joint distribution over integral bundle assignments and require every assignment in its support to satisfy all pairwise EF1 constraints. That introduces a configuration or coupling problem over bundles \(B\subseteq O\), potentially of size \(2^m\), together with correlations between type masses and bundles. If one drops those support constraints and keeps only average costs, one has changed the theorem. If one restores them, the attractive type-level LP is no longer the proposed problem, and the crucial rounding step becomes the entire unresolved question.
Truthfulness also changes meaning in the atomless limit. A single agent has zero mass, so changing their report does not change \(\mu\), the supply constraints, or any allocation computed solely from aggregate reports. Truthfulness is then either vacuous or reduces to selecting from a fixed menu. The proposed inequality
\[
c_t(z_t)\le c_t(z_r)
\]
is effectively the same cross-type comparison used for ex-ante envy-freeness, not the finite-agent strategic externality studied in the paper. Making positive-mass groups strategic would be meaningful, but that is a new notion of group truthfulness, not the theorem’s individual truthfulness.
Section 4 cannot rescue the case: its continuity is in item allocation, which is outside ChoCo’s scope, and its main impossibility result is explicitly for two agents. Replicating agents and items to create a population continuum would again produce the new large-market model above.
So the most defensible negative verdict is: the proposed continuum problem is coherent and may be worthwhile as new high-multiplicity fair-division research, but it is not justified as a computational mirror of this paper. The universal claim that no useful scenario can exist is weaker: once scalable chore supplies and support-wise integral allocations are admitted, the proponent has identified a genuinely plausible extension.
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.