| paper | Asymptotic Fair Division: Chores Are Easier Than Goods |
| authors | Pasin Manurangsi, Warut Suksompong |
| venue | IJCAI 2025 |
| 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.1
statement extracted from the paper’s text layer
Given finite agent types \(T\) with rational masses \(\mu_t\), recurring chore classes \(Q\) with rational per-capita supplies \(\lambda_q\) satisfying \(\sum_q\lambda_q\le1\), and disutilities \(d_{tq}\), decide whether all chore mass can be assigned in singleton bundles: does there exist \(y_{tq}\ge0\) such that \(\sum_t y_{tq}=\lambda_q\), \(\sum_q y_{tq}\le\mu_t\), and \(y_{tq}=0\) whenever \(d_{tq}>\sum_{q'}\lambda_{q'}d_{tq'}\)?
A high-multiplicity sparse chore-allocation model in which \(\mu_t\) is the mass of agents with complete disutility type \(t\), \(\lambda_q\) is the supply of recurring chore class \(q\), and \(y_{tq}\) is assignment mass; the objective is proportional-feasibility, equivalently maximizing covered chore mass.
Replacing the paper's non-atomic independent valuation matrix and sparse finite-sample randomness by repeated class-level disutilities and per-capita chore supplies changes the substantive probabilistic mechanism into a deterministic capacitated flow.
fatal: False
The mirror covers Theorem 4.1's sparse matching-based proportional-allocation component and therefore part of Theorem 1.3; it leaves the full \(m=\omega(1)\) threshold, Theorems 1.1, 1.2, and 1.4, and the other fairness implications unmirrored.
The best positive case is narrow but real: the paper’s sparse-\(m\) proportionality algorithm has a clean population mirror. My lead anchor is Theorem 4.1, proved in this paper. It states that, under the paper’s PDF-bounded assumptions and \(m\log m\le n/40\), a polynomial-time algorithm finds a proportional allocation with high probability. This is the matching-based core of the broader Theorem 1.3, also proved here. I would not claim that the whole asymptotic theorem transfers automatically.
Call the continuous problem Sparse Proportional Chore Matching\(_\infty\). An instance consists of:
The proportional budget of type \(t\) is
\[ p_t=\sum_{q\in Q}\lambda_q d_{tq}. \]
This is exactly the discrete proportional threshold after scaling: with \(N\) agents and \(N\lambda_q\) indivisible copies of chore class \(q\), the total disutility of all chores to a type-\(t\) agent is \(Np_t\), so one \(N\)-th share is \(p_t\).
The decision variable is \(y_{tq}\), the mass of type-\(t\) agents receiving one whole chore of class \(q\). Every remaining agent receives the empty bundle. We seek \(y\) satisfying
\[ \sum_{t\in T} y_{tq}=\lambda_q \quad\text{for every }q, \]
\[ \sum_{q\in Q}y_{tq}\le\mu_t \quad\text{for every }t, \]
and
\[ y_{tq}=0 \quad\text{whenever }d_{tq}>p_t. \]
Equivalently, one may maximize covered chore mass and ask whether the optimum equals \(\sum_q\lambda_q\). A feasible solution is a distribution over integral bundles: type \(t\) receives the empty bundle with mass \(\mu_t-\sum_qy_{tq}\), and the singleton bundle \(\{q\}\) with mass \(y_{tq}\).
This is population continuization, not fractional chores. In a finite realization with scale \(N\), there are \(N\mu_t\) agents of type \(t\) and \(N\lambda_q\) distinct indivisible chores of class \(q\); each chore is assigned whole to one agent, and each agent receives at most one chore. The variables \(y_{tq}\) record only the limiting frequencies of these assignments. Rational masses can be lifted to finite instances by clearing denominators.
The natural regime is a large pool of interchangeable workers or residents, with \(N\) much larger than the number \(\tau=|T|\) of complete disutility profiles. Chore classes represent recurring medical shifts, teaching duties, service tasks, or household chores. The sparse regime corresponds to \(m=N\sum_q\lambda_q\) satisfying the paper’s \(m\log m\le N/40\): many agents, relatively few chores, and most agents receiving none. This is a plausible high-multiplicity version of precisely the setting used in the proof of Theorem 4.1, whose Algorithm 2 restricts attention to one-or-zero-chore allocations and uses a right-saturated matching.
I expect Sparse Proportional Chore Matching\(_\infty\) to be Class A. Construct a bipartite graph between chore classes and agent types, retain the edge \(q\text{--}t\) exactly when \(d_{tq}\le p_t\), and solve the resulting capacitated transportation problem. It is polynomial in \(|T|+|Q|\) and the encoding length of the rational data. The continuum makes the matching capacities explicit; it does not introduce a new hardness source.
The authors should recognize this as their proportional-chore problem in a high-multiplicity regime, not as an unrelated fractional-allocation problem. The fairness benchmark is unchanged, disutilities remain additive, chores remain indivisible in every finite realization, and the matching construction is directly inherited from their proof. What changes is that many agents share a complete disutility type and are represented by mass.
This mirror deliberately covers only the sparse, one-chore-per-agent component represented by Theorem 4.1, and hence that component of Theorem 1.3. It generates worthwhile extensions: allowing \(\sum_q\lambda_q>1\) requires integral multi-chore configurations and a configuration LP; continuous envy-freeness would require comparing every assigned bundle with every bundle in the support; and one could ask whether the paper’s \(m=\omega(1)\) threshold has a counterpart for random type measures.
The weakest point is that a fixed finite inventory of indivisible chores degenerates against an atomless population: almost everyone receives nothing, and proportionality becomes meaningless. The mirror therefore uses a per-capita supply of recurring chore copies, so agents and chore copies scale together. That is a joint high-multiplicity regime, not a literal fixed-\(m\) limit. If “continuization” is required to hold the inventory fixed, I would withdraw the claim. Under the programme’s high-multiplicity interpretation, however, the model is a credible and computationally useful continuous mirror of the paper’s matching-based proportional-allocation result.
The proposed anchor fails at the level of the random object it claims to mirror. In this paper, an agent’s complete type is her entire valuation vector \((d_i(1),\ldots,d_i(m))\). Because \(D\) is non-atomic, two agents have the same complete type with probability zero. Thus the paper’s own model has no finite high-multiplicity population: grouping agents by complete type gives \(\tau=n\) almost surely.
This is not the objection that prices or costs cannot be type-dependent. The problem is that the proposed \(d_{tq}\) model replaces the paper’s independent agent–chore matrix by exact correlations: every member of type \(t\) values every copy of class \(q\) identically. That is a plausible recurring-shifts model, but it is not a high-multiplicity representation of the paper’s stochastic instance. It removes precisely the random structure used by Theorem 4.1: favorite-chore collisions, independent eligibility edges, and the concentration argument behind the matching.
The natural repair is to retain the full valuation vector and let the population be a measure on \([0,1]^m\). That does preserve the paper’s semantics, but it destroys the proposed finite-type mirror. The measure is atomless and almost every agent is a distinct type. Any algorithm must then access an arbitrary measure over complete valuation vectors, rather than a finite list of type masses. If randomness is instead resampled within each chore class, the realized cost of a copy is no longer determined by the agent’s type, so the “type” is incomplete and the proportionality predicate has changed.
There is also an asymptotic mismatch that scaling the chore supply does not repair. The sparse theorem assumes
\[ m\log m\le \frac n{40}, \]
so \(m/n\to0\). In normalized population units, the total chore mass therefore tends to zero. With finitely many fixed chore classes, the continuous limit contains no chores at all; it cannot distinguish \(m=O(1)\) from \(m=\log\log n\), even though Theorems 1.3 and 1.4 distinguish them sharply. If the classes retain positive mass, then \(m=\Theta(n)\), outside the sparse regime. If one keeps every chore as a separate class, then the number of classes grows with \(m\), and the item multiplicity—not the population multiplicity—carries the asymptotics.
The same issue explains why the proposed flow is not actually the computational content of Theorem 4.1. In the paper, the flow algorithm is elementary; the substantive theorem is that a random finite graph has the required matching with high probability. In the proposed model, the graph is a deterministic eligibility graph on \(T\times Q\), and the answer is simply a capacitated transportation problem. That is a legitimate new allocation model, but cloning the population does not generate the paper’s probability or its \(m=\omega(1)\) threshold. A random matrix over type classes would only restore an asymptotic question by making \(|T|\) or \(|Q|\) grow, at which point the finite-type high-multiplicity compression has disappeared.
The stronger repair of preserving the random population also fails to retain the paper’s nonexistence phenomena. For a continuum of agents, a chore has a positive mass of agents below any threshold at which \(D\) assigns positive probability. The finite event that every one of \(n\) agents is ineligible—the mechanism behind Theorem 1.4—vanishes as sampling noise disappears. Reintroducing that event requires a finite sample, a Poisson population, or some other discrete population mechanism.
One could instead mirror envy-freeness in a recurring-class model with \(m/n\) bounded below. But then one must retain the full support of indivisible bundles: a type split across bundles must compare each assigned bundle with every bundle in the population. Replacing this by expected disutility gives a different fairness notion; retaining it yields a configuration-support problem unrelated to the paper’s random threshold arguments. It is an interesting extension, but not a faithful continuous mirror of the named results.
So the strongest negative conclusion is that Theorems 4.1 and 1.3 do not survive population continuization as stated. Their interesting content is finite-sample randomness over individually distinct valuations. A finite type/class model yields a useful deterministic flow, while a faithful measure-valued model loses finite representation and the sparse threshold. The honest weakness is that, under ChoCo’s permissive notion of an author-recognizable extension, recurring medical shifts or teaching duties may still justify studying the proposed flow as a new Class A problem. I do not think the universal “no worthwhile scenario” claim is airtight; the case against is strongest only if “mirror” must preserve the paper’s stochastic object and asymptotic source of content.
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.