| paper | Fair Allocation of Two Types of Chores |
| authors | — |
| venue | AAMAS 2023 |
| 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 4.7
statement extracted from the paper’s text layer
Given finitely many valuation types \(\Theta\subseteq\mathbb{Q}_{<0}^{2}\), masses \(\mu\), and rational per-agent supplies \((\bar a,\bar b)\), find a finite-support mass allocation \(\lambda_{\theta,a,b}\) over integral bundles \((a,b)\in\mathbb{Z}_{\ge 0}^{2}\) satisfying \(\sum_{a,b}\lambda_{\theta,a,b}=\mu_{\theta}\), \(\sum_{\theta,a,b}a\lambda_{\theta,a,b}=\bar a\), and \(\sum_{\theta,a,b}b\lambda_{\theta,a,b}=\bar b\), such that every positive-mass cohort is EF1 and the allocation is \(fPO\) against all supply-preserving fractional reallocations.
An ex-post high-multiplicity allocation model with valuation-type masses \(\mu\), integral bundle configurations \((a,b)\), mass variables \(\lambda_{\theta,a,b}\), aggregate chore-supply constraints, and feasibility as the objective.
The paper does not establish a polynomial-size support theorem, configuration formulation, or denominator-independent rounding result for the mass allocation with integral bundles and support-wise EF1.
fatal: False
The mirror directly covers Theorem 4.7 and also proposes a more technically demanding analogue of Theorem 5.1. It leaves the nonexistence of simultaneous EFX and \(fPO\), general and personalized valuation settings, and the unnumbered envy-free checking result outside the core anchor.
There is a credible positive case, concentrated on two results. My lead is Theorem 4.7, because its \(fPO\) characterization supplies exactly the kind of structure that can make a high-multiplicity problem tractable. Theorem 5.1 is a stronger fairness target and a valuable second anchor, although its indivisible-item condition makes the continuum limit technically more delicate.
The appropriate regime is a large institution, housing cooperative, hospital, or workplace with many agents sharing a small number of roles. The two chores might be cleaning and cooking. Agents in the same role have the same pair \((v^A,v^B)\), because their contracts, schedules, or physical circumstances make them genuinely interchangeable. There are \(N\) agents, \(N\gg\tau\), where \(\tau\) is the number of distinct valuation types, and the numbers of \(A\)- and \(B\)-chores scale with \(N\). This is a genuine high-multiplicity version of the paper’s setting, not the paper’s four-housemate illustration.
Let the valuation types be
\[ \Theta=\{\theta_1,\ldots,\theta_\tau\},\qquad \theta=(v^A_\theta,v^B_\theta)\in\mathbb{Q}_{<0}^2, \]
with population masses \(\mu_\theta\ge 0\) summing to \(1\). Let \(\bar a,\bar b\) be the numbers of \(A\)- and \(B\)-chores per agent. An allocation is not a fractional chore assignment to an individual. Instead, it is a mass allocation
\[ \lambda_{\theta,a,b}\ge 0, \]
where \(\lambda_{\theta,a,b}\) is the mass of type-\(\theta\) agents receiving the integral bundle \((a,b)\in\mathbb{Z}_{\ge 0}^2\). It must satisfy
\[ \sum_{a,b}\lambda_{\theta,a,b}=\mu_\theta, \]
\[ \sum_{\theta,a,b}a\lambda_{\theta,a,b}=\bar a, \qquad \sum_{\theta,a,b}b\lambda_{\theta,a,b}=\bar b. \]
Thus each individual still receives an indivisible bundle; only the population is represented by mass. For rational data, clearing denominators gives a finite realization: \(N\lambda_{\theta,a,b}\) agents receive bundle \((a,b)\), while \(N\bar a\) and \(N\bar b\) are the chore counts. Conversely, every finite allocation aggregates into such a \(\lambda\). This gives the mirror a precise high-multiplicity dictionary.
Write
\[ u_\theta(a,b)=v^A_\theta a+v^B_\theta b. \]
The first problem is \(\mathrm{EF1+fPO\text{-}Allocation}_\infty^{2\text{-chore}}\).
An instance consists of \((\Theta,\mu,\bar a,\bar b)\) as above. The question is to find an integral-bundle mass allocation \(\lambda\) satisfying the supply constraints, EF1, and \(fPO\). EF1 means that for every two positive-mass bundle cohorts \((\theta,x)\) and \((\theta',y)\), if
\[ u_\theta(x)<u_\theta(y), \]
then there is an actual chore \(e\) in \(x\) such that
\[ u_\theta(x-e)\ge u_\theta(y). \]
Here \(e\) is either one \(A\)-chore or one \(B\)-chore, according to the contents of \(x\).
For \(fPO\), compare \(\lambda\) with fractional reallocations of the chores. A fractional reallocation assigns every cohort \((\theta,x)\) a pair \((\alpha_{\theta,x},\beta_{\theta,x})\in\mathbb{R}_{\ge0}^2\), preserves the aggregate supplies, and weakly improves every agent’s utility:
\[ v^A_\theta\alpha_{\theta,x} +v^B_\theta\beta_{\theta,x} \ge u_\theta(x). \]
It is a Pareto improvement if the inequality is strict on a positive-mass cohort. The allocation \(\lambda\) is \(fPO\) if no such improvement exists. The objective is feasibility: produce one witness allocation.
This mirrors Theorem 4.7, which is proved in this paper, not cited from elsewhere. The theorem states that Algorithm 1 finds an EF1 and \(fPO\) allocation in polynomial time for every two-chore-type instance. Lemma 4.1, also proved as part of the paper’s development, is the key structural support: after sorting agents by the ratio \(v^A_i/v^B_i\), an \(fPO\) allocation has a threshold form. Types below a threshold receive only \(A\)-chores, types above it receive only \(B\)-chores, and only the threshold class may mix.
That structure survives particularly well under continuization. The finite index \(i^\ast\) becomes a threshold in the valuation-type order, while quantities such as “the first \(i^\ast\) agents” become masses of initial intervals. The finite round-robin steps become arithmetic allocation of integer bundle layers to masses. I would expect this problem to be Class A: sort the finitely many valuation types, guess or optimize the threshold, and solve the remaining mass-balance and EF1 conditions using a compact configuration LP or structured flow formulation. The desired complexity would be polynomial in \(\tau\) and the encoding length of \(\mu,\bar a,\bar b\), rather than in the denominator representing the actual population size.
The second problem is \(\mathrm{EFX\text{-}Allocation}_\infty^{2\text{-chore}}\), using exactly the same instance and allocation model. The question is to find \(\lambda\) satisfying the supply constraints and the following EFX condition: whenever a type-\(\theta\) agent with bundle \(x=(a,b)\) envies a positive-mass cohort with bundle \(y\), removing any chore from the envier’s own bundle must remove the envy. Formally, if
\[ u_\theta(x)<u_\theta(y), \]
then
\[ a>0\implies u_\theta(a-1,b)\ge u_\theta(y), \]
and
\[ b>0\implies u_\theta(a,b-1)\ge u_\theta(y). \]
This is a direct population-continuous version of the paper’s EFX definition: chore units remain indivisible, and the quantification is over bundle cohorts of positive mass.
This mirrors Theorem 5.1, proved in this paper, with some supporting lemmas deferred to the authors’ full paper [4]. The theorem states that an EFX allocation always exists and can be found in polynomial time for two chore-type instances. The paper’s Algorithm 2 is especially suggestive for the mirror. Its progress depends on allocating whole layers of identical \(A\)-chores and \(B\)-chores, on the partition of agents according to which type they prefer, and on the valuation ordering. All of those have natural mass counterparts. Repeated applications of Rule 1 or Rule 2 can be batched over a positive mass rather than simulated agent by agent.
I would also expect \(\mathrm{EFX\text{-}Allocation}_\infty^{2\text{-chore}}\) to be Class A, though with less confidence than the EF1+\(fPO\) problem. The challenge is to prove that exact EFX remains representable by a bounded collection of bundle layers and does not require population-size-dependent exceptional agents. If that compression works, Theorem 5.1 should have a genuine high-multiplicity analogue. If it fails, the failure would be an interesting continuum-specific phenomenon: the paper’s finite algorithm might rely essentially on one-agent remainders that disappear when the population becomes atomless.
These mirrors cover only Theorem 4.7 and Theorem 5.1. They do not claim to continuize the general additive-valuation problem, personalized bi-valued valuations, or the nonexistence of simultaneous EFX and \(fPO\). The latter example could be lifted to repeated valuation cohorts, but it is not needed as an anchor. The paper’s unnumbered remark about polynomial-time envy-free checking in the full version is also not an anchor here.
The weakest point is EFX’s dependence on individual indivisible chores. A continuum of agents can make allocation degenerate if one allows a vanishingly small cohort to absorb all chores, or if one silently replaces integral bundles by fractional per-agent bundles. The proposed model avoids that by requiring every positive-mass cohort to receive an integral bundle and by treating \(\lambda\) as a distribution of actual agents, not a lottery for one agent. Nevertheless, a referee could reasonably demand a denominator-independent existence and rounding theorem showing that the mass formulation is the limit of finite EFX allocations without exceptional cohorts. That is a real technical gap, not something to conceal.
The EF1+\(fPO\) mirror is therefore the safer positive case: it preserves the paper’s fairness notion, retains integral bundles, and has the threshold structure of Lemma 4.1 pointing directly toward continuous optimization. The EFX mirror is more ambitious, but still a plausible and recognisable continuous form of the paper’s central theorem.
The negative case must concede at the outset that both proposed anchors are genuine computational results: Theorem 4.7 gives a polynomial-time EF1+\(fPO\) algorithm, and Theorem 5.1 gives a polynomial-time EFX algorithm. Nor is the proposed large-institution scenario fanciful: repeated valuation cohorts and repeated cleaning/cooking chores are a sensible high-multiplicity regime.
The strongest objection is that the literal population limit is degenerate. If the paper’s finite chore set \(M\) is held fixed while the population grows, then the total chore supply per capita tends to zero. Almost every agent receives the empty bundle, while the finitely many nonempty recipients have vanishing population mass. EF1 and EFX then become almost vacuous: empty agents do not envy negatively valued bundles, and the chores can be assigned to a null exceptional set. This is not a meaningful continuous society.
The proponent’s repair scales the chore supply as well, using \(N\bar a\) and \(N\bar b\) copies for \(N\) agents. That is coherent, but it is no longer merely the population continuum of this paper. It is a new repeated-resource market with an additional density parameter \((\bar a,\bar b)\), and with allocations represented by distributions over integral bundle configurations. The rational-clone correspondence now requires cloning both agents and chores. That may be a worthwhile new model, but it is an extension whose legitimacy and complexity cannot simply be inherited from the paper.
This is especially problematic for Theorem 4.7. Lemma 4.1 supplies a threshold characterization of \(fPO\) allocations, but it does not supply a compact representation of allocations that are simultaneously EF1 and \(fPO\). EF1 is support-wise and nonconvex: if a valuation type is split across bundles \(x\) and \(y\), every positive-mass cohort must be checked against every other positive-mass cohort, with a possibly different deleted chore. A purported configuration LP is therefore not automatically an LP. With per-capita supplies encoded in binary, the natural bundle catalogue has size \((\bar a+1)(\bar b+1)\), and the paper gives neither a polynomial-size support theorem nor a pricing oracle.
The claimed batching of Algorithm 1 is also not immediate. Its proof temporarily concentrates all chores on one named split-agent and transfers them one at a time. In a continuum, one individual has zero mass; assigning extensive supply to such an agent produces an unbounded bundle on a vanishing cohort. Replacing that agent by a positive-mass cohort changes the EF1 comparisons, while splitting the cohort creates precisely the support-compatibility problem the configuration formulation has not solved. Thus the threshold survives descriptively, but not yet as a denominator-independent computational theorem.
The EFX anchor is weaker still. Algorithm 2 relies on choosing a particular envy-free agent, applying one-item updates, and reasoning with exact residual counts such as \(|N_A|\), \(|N_B|\), and the number of unallocated chores. EFX is not preserved merely by averaging these updates over a mass: a mass split creates new bundle cohorts, and EFX must hold between every pair of them. Requiring one bundle per valuation type is too restrictive to represent ordinary floor/ceiling effects from indivisible supplies; allowing splits requires a finite-support and rounding theorem that the paper does not provide. Allowing vanishing exceptional cohorts restores the finite algorithm’s behavior only by reintroducing the degeneracy above.
The possible repairs all change something substantial. Fixed supplies make the limit vacuous; scaled supplies create a repeated-resource extension; one bundle per type loses finite allocation fidelity; arbitrary bundle lotteries replace ex-post EFX by an ex-ante notion; and support-wise EFX leaves an unresolved configuration problem. Consequently, neither Theorem 4.7 nor Theorem 5.1 presently yields a clean population-only continuous mirror with a demonstrated computational object.
This is not an airtight universal impossibility claim. The institutional repeated-chore model is genuinely plausible, and a successful denominator-independent configuration algorithm would make the positive case strong. But that result would be new work about a jointly scaled repeated-resource market, not a consequence of continuizing this paper. The best negative conclusion is therefore that the proposed mirrors are promising extensions, but not yet worthwhile ChoCo anchors under the programme’s stricter population-continuum standard.
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.