| paper | Allocating Contiguous Blocks of Indivisible Chores Fairly: Revisited |
| authors | — |
| venue | AAMAS 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 |
Lemma 7
statement extracted from the paper’s text layer
Given \(N\), \(m\), a finite type set \(T\), rational disutility vectors \(a_t\in\mathbb{Q}_{\le 0}^m\) with \(\sum_j a_t(j)=-1\), and a rational society distribution \(\mu\in\Delta(T)\), let \(\mathcal{K}_{\mathrm{MMS}}\) be the typed contiguous allocations of one \(m\)-chore path among \(N\) slots in which every type-\(t\) slot receives value at least \(M_t=\max_{(I_1,\ldots,I_N)\in\Pi_N([m])}\min_\ell a_t(I_\ell)\). Over masses \(z_\kappa\ge 0\) of repeated paths using configuration \(\kappa\), find a \(z\) satisfying \(\sum_\kappa z_\kappa=1\) and \(\sum_\kappa z_\kappa r_t(\kappa)=N\mu_t\) for every \(t\), maximizing \(\sum_\kappa z_\kappa\sum_{(t,I)\in\kappa}a_t(I)\), without splitting any chore within a path.
A high-multiplicity collection of identical paths: \(T\) contains complete valuation types, \(\mu\) gives population masses, \(z_\kappa\) gives masses of integral typed contiguous configurations, and the objective is average utilitarian welfare subject to exact type-mass and MMS constraints.
The repeated-path construction fixes an \(N\)-agent MMS benchmark and localizes fairness to each path, so global constraints \(\sum_{\kappa} z_{\kappa}r_t(\kappa)=N\mu_t\) do not preserve the single-path semantics or the paper's lower-bound composition.
fatal: False
The mirror covers the constructive MMS and PROP1 algorithms in Lemmas 7 and 13 and the associated utilitarian welfare questions in Theorems 12 and 18; it leaves the egalitarian results in Theorems 11 and 17 and the \(n=2\) theorem without demonstrated counterparts.
The strongest positive case is a qualified Class-A mirror for the paper’s utilitarian MMS and PROP1 results. It is not a literal \(n\to\infty\) limit of one path with a fixed inventory; the defensible regime is a high-multiplicity collection of repeated path instances.
Take \(q\) identical schedule-paths. Each path has \(m\) indivisible chores, \(N\) agent slots, and contiguous bundles. A type \(t\) is the complete additive disutility vector \(a_t=(a_t(1),\ldots,a_t(m))\), with \(a_t(j)\le0\) and \(\sum_j a_t(j)=-1\). The society is a rational mass vector \(\mu\in\Delta(T)\): across the \(qN\) agents, a fraction \(\mu_t\) has type \(t\). The natural regime has \(qN\gg\tau\), often with \(\tau=2\): for example, recurring maintenance crews whose members fall into a few exchangeable skill/disutility profiles, allocated contiguous runs of tasks on many identical district schedules.
The action is not fractional allocation of chores. Let \(\mathcal K_F\) be the finite set of complete typed allocations \(\kappa\) of one path: every chore belongs to one contiguous bundle, every one of the \(N\) slots has a type, and every slot satisfies fairness criterion \(F\). Empty bundles are allowed for MMS exactly as in the paper; for PROP1 we restrict to the paper’s nonempty feasible regime. Let \(r_t(\kappa)\) be the number of type-\(t\) agents in \(\kappa\), and let \(u(\kappa)\) be its utilitarian welfare.
A continuous allocation is a mass \(z_\kappa\ge0\) over whole integral configurations, satisfying \(\sum_{\kappa}z_\kappa=1\) and \(\sum_{\kappa}z_\kappa r_t(\kappa)=N\mu_t\) for every type \(t\). Thus \(z_\kappa\) says what fraction of repeated schedule-paths uses configuration \(\kappa\). The objective is \(\sum_\kappa z_\kappa u(\kappa)\). A rational solution can be denominator-cleared into finitely many repeated paths, with no chore ever split.
The lead anchor is Lemma 7, proved here: “For any \(\beta\le -2/n\), ALG-M(\(\beta\)) returns an MMS allocation in polynomial time.” Its welfare-level companion is Theorem 12, also proved here, which establishes \(\operatorname{PoF}(\mathrm{UW}\mid\mathrm{MMS})=\Theta(n)\) and obtains the upper bound through the polynomial-time construction ALG-M\((-2/n)\).
The corresponding continuous problem is:
\(\mathrm{MMS\text{-}UW}_\infty\): given \(N,m,T,\mu\), and the rational valuation vectors \(a_t\), compute a mass \(z\) over MMS-fair typed contiguous allocations satisfying the type-mass constraints and maximizing utilitarian welfare. Equivalently, given \(B\), decide whether such a \(z\) exists with welfare at least \(B\).
For type \(t\), the MMS threshold \(M_t\) is exactly the paper’s quantity \(MMS_i\), with \(a_t\) substituted for the agent valuation. The fairness restriction is simply \(a_t(I)\ge M_t\) for every interval \(I\) assigned to type \(t\). Lemma 4, proved here, gives polynomial-time computation of each \(M_t\).
I expect this problem to be Class A. Although the configuration LP has exponentially many columns, its pricing problem is a path dynamic program: given dual prices for type counts, choose a sequence of at most \(N\) contiguous intervals, assigning each interval an admissible type. The DP runs over path positions, interval endpoints, and the number of bundles. Hence the continuous welfare problem has exactly the configuration-LP shape that the ChoCo programme is designed to exploit.
Theorem 12’s \(\Theta(N)\) price should remain meaningful in this regime. Its lower-bound construction uses only two valuation types: one exceptional type and one common type, with \(\mu=(1/N,(N-1)/N)\). The argument that every MMS allocation forces many chores onto the common types applies path by path and therefore survives averaging over repeated paths. The upper bound also survives by applying ALG-M\((-2/N)\) to each path and averaging. The natural continuous research question is whether the exact price remains \(\Theta(N)\) for all \(\mu\), and whether finer bounds can depend on \(\tau\) or the small exceptional masses.
The second anchor is Lemma 13, proved here: “For any \(\beta\le -2/n\), ALG-P(\(\beta\)) returns a PROP1 allocation in polynomial time.” Its welfare consequence is Theorem 18, proved here, which establishes \(\operatorname{PoF}(\mathrm{UW}\mid\mathrm{PROP1})=\Theta(n)\).
The corresponding problem, \(\mathrm{PROP1\text{-}UW}_\infty\), has the same instance and configuration variables, but an interval \(I\) assigned to type \(t\) is admissible precisely when there is an endpoint chore \(e\in I\) such that \(a_t(I\setminus\{e\})\ge -1/N\). The task is again to find a mass \(z\) satisfying the type-mass constraints and maximizing utilitarian welfare over PROP1-fair configurations.
This is also likely Class A. PROP1 admissibility of an interval is directly checkable from prefix sums, and the same pricing DP applies. Theorem 18’s lower-bound instance again uses only two types, so the mirror is not relying on a type count that grows with the population. The open questions include whether the \(\Theta(N)\) price is stable under arbitrary type-mass distributions, whether a better dependence on \(\tau\) is possible, and whether continuous optima admit efficient finite-\(q\) rounding with explicit denominator bounds.
The authors should recognize these as their problems: setting \(q=1\) and taking \(z\) to be a point mass recovers their original path allocation model; the relaxed object is only the population of repeated copies. The path, indivisibility, contiguity, additive disutilities, MMS/PROP1 predicates, and utilitarian objective are all retained. The configuration-mass formulation is a high-multiplicity representation of integral allocations, not a lottery over fractional chores inside one path.
The weakest point is also clear. This requires a repeated-schedule or repeated-path interpretation. It does not claim that one fixed path with a fixed inventory can support an atomless population; that limit degenerates. Nor does it cover the paper’s egalitarian theorems without further work, because mixing different type compositions across repeated paths can change a support-wise minimum welfare. Thus the positive claim is deliberately limited: Theorems 12 and 18, together with their constructive Lemmas 7 and 13, admit a credible high-multiplicity continuous mirror; the whole paper does not automatically do so.
The strongest case against the proposed mirror is that it is not actually a population continuization of the paper’s problem. It is a new product model consisting of \(q\) independent finite allocation instances, followed by convexification over their configurations.
With one fixed path, the objection is decisive: an atomless population cannot receive indivisible chores on that path. As the population grows, empty bundles dominate and the MMS and PROP1 predicates either degenerate or become undefined for agents receiving nothing. The proposed \(q\)-path repair avoids this only by scaling the resource system as well as the population. That may be sensible, but it adds an independence structure, a cohort size \(N\), and a locality convention: agents are judged only against the chores on their own path. None of these is present in the paper.
The missing convention matters for both anchors. If all \(q\) paths are pooled, an agent’s MMS benchmark is computed over \(qm\) chores with \(qN\) agents, not by substituting a type valuation into the paper’s \(N\)-agent MMS value. Contiguity also changes. If paths remain independent, then the “continuum” is only an aggregate of finite \(N\)-agent problems; \(q\) tends to infinity while the substantive fairness problem remains finite on every path. Clearing denominators shows that a rational configuration law can be realized by finitely many paths, but it does not show that this law is equivalent to the original single-path model.
This undermines Lemma 7 and Theorem 12 as continuous anchors. Lemma 7 is a finite moving-knife construction with a distinguished last agent and an MMS threshold depending on exactly \(N\) agents. The proposed LP instead asks for a new welfare optimization problem over typed path configurations. Its pricing dynamic program may well be polynomial, but that would be a new theorem about the product model, not a continuization of Lemma 7.
The claimed \(\Theta(N)\) lower bound also does not automatically survive. The construction has one exceptional type with mass \(1/N\) and one common type. The original argument assumes that every finite instance contains exactly one exceptional agent and \(N-1\) common agents. The proposed constraint
\[ \sum_{\kappa} z_\kappa r_t(\kappa)=N\mu_t \]
only imposes these counts globally. It permits exceptional agents to be concentrated in some paths and absent from others, so the lower-bound argument cannot be applied path by path. Enforcing the original composition on every path repairs the bound, but then each path is simply the original finite instance and the mass formulation is a convexified repetition rather than a population-level mirror.
The same objection applies to Lemma 13 and Theorem 18, with an additional threshold problem. PROP1 uses the finite-agent threshold \(-1/N\). If \(N\) is the number of agents per path, the threshold remains fixed while the total population grows; if \(N\) is replaced by the total population \(qN\), the predicate changes and tends toward a different, potentially vacuous notion. The paper’s endpoint-removal proof and its “last agent” argument therefore do not survive a canonical population limit. The proposed PROP1 configuration LP is again a reasonable new model, but its polynomial pricing argument and any \(\Theta(N)\) price statement would need to be proved afresh.
The proponent has correctly avoided the weaker objections: types can be complete valuation profiles, indivisibility can be preserved, and repeated maintenance schedules are a plausible high-multiplicity story. That is why the negative case is not airtight. Under a broad notion of “author-recognizable extension,” the repeated-path model is worthwhile and probably defeats a red verdict. But under the stricter population-only reading of continuization, neither pair of anchors survives unchanged: fixed-path limits degenerate, pooled limits alter MMS and PROP1, and independent repeated paths introduce a new resource/cohort model. The honest negative conclusion is therefore not that no such research problem exists, but that the paper does not itself support the claimed continuous mirror without substantial re-modelling and new results.
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.