| paper | d4-conf-aaai-2017-0329 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 8
statement extracted from the paper’s text layer
Given a finite set of types \(T\), rational type masses \(\mu_t\) summing to \(1\), rational per-capita chore supplies \(q_j\), and nonnegative additive burdens \(a_{tj}\), define \(b_t=\min_{\pi}\max_{B:\pi_B>0} a_t\cdot B\), where \(\pi\) ranges over finite-support distributions on integral bundles \(B\in\mathbb{Z}_{\ge0}^{J}\) with \(\sum_B\pi_B=1\) and \(\sum_B\pi_B B=q\). Determine whether there is a finite-support mass assignment \(x_{t,B}\ge0\) with \(\sum_Bx_{t,B}=\mu_t\), \(\sum_{t,B}B_jx_{t,B}=q_j\) for every chore category \(j\), and \(x_{t,B}>0\) only if \(a_t\cdot B\le b_t\); if so, output such an assignment, and otherwise report infeasibility.
A configuration-feasibility problem over a continuum of offices with finitely many complete burden types: the variables \(x_{t,B}\) give mass of type \(t\) receiving integral bundle \(B\), columns are restricted by each type’s limiting MmS bound \(b_t\), and the constraints conserve type mass and per-capita chore supply. The objective is feasibility and construction of an exact MmS allocation.
The mirror covers the exact MmS allocation computation anchored by Proposition 8; it leaves the non-existence result in Proposition 6, the approximation guarantee in Theorem 9, the PTAS in Corollary 18, and the SCHED experiments outside its scope.
The strongest mirror is an exact max-min-share allocation for a large cohort receiving repeated kinds of indivisible chores. Think of a large network of facilities or local offices assigned recurring work orders. Each office has one of a small number of complete burden profiles: offices of type \(t\) have the same disutility \(a_{tj}\) for every chore category \(j\). Let \(\mu_t\) be the fraction of offices of type \(t\), and \(q_j\) the number of chores of category \(j\) per office on average. The number of offices is large, while the number of types and the chore catalogue are comparatively small.
Each office still receives an integral bundle of chores. Continuity enters only because a fraction of a type can receive each bundle. Let \(B\in\mathbb{Z}_{\ge0}^{J}\) describe an office’s bundle, with burden \(a_t\cdot B\). Define type \(t\)’s continuous MmS burden \(b_t\) as the least possible worst burden when the per-capita chore supply \(q\) is distributed among a unit mass of identical dividers:
\[ b_t=\min_{\pi}\ \max_{B:\pi_B>0} a_t\cdot B \quad\text{subject to}\quad \sum_B \pi_B=1,\qquad \sum_B \pi_B B=q, \]
where \(\pi\) is a finite-support distribution over integral bundles. This is the large-population limit of the finite MmS benchmark: \(nq_j\) chores of category \(j\) are divided into \(n\) bundles, then \(n\) grows along values making the supplies integral.
My lead question is Continuous Cohort MmS Allocation. Given rational \(\mu_t,q_j,a_{tj}\), compute an exact MmS allocation if one exists, or report that none exists. A solution is a finite set of nonnegative masses \(x_{t,B}\) such that
\[ \sum_B x_{t,B}=\mu_t,\qquad \sum_{t,B}B_jx_{t,B}=q_j, \]
and \(x_{t,B}>0\) only when \(a_t\cdot B\le b_t\). Thus every office gets a whole bundle, every type receives its population share, and every chore is assigned.
The anchor is Proposition 8, proved in this paper: computing an MmS allocation for chores, if one exists, is strongly NP-hard, and is weakly NP-hard even for two agents. The paper says the reduction is straightforward from Integer Partition and uses an instance in which all agents have the same utility function. My mirror asks whether that hardness survives when the agents are represented by masses of repeated types and chores come from a repeated catalogue. It keeps the paper’s underlying allocation problem and its individual-level indivisibility; it does not turn chores into divisible outcomes or replace MmS with an average-welfare objective.
For the general version, I expect continuum-specific hardness may remain. A configuration LP over the possible integral bundles has pricing questions of the form “which integer bundle best fits these chore prices under a type’s burden limit?” With the chore catalogue as part of the input, that can retain substantial combinatorics even though the population itself is continuous. A useful boundary question is whether the problem becomes tractable for fixed numbers of agent and chore types, and what happens when per-capita supplies are binary encoded. Natural extensions include finding the best common approximation ratio \(\lambda\), and determining how quickly the finite-\(n\) MmS guarantees converge to \(b_t\).
The authors should recognize the core question: assign indivisible chores among agents with additive negative utilities so each agent meets their max-min-share guarantee. The regime gives that problem a credible high-multiplicity setting: many interchangeable offices, few complete burden profiles, and repeated work orders.
The weakest point is that Proposition 8’s hardness may rely on the finite instance’s item structure in a way that does not survive this limit. In particular, a single repeated chore catalogue rules out reductions that depend on every chore being a unique category. That is a substantive test for the mirror, not a reason to abandon it: the question of whether the hardness dissolves is precisely what the continuous version would let us ask.
The strongest case against Proposition 8 as an anchor is a regime mismatch. Its reduction is about the combinatorics of indivisible chores, not a large population: the paper notes hardness even with two agents and identical utility functions. If we hold a one-off chore stock fixed while the number of agents grows, the per-capita supply tends to zero. Almost all the population receives nothing, while the finite chores go to a vanishing fraction of agents; the mass model loses those recipients. The limiting benchmark can also be discontinuous: with one positive-cost chore and supply \(1/n\), the finite MMS burden stays positive, but at supply zero the continuous benchmark is zero.
That objection does not defeat the proponent’s better model. Scaling a repeated chore catalogue with the cohort keeps per-capita supply positive, and the programme explicitly allows that kind of co-modification. The proposed \(b_t\) then captures the limiting finite MMS benchmark: finite partitions give distributions over integral bundles, and rational finite-support distributions can be lifted to sufficiently large finite cohorts. The allocation still gives each agent an integral bundle. Repeated work orders and a small set of recurring burden profiles are plausible enough that the authors could recognize this as their problem.
So the reduction’s reliance on chore structure weakens any claim that the mirror will explain the paper’s hardness through population multiplicity, but that is not a reason to reject the computational question. I cannot honestly defeat this anchor. My negative case is weak: the static-stock limit is degenerate, but the recurring-cohort version avoids that problem and remains a worthwhile mirror.
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.