| paper | d4-conf-aaai-2021-0464 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Theorem 2 is a computational mechanism result: it proves a particular randomized allocation mechanism truthful in expectation. The proposed configuration model gives a coherent continuous scheduling optimization problem, but it does not formulate a mechanism or preserve that incentive guarantee; the proponent explicitly sets truthfulness aside. It is a plausible extension of the scheduling subproblem, not a continuous analogue of the anchored result.
fails bit b-changes — the continuum limit changes the question
The candidate covers aggregate makespan scheduling with machine types and integral job configurations, but leaves out Theorem 2’s truthful-in-expectation guarantee.
The strongest mirror I see is the restricted-related machine result, Theorem 2. It is proved in this paper. The theorem says that the paper’s randomized \(VCGmon_\mu\) mechanism is truthful in expectation when each machine’s multidimensional private type consists of its speed and the set of jobs it can process. The mechanism uses the fractional scheduling LP and randomized rounding described in the paper; that construction runs in polynomial time and gives a makespan at most twice the fractional optimum. The theorem establishes the truthfulness claim; the paper’s rounding analysis supplies the approximation guarantee.
A natural high-multiplicity setting is a large cloud or compute fleet. Many hosts share the same speed and the same compatibility with workload classes, so there are \(N\) machines but only \(\tau\) distinct machine types, with \(\tau \ll N\). A type \(t\) is the complete pair \((s_t,A_t)\): speed \(s_t\) and eligible job classes \(A_t\). Workloads also arrive in recurring classes with public processing times. Their supplies scale with fleet size. This scaling is part of the mirror: a finite fleet of \(N\) machines has \(N\mu_t\) hosts of type \(t\) and, say, \(Nd_j\) jobs of class \(j\).
Call the continuous problem Mass Restricted-Related Scheduling. An instance gives finitely many machine types with masses \(\mu_t\ge 0\), \(\sum_t\mu_t=1\); job classes \(j=1,\ldots,q\), processing times \(p_j>0\), and rational demands \(d_j\) per unit of machine population. A machine of type \(t\) can process class \(j\) only if \(j\in A_t\), and its load from \(k_j\) such jobs is \(p_jk_j/s_t\).
A configuration \(k\in\mathbb Z_{\ge0}^q\) is the integral bundle of job classes assigned to one machine; it must use only classes eligible for that machine type. Choose masses \(x_{t,k}\ge0\), where \(x_{t,k}\) is the fraction of the fleet of type \(t\) assigned configuration \(k\). They must satisfy
\[
\sum_k x_{t,k}=\mu_t \quad\text{for each }t,
\qquad
\sum_{t,k}x_{t,k}k_j=d_j \quad\text{for each }j.
\]
The question is to minimize the largest load \(\sum_j p_jk_j/s_t\) among configurations given positive mass. A solution is that minimum makespan and a mass allocation attaining it. Thus each machine still gets an integral bundle; only the number of indistinguishable machines assigned to each bundle becomes fractional.
I expect the unrestricted problem to retain hardness from the packing and eligibility choices among job classes: fractional machine counts do not make an individual machine’s bundle fractional. At a fixed makespan, the model has potentially exponentially many configurations, and finding a high-value configuration for a pricing step resembles a knapsack problem. That suggests a Class B direction, with the relevant combinatorics in job classes and sizes rather than population multiplicity. It is a research prediction, not a hardness result established by Theorem 2; a reduction must show that fractional machine mass does not erase the discrete gap.
This mirror covers the scheduling allocation problem underlying Theorem 2, not the paper’s full mechanism-design claim. Whether a useful truthfulness guarantee survives in a model whose input is a type distribution is a separate question: an infinitesimal host has no individual impact on the aggregate report. The mirror also generates concrete questions about exact configuration pricing, approximation algorithms, and the relation between a rational mass solution and finite schedules as \(N\) grows.
The weak point is that the theorem itself concerns named finite machines and a mechanism, while the proposed mirror co-scales recurring workload demand and asks for an aggregate scheduling optimum. That is a substantive modeling step. I think it is defensible because the continuous object is the machine population, machine types preserve the paper’s private capabilities, and hosts still receive integral job bundles. But the theorem’s truthfulness result does not automatically transfer to the mass problem.
Theorem 2’s distinctive result is about incentives for individual machines. A machine has a private speed and eligibility set, receives an assignment, and can compare truthful reporting with a unilateral lie while every other machine’s report stays fixed. Its proof uses that individual report in the fractional schedule and in the expected-utility calculation.
In a continuum population, a single machine has zero mass. Changing its report leaves the aggregate schedule unchanged, and the mass allocation specifies assignments only up to sets of measure zero. It therefore does not determine what that machine receives after reporting a type outside the population’s support, or how the mechanism should treat an exceptional machine while preserving individual feasibility. The \(VCGmon_\mu\) truthfulness proof does not transfer. Keeping each machine’s mass positive restores the paper’s finite-agent incentive problem, rather than answering it in the continuous model.
That objection does not defeat the proponent’s stronger configuration model. With job demand scaled per unit of machine mass, its variables \(x_{t,k}\) define a coherent high-multiplicity scheduling problem: each machine still receives an integral configuration, while the mass assigned to each configuration is fractional. Exact optimization, pricing, and approximation for that LP are genuine computational questions. They concern aggregate scheduling, though, and do not preserve Theorem 2’s central truthful-in-expectation claim.
So the negative case is weak against the anchor as stated. I can argue that the configuration LP is a different question from the theorem’s incentive result, but I cannot honestly argue that it is an unworthy continuous question. If a mirror of the underlying scheduling problem counts, this anchor survives.
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.