| paper | Fair and Efficient Allocations of Chores under Bivalued Preferences |
| authors | Jugal Garg, Aniket Murhekar, John Qin |
| venue | AAAI 2022 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given divisible chores \(M\), one unit of each chore, a finite support \(T\) of complete cost types \(c_t\in\{1,k\}^{M}\), and rational masses \(\mu_t>0\) summing to \(1\), choose mass assignments \(z_{tj}\ge0\) with \(\sum_{t\in T}z_{tj}=1\) for every \(j\). Define type \(t\)'s cost for type \(t'\)'s average bundle by \(D_t(z_{t'})=\sum_{j\in M}c_t(j)z_{t'j}/\mu_{t'}\). Find a feasible \(z\) satisfying \(D_t(z_t)\le D_t(z_{t'})\) for all \(t,t'\), such that no feasible \(y\) has \(D_t(y_t)\le D_t(z_t)\) for every \(t\) with strict inequality for some \(t\).
A type-capacitated divisible-chore market: \(\mu\) describes repeated complete cost types, \(z_{tj}\) is total chore mass assigned to type \(t\), costs are additive and bivalued, and the output is an envy-free and Pareto-optimal allocation.
The strongest objection is that divisible allocation makes equal-cost agents interchangeable, so the mirror may be an exact quotient whose algorithmic novelty is routine; the proponent also used per-capita language that could inadvertently continue the chore supply. This bounds the depth of the proposed contribution but does not defeat the well-posed high-multiplicity problem.
fatal: False
The mirror covers Theorem 2's bivalued divisible-chore EF+PO computation under a type distribution. It leaves Theorem 1's indivisible EF1+fPO result and the paper's general-valued and open problems untouched.
I would make Theorem 2 the lead, and stop at one anchor. The paper contains no named NP-hardness or other hardness theorem of its own; its two principal named results are positive algorithmic results. Theorem 2 is the cleaner mirror because its divisible-chore model permits a genuine population limit without destroying the meaning of envy-freeness.
The continuous problem would be Mass EF+PO for Bivalued Chores. An instance consists of a finite set of chore categories \(M\), a finite support \(T\) of agent types, a rational mass vector \(\mu\) with \(\sum_{t\in T}\mu_t=1\), and a rational \(k\ge1\). Each type \(t\) has a complete cost vector \(c_t\in\{1,k\}^{M}\). Thus two agents have the same type exactly when they have the same cost for every chore; any additional relevant parameter would also have to be included in the type.
The interpretation is a large institution—say a citywide cleaning service, hospital network, or school system—with millions of workers but a small catalogue of cost profiles. The mass \(\mu_t\) is the fraction of workers of type \(t\). A plausible regime has \(N\) in the millions while \(\tau=|T|\) is perhaps tens or hundreds. The relevant agents are not a seven-person household, but a repeated labour market with standardized qualifications, training, or working conditions.
Let \(q_j\) be the amount of chore \(j\) available per unit population. The decision variable is \(x_{tj}\ge0\), the amount of chore \(j\) assigned to each member of type \(t\). Feasibility requires \(\sum_{t\in T}\mu_t x_{tj}=q_j\) for every chore \(j\). The per-agent cost of type \(t\) is \(d_t(x)=\sum_{j\in M}c_t(j)x_{tj}\).
The question is to construct an allocation \(x\) satisfying
\(d_t(x)\le \sum_{j\in M}c_t(j)x_{t'j}\)
for every pair of types \(t,t'\) with positive mass, and such that no other feasible allocation \(y\) weakly lowers every type’s cost and strictly lowers the cost of one positive-mass type. In other words, the output must be an envy-free and Pareto-optimal allocation for the population. The objective is feasibility and construction, exactly as in the paper, not the optimization of an additional welfare function. A price vector and market-equilibrium certificate may be output as auxiliary evidence, but are not part of the allocation itself.
This is genuinely a population continuization. The paper’s divisible chores remain divisible because that is part of the anchored problem; the new continuous object is the society of agents, represented by \(\mu\) rather than by an explicit list of \(N\) names. The type-symmetric formulation is natural here: identical agents can be averaged, and in the divisible setting this preserves their costs, envy comparisons, and the market-based Pareto argument. Equivalently, for rational \(\mu\), the instance is the high-multiplicity limit of finite instances containing \(N\mu_t\) copies of each type. The important algorithmic requirement is therefore a running time polynomial in \(m\), \(\tau\), and the encoding length of \(\mu\), rather than polynomial in the potentially enormous denominator-expanded population \(N\).
The named anchor is Theorem 2, proved by the authors, with the conference version stating that the detailed proof appears in their full version, Garg, Murhekar, and Qin (2021). It states that for bivalued divisible chores, an EF+PO allocation can be computed in strongly polynomial time. My continuous problem preserves its cost domain \(\{a,b\}\), its chore-allocation action, and exactly its EF and PO requirements. It changes only the representation of the agent side from named agents to a distribution of repeated types. The authors should recognize this as the high-multiplicity version of their own problem, not as a welfare surrogate or a different fairness notion.
I expect this mirror to be Class A: tractable. The paper’s Section 4 already uses balanced flow, prices, mBB relations, groups, and price-raising. Those are precisely the structures that should aggregate well: named agents become type nodes with capacities \(\mu_t\), and transfers between agents become flows between type masses. The relevant graph has \(m+\tau\) nodes rather than \(m+N\). The bivalued restriction is doing real work, since it is what makes the mBB structure and the group argument manageable. Thus the expected result is a compressed strongly polynomial or at least \(\mathrm{poly}(m,\tau,L)\) algorithm that never expands the population.
This mirror generates several useful questions. Can the balanced-flow construction in Theorem 2 be stated directly with fractional type capacities? Can every type-symmetric EF+PO allocation be implemented in finite high-multiplicity instances, and with what rounding guarantee if the chores are later made indivisible? Does the algorithm remain strongly polynomial when masses are rational, or only polynomial in their encoding length? Finally, when the bivalued restriction is replaced by three or more cost values, does hardness arise from the number of types or from the chore-side structure?
My weakest point is that the anchor already allows divisible chores. A critic could say that the apparent continuity comes from fractional allocation rather than from the population. That criticism would be correct for a finite-agent version of the problem, and I would not present that as a ChoCo mirror. Here, however, divisibility is held fixed from the paper’s own anchor, while the society is replaced by the mass vector \(\mu\), and the central new question is whether the theorem survives compressed high multiplicity. The other weakness is that the paper does not prove the type-compressed algorithm; the positive case is a strongly motivated Class A research problem, not a result already established by Theorem 2.
I would not anchor on Theorem 1. Its indivisibility creates a genuine atom problem in a continuum of agents: with finitely many indivisible chores, almost all agents receive nothing, while with chores scaled proportionally to population the aggregate limit begins to look like a different divisible-resource model. Theorem 2 therefore gives the strongest honest continuous mirror in this paper.
The strongest case against the proposed mirror is that it does not really expose a population-level computational phenomenon. In the divisible model, agents with the same cost vector are already interchangeable. If \(I_t\) is a set of agents of type \(t\), then any EF allocation gives all agents in \(I_t\) the same cost: EF applied in both directions yields equality. Their allocations can therefore be averaged and replaced by one common fractional bundle without changing feasibility, EF, or PO. The finite instance is exactly quotiented by its cost types.
Thus the proposed mass problem is not a new social-choice object so much as a compressed representation of the paper’s existing divisible-allocation problem. The mass vector appears only as a capacity in constraints such as
\[ \sum_{t\in T}\mu_t x_{tj}=q_j, \]
while the EF constraints remain typewise and unweighted. There is no identity-sensitive operation, targeting decision, indivisibility, or minimum-granularity effect for population continuization to reveal. The algorithmic question is essentially whether the authors’ finite-agent market proof can be implemented on these already-interchangeable rows.
The proposed institutional story also requires care. With a fixed finite set of chores, increasing the number of agents merely gives more agents shares of the same divisible objects; the population is not generating new work or new allocation structure. If instead each chore category supplies \(q_j\) units per capita, then the model has quietly replaced the paper’s finite set of chores by homogeneous commodity mass. That may be a worthwhile Fisher-market model, but its nontriviality comes from continuing the resource side as well as the population side. It is no longer cleanly a population-only mirror of Theorem 2.
A still stronger version would demand EF for individual agents rather than merely for positive-mass types, or would allow type distributions with arbitrarily small masses. But that does not rescue the objection: with complete types and divisible chores, the typewise formulation is the exact high-multiplicity formulation, and rational masses can be expanded into finite repeated-agent instances.
The difficulty is that this negative case ultimately does not defeat the anchor. The proponent has supplied precisely the kind of repeated-type institution the programme permits, and the distinction between a quotient and a “new” problem cannot by itself disqualify high-multiplicity work. The fact that Theorem 2 is already strongly polynomial in the explicit number of agents also does not answer whether it admits an algorithm polynomial in \(\tau\) and the encoding length of \(\mu\). That compressed question could be a genuine contribution.
So the honest verdict is that the universal negative claim is weak here. Theorem 2 survives: its divisible setting supports a coherent population distribution, the type definition is exact, and the high-multiplicity version poses a legitimate compression question. The best objection is that the mirror may be technically routine rather than conceptually deep, but that is not enough to establish that it is not worth asking.
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.