| paper | Weighted EF1 and PO Allocations with Few Types of Agents or Chores |
| authors | Jugal Garg, Aniket Murhekar, John Qin |
| venue | IJCAI 2024 |
| 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 2
statement extracted from the paper’s text layer
Given rational per-capita supplies \(\rho_A,\rho_B\), integer capacity \(K\), and a finite distribution \(\mu\) over complete agent types \(t=(d_{t,A},d_{t,B},w_t)\), find a finite-support mass allocation \(q_{t,r,s}\ge0\) to integral bundles \((r,s)\) with \(r+s\le K\), satisfying \(\sum_{r,s}q_{t,r,s}=\mu_t\), \(\sum_{t,r,s}r q_{t,r,s}=\rho_A\), and \(\sum_{t,r,s}s q_{t,r,s}=\rho_B\), support-wise wEF1 \(\phi_t(r,s)/w_t\le d_t(r',s')/w_u\) whenever \(q_{t,r,s}q_{u,r',s'}>0\), where \(d_t(r,s)=r d_{t,A}+s d_{t,B}\) and \(\phi_t\) is the minimum disutility after removing one bundle item, and such that no feasible fractional reallocation weakly improves almost every holder and strictly improves a positive-mass set; output \(q\) or certify none exists.
Complete types are recurring \(t=(d_{t,A},d_{t,B},w_t)\); \(\mu_t\) is agent mass, \(q_{t,r,s}\) is mass assigned an indivisible \((r,s)\) bundle, and \(\rho_A,\rho_B\) are per-capita chore supplies. The task is constrained feasibility and construction, with no objective beyond wEF1 and fPO.
The paper proves no invariant showing that pivot transfers and one-chore progress aggregate over mass supports, while the workload scaling and capacity are substantive regime choices.
fatal: False
The mirror directly covers Theorem 2 and has an analogous three-disutility-class version for Theorem 1; it leaves the unrestricted named-agent formulations, auxiliary lemmas, and the general symmetric open case untouched.
The strongest positive case is a genuine one, although I would describe it as an author-recognisable high-multiplicity extension rather than a literal limit theorem. My lead anchor is Theorem 1, proved in this paper.
The natural regime is a large computing cluster of the kind mentioned in the paper: many processing units or employees, but only a few standardized disutility profiles. A complete agent type must include both the disutility vector and the entitlement \(w\). Thus agents with the same disutilities but different contractual weights are different full types, although their disutilities belong to one of the paper’s three agent-type functions. In the intended regime there are \(N\gg 1\) agents but only finitely many full types \(T\), with rational masses \(\mu_t\).
The workload must scale with the population. Keeping a fixed finite set of chores while \(N\) grows would make almost everyone receive nothing and would destroy the meaning of EF1. Let \(J\) be a set of recurring chore classes and let \(\rho_j\) be the number of copies of class \(j\) per unit population. Each physical chore remains indivisible; \(\rho_j\) is a per-capita description of a large repeated workload. A bounded-load version may impose a fixed daily capacity \(K\) on each agent.
A bundle is an integer vector \(B\in\mathbb Z_{\ge0}^{J}\), with \(\sum_j B_j\le K\). The decision variable is
\[ q_{t,B}\ge 0, \]
the mass of type-\(t\) agents receiving the integral bundle \(B\). Feasibility requires
\[ \sum_B q_{t,B}=\mu_t \]
for every \(t\), and
\[ \sum_{t,B}q_{t,B}B_j=\rho_j \]
for every chore class \(j\). Thus the model fractionalizes the population of identical agents, not individual chores.
For a type \(t\), write \(d_t(B)=\sum_j d_{t,j}B_j\). Define
\[ \phi_t(B)= \begin{cases} 0,&B=\mathbf 0,\[2mm] \displaystyle\min_{j:B_j>0}d_t(B-e_j),&\text{otherwise}. \end{cases} \]
The allocation is support-wise wEF1 if, whenever \(q_{t,B}>0\) and \(q_{u,B'}>0\),
\[ \frac{\phi_t(B)}{w_t} \le \frac{d_t(B')}{w_u}. \]
This preserves the paper’s universal, ex-post fairness condition: it does not replace every agent’s guarantee by an average disutility.
The allocation is fractionally Pareto-optimal if there is no measurable fractional reallocation \(z(\omega)\) of the chore mass, respecting the same per-agent capacity, such that
\[ d_t(z(\omega))\le d_t(B(\omega)) \]
for almost every agent and strict inequality holds on a positive-mass set. The computational problem is:
\(3\)-Type Weighted EF1–fPO\(_\infty\): given rational type masses \(\mu_t\), weights, disutilities, per-capita chore supplies, and \(K\), output a finite-support rational \(q\) satisfying feasibility, support-wise wEF1, and fPO, or certify that none exists.
This is the continuous mirror of Theorem 1. The theorem itself says that for every three-agent-type instance a wEF1 and fPO allocation exists and can be computed in polynomial time; it is proved here, not cited from elsewhere. The mirror preserves exactly the paper’s core objects: additive disutilities, unequal entitlements, indivisible bundles, wEF1, and fPO. The paper’s weighted picking sequence and competitive-equilibrium framework suggest a Class A outcome. In the mass version, picking events should become cumulative threshold events and the allocation should become a finite configuration-flow LP, with pricing over integral bundles. The desired running time would depend on the number of chore classes, full agent types, \(K\), and encoding length, but not on the number of cloned agents.
There is also an exact rational-clone dictionary. If all masses are rational, clearing denominators gives \(D\mu_t\) agents of type \(t\), \(Dq_{t,B}\) agents receiving bundle \(B\), and \(D\rho_j\) copies of chore \(j\). Conversely, any finite repeated-type instance induces such a \(q\). Support-wise wEF1 is preserved exactly, and the positive-mass Pareto condition corresponds to improvement of at least one clone. This is why the model is more than merely replacing \(n\) by a real number.
A secondary anchor is Theorem 2, also proved in this paper. It gives the same existence and polynomial-time conclusion for arbitrary agents when there are only two chore types. Its continuous problem is cleaner:
\(2\)-Chore-Type Weighted EF1–fPO\(_\infty\): given rational masses \(\mu_t\) over finitely many full agent types \(t=(d_{t,A},d_{t,B},w_t)\), and per-capita supplies \(\rho_A,\rho_B\), find a rational mass allocation \(q_{t,(r,s)}\) of integral bundles containing \(r\) \(A\)-chores and \(s\) \(B\)-chores, satisfying the two supply equations, support-wise wEF1, and fPO.
For this problem the wEF1 constraint is explicitly
\[ \frac{1}{w_t} \min\!\left\{ (r-1)d_{t,A}+s d_{t,B}\;:\;r>0,\; r d_{t,A}+(s-1)d_{t,B}\;:\;s>0 \right\} \le \frac{r'd_{t,A}+s'd_{t,B}}{w_u}. \]
I would also expect this problem to be Class A in the bounded-load regime. The proof of Theorem 2 sorts agents by the ratio \(d_{t,A}/d_{t,B}\); with mass types, that order becomes a one-dimensional type order, and the pivot transfers should become aggregate mass transfers. The paper’s own “heavy or light jobs” example makes this especially recognisable.
The weakest point is unavoidable: neither mirror is a direct continuization of the paper’s completely unrestricted finite model. A fixed chore supply makes fairness degenerate as the population grows; scaling chore supplies introduces a repeated-workload regime; and the bounded bundle size \(K\) is an additional modelling assumption. Removing indivisibility by allowing arbitrary fractional bundles would be easier, but would no longer be the authors’ problem. I would therefore present Theorem 1 as the lead, with an explicit label of “high-multiplicity extension,” not claim that the paper already proves its continuous theorem.
The main open questions are whether \(K\) can be removed, whether configuration separation is polynomial in the binary encoding of \(\rho\), whether the paper’s weighted-picking arguments admit a compact cumulative-mass representation, and what rounding guarantee converts a continuous solution back to a finite election without losing wEF1 or fPO.
The strongest negative case is that neither theorem is a theorem about a genuinely continuous population once “type” is interpreted correctly.
Theorem 1 says there are three disutility functions, but weights may differ arbitrarily. Under ChoCo’s definition, weight is part of an agent’s complete type: it appears directly in wEF1 and in the weighted picking sequence. Thus an instance with three paper-types may contain \(n\) complete types. A finite-mass model with only a few full types must restrict weights to a recurring finite menu; a model allowing arbitrary weights requires a distribution over weights rather than the paper’s three-type object. The proposed mirror therefore preserves either the paper’s preference structure or its unequal-entitlement generality, but not both.
There is also a scaling obstruction. With a fixed set of indivisible chores and \(n\to\infty\), almost every agent receives nothing. EF1 then loses its intended content: one can distribute the finitely many chores among finitely many agents, leaving the rest empty. To avoid this, the proposed mirror scales the chore supply with the population, introduces recurring chore classes, and often imposes a bundle capacity \(K\). That is a legitimate new repeated-workload model, but it is not a population-only continuization of the paper’s instances. The central object becomes a configuration allocation \(q_{t,B}\) over bundles, with both agent multiplicity and chore multiplicity built into the model.
The rational-clone dictionary does not resolve this objection. It shows that the proposed problem is a succinct description of a family of finite cloned instances. It does not identify a canonical limit of the paper’s arbitrary finite instances. In particular, the finite-clone equivalence holds only after imposing repeated complete agent types, repeated chore classes, and a chosen workload scaling. Those are precisely the additional modelling assumptions that require justification.
Theorem 1’s proof also gives no population-level object for free. Its weighted picking sequence tracks each agent’s integer chore count \(s_i\), while the competitive-equilibrium argument repeatedly transfers one named chore between named groups and updates payments. In a mass model, one such transfer has size \(1/D\) after denominator clearing and disappears in the limit. Replacing the sequence by “cumulative threshold events” is not a reformulation of the proof; it is a new algorithmic problem whose fairness and fPO invariants have yet to be established.
Theorem 2 has the same difficulty in a cleaner form. Its “two chore types” assumption already supplies multiplicity on the chore side, while “arbitrary agents” allows every pair \((d_{i,A},d_{i,B})\) and every weight to be unique. A finite full-type distribution therefore studies a restricted recurring-agent regime, not the theorem’s arbitrary-agent result. If the bundle capacity \(K\) is fixed, the proposed model has a finite configuration set and is essentially a new cohort allocation problem. If \(K\) grows with the workload, the bundle space becomes unbounded or exponentially large, and the proposed finite configuration-flow formulation disappears.
The ratio ordering used in Algorithm 3 does not automatically aggregate either. The algorithm’s pivot is an individual agent, and its progress is measured by successive one-chore transfers to carefully selected least earners. With masses, a type can occupy several bundles, least-earner status can change at support boundaries, and a transfer of one chore is infinitesimal at population scale. The paper proves no invariant for this setting. Again, that does not prove the mass problem uninteresting, but it means the claimed mirror is not supplied by Theorem 2.
The fPO repair is natural but substantive. In the finite paper, improving one agent suffices; in an atomless population, improvement on a null set is invisible, so the proposed definition requires strict improvement on positive mass. That is probably the right convention, and I would not reject a model solely for making it. But it confirms that the proposed problem is a new population-level Pareto concept rather than a literal continuation of the paper’s definition.
So the negative case can defeat the mirrors as stated: Theorem 1’s headline “three agent types” is not three complete types, Theorem 2’s arbitrary-agent regime is lost, and both proposed formulations require scaling chores and adding capacity. The resulting questions may be worthwhile, but they are new repeated-workload fair-division problems rather than continuous mirrors clearly anchored in the paper.
The honest limitation is that this is not an airtight universal rejection. Under ChoCo’s explicit acceptance of high-multiplicity extensions, the proponent’s construction is author-recognisable and mathematically legitimate. I would reject the claim that the paper already supplies a clean continuous mirror, but I could not honestly claim that no worthwhile mirror exists in any scenario.
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.