| paper | d4-conf-aaai-2021-1250 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Lemma 6
statement extracted from the paper’s text layer
Given a finite set of job types \(T\), rational masses \(\mu_t\geq 0\) with \(\sum_{t\in T}\mu_t=1\), and rational work requirements \(k_t>0\), choose a measurable service rate \(a_t(u,s)\geq 0\) for each \(u\in[0,\mu_t]\) and time \(s\geq 0\). Require \(\sum_{t\in T}\int_0^{\mu_t}a_t(u,s)\,du\leq 1\) at every time and \(\int_0^{T_t(u)}a_t(u,s)\,ds=k_t\), where \(T_t(u)\) is that job's completion time. Minimize \(\sum_{t\in T}\int_0^{\mu_t}\log T_t(u)\,du\).
A unit-mass cohort of jobs with finitely many workload types, where \(\mu_t\) is the mass of type \(t\). The decision is a feasible service schedule for each infinitesimal job; the objective is the mass-weighted log of completion times, the continuum counterpart of the normalized finite log-product. The paper's SJF structure suggests sorting types by \(k_t\), giving type-\(t\) completion times \(T_t(u)=S_t+k_tu\), where \(S_t\) is the preceding types' total work mass.
Lemma 6 states an allocation structure without a runtime bound, and the paper says it does not address LCP complexity; the computational reading depends on treating the SJF characterization as a constructive method.
fatal: False
Covers the single-resource SJF clause of Lemma 6. It leaves the envy-freeness claims, the two-agent multi-resource case, and the paper's general multi-resource results untouched.
The paper has no named result saying an allocation problem is in \(P\), NP-hard, or belongs to another complexity class. The strongest computation-facing anchor is Lemma 6, proved in this paper. It says that for one resource, LCP serves jobs serially in increasing order of their work requirements (Shortest Job First), and the resulting allocations are envy-free in expectation; it also says LCP is envy-free in expectation with multiple resources when there are two agents. I would use only the single-resource clause. The paper’s conclusion explicitly leaves LCP’s computational complexity open, and its LCP-X simulation enumerates candidates in time polynomial in the number of resources but exponential in the number of agents.
My lead mirror is Continuous Single-Resource LCP. It has one divisible resource and a population with finite support \(T\): each type \(t\) has rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\), and a rational work requirement \(k_t>0\). A type is a job template: its members have the same amount of work. Mass is the fraction of the cohort using that template.
A schedule may serve any fractional subcohort at a time, so identical jobs can finish at different times. Formally, represent service by a measure \(\pi\) over the population and time. Each infinitesimal job \(x\) of type \(t\) receives total service \(k_t\); the time marginal of \(\pi\) is bounded by the available resource per unit time. Let \(T(x)\) be the job’s completion time. The objective is to find a feasible schedule minimizing \(\int \log T(x)\,d\mu(x)\), equivalently the mass-weighted geometric mean of completion times. A solution is the schedule, including each job’s completion time.
This is the high-multiplicity version of the paper’s one-resource LCP: for \(N\) jobs, the type masses are the fractions \(n_t/N\), and the objective is the finite product’s log divided by \(N\). Measuring time in units scaled by \(N\) normalizes the resource rate; that common time rescaling does not change which schedule minimizes the objective.
The intended regime is a large batch-processing pool with many jobs drawn from a small number \(\tau=|T|\) of exact workload templates. Members of a template remain separate jobs and may be scheduled separately; the mirror does not force an entire type to finish as one block. This is the population becoming continuous. Resource divisibility and continuous time were already present in the paper.
The mirror has a concise solution: sort the types by increasing \(k_t\). For a type \(t\) in that order, let \(S_t\) be the total work mass of the preceding types. Its jobs then have completion times \(T_t(a)=S_t+k_t a\), for \(a\in[0,\mu_t]\). This is the fluid form of SJF. The schedule has a finite description of size \(O(\tau)\), found by sorting rational work requirements and summing rational masses and workloads. I expect this restricted mirror to be Class A, tractable.
That makes a credible, narrow positive case: the authors already identify the LCP objective and prove an optimal scheduling structure for this special case, while the high-multiplicity version has a compact input and solution. It does not claim that a discrete hardness result dissolves; the paper supplies no such hardness anchor. The further question is whether useful finite descriptions survive with multiple resources and whether the paper’s general LCP structure can lead to efficient computation there.
The weak point is the restriction to one resource, where SJF gives unusually clean structure. Extending the mirror to multiple resources brings back the paper’s trade-offs between simultaneous sharing and serial completion, and its general structural theorem does not itself establish a complexity classification. A referee would also need to accept the cohort-scaled, mass-valued schedule as the right high-multiplicity form of the authors’ allocation problem.
The strongest objection is that the paper supplies no named computational result to continuize. Its conclusion says LCP’s computational complexity is not addressed. Lemma 6—the proponent’s anchor—characterizes the one-resource LCP outcome as Shortest Job First and gives an envy-freeness guarantee; it does not classify or analyze the complexity of computing a solution. Theorem 5 likewise describes the structure of LCP allocations, not an algorithm or complexity bound. The paper’s LCP-X enumeration is experimental, and the authors explicitly leave the general computation question open.
The proposed single-resource model is coherent: a large pool of jobs drawn from a few workload types is a plausible high-multiplicity regime, and mass-weighted completion costs preserve the finite objective after a common time rescaling. But that makes it a new algorithmic question built from a structural scheduling lemma, rather than a mirror of a computational result in this paper. Even the stronger one-resource formulation—allowing jobs of one type to finish at different times—has a finite description obtained from the type masses and the SJF order. That establishes a sensible fluid model; it does not supply the missing computational result in the paper.
The broader multi-resource version is the better candidate, and it is where the negative case is weakest. A pool of many jobs with a small number of exact demand-and-work templates is plausible, and completion costs do not inherently depend on job identity. Theorem 5 and the exponential dependence of LCP-X on the number of agents give a natural reason to ask whether a continuous-population formulation admits efficient computation. I cannot rule out that mirror without treating the absence of an existing complexity theorem as if it made a new, well-posed computational question worthless. So the case against the cited Lemma 6 anchor is strong; the universal claim that no worthwhile mirror exists in any scenario is not.
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.