| paper | d4-conf-atal-2020-0092 |
| 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→P discrete result → its continuous mirror
Answer: Exactly polynomial-time solvable, with bit complexity \(\bigl(m\tau^2(L+1)\bigr)^{O(1)}\); the numerical horizon \(H\) enters only through its binary encoding in \(L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite horizon \(H\), resource capacities per capita \(a_r\), and a deterministic known stream of cohorts with rational masses \(\mu_{t,k}\) and task attributes \((v_k,d_k,q_k)\), find a welfare-maximizing feasible schedule. Choose accepted mass \(x_{t,k}\) with \(0 \le x_{t,k} \le \mu_{t,k}\), set \(x_{t,k}=0\) when the task cannot finish by \(H+1\), and require \(\sum_{(t,k):\,t \le u < t+d_k} q_{k,r}x_{t,k} \le a_r\) for every resource \(r\) and time \(u\). Maximize \(\sum_{t,k} v_k x_{t,k}\), with each individual task receiving its full requested bundle or being rejected.
A continuous population of task owners grouped by arrival period and shared value, duration, and resource requirements; the decision variable \(x_{t,k}\) is the accepted mass of each cohort, the objective is total accepted value, and active-task resource use is bounded by per-capita capacity.
Theorem 1’s knapsack reduction gives tasks distinct arrival times, so its hard instance does not itself compress into a small-support cohort instance; this limits what the mirror covers.
fatal: False
The mirror covers deterministic known-stream welfare maximization from Theorem 1 in a batched high-multiplicity regime. It leaves aside unknown-arrival learning, SP-RL’s strategyproofness and payment guarantees, and the experimental performance results.
My lead is Fluid Known-Stream Welfare Maximization, a continuous mirror of the allocation problem underlying Theorem 1. The theorem is proved in this paper: finding a policy that maximizes expected total task value subject to the resource and completion constraints is NP-hard. The paper proves this by reducing from 0–1 knapsack, and its hardness holds even for a deterministic task stream known in advance.
A plausible high-multiplicity regime is an edge-cloud provider serving many task owners over a day. In each scheduling period, many owners may submit tasks with the same value, duration, and resource requirements: for example, requests from the same service tier running the same workload. Let a complete type be \((t,v,d,q)\), including arrival period \(t\), value \(v\), duration \(d\), and resource vector \(q\). Including \(t\) matters because otherwise identical tasks arriving at different times face different remaining capacity. Suppose the population has normalized mass \(\mu_{t,k}\) in each supported type \(k\), with rational masses and support size \(\tau\). The number of task owners can be very large while the number of distinct time-and-task profiles remains much smaller.
The continuous problem is: given an explicit horizon \(H\), resource capacities per capita \(a_r\), and a deterministic known stream of type masses \(\mu_{t,k}\), find an optimal accepted-mass schedule \(x_{t,k}\). Require \(0\le x_{t,k}\le\mu_{t,k}\), and set \(x_{t,k}=0\) if a task starting at \(t\) cannot finish by \(H+1\). For every resource \(r\) and time \(u\), impose
\[
\sum_{(t,k):\,t\le u<t+d_k} q_{k,r}x_{t,k}\le a_r.
\]
Maximize
\[
\sum_{t,k} v_k x_{t,k}.
\]
A solution is the accepted mass for each cohort. Each individual task still receives its full requested bundle or is rejected; \(x_{t,k}\) specifies the measure of the cohort selected for service. The instance’s task stream and capacities are given as binary rationals, and the question is to return an optimal schedule.
This mirror should be tractable: it is a linear program with \(\tau\) variables and \(O(H|R|+\tau)\) constraints, so it can be solved in time polynomial in the explicit horizon, number of resources, support size, and input bit length. The knapsack choice of whether to accept each individual item has become a choice of how much mass of each type to accept. That makes this a credible Class A outcome for the deterministic known-stream case of Theorem 1.
I would keep the scope narrow. This mirrors the paper’s welfare-maximizing allocation problem in the known-stream regime; it does not mirror the unknown-arrival learning problem or the paper’s strategyproof payment guarantees. A natural next question is how well an optimal continuous schedule can be rounded or implemented with finitely many agents, with bounds in terms of population size and support. Other questions include whether a continuous online policy remains efficiently computable under unknown arrival distributions, and whether cohort-level allocation can be combined with truthful reporting and critical payments.
The weakest point is that the paper’s setting has one task arriving at each discrete time, while this mirror groups many arrivals into cohorts and permits a selected fraction of a cohort to be served. It therefore changes the unit of the allocation decision. But it keeps the task attributes, temporal resource occupancy, completion limits, and social-welfare objective from Theorem 1, and it targets precisely the deterministic known-arrival case that the paper uses to establish hardness. That makes it a defensible mirror of a substantial underlying problem, even though it does not cover the full SP-RL contribution.
Theorem 1 is a real obstacle to a negative verdict: it is a named computational result, and the known-stream knapsack case is a plausible target for a fluid model. Many similar requests arriving in the same scheduling period could be grouped by period, value, duration, and resource needs. Allocating accepted mass then gives a coherent interval-packing LP. I can’t honestly rule out that scenario.
The strongest objection is that the LP needs a different arrival model. In the paper, one task arrives at each time step, and the mechanism decides before seeing the next task. In the knapsack reduction, each item is encoded at its own time step. If time remains part of a complete type, those arrivals are singleton types; the support grows with the number of tasks, so the type grouping does not compress the hard instance. To obtain positive mass per type, the mirror must allow batches of similar tasks at a scheduling time and let the provider select an arbitrary fraction of each batch. That is a sensible extension of cloud allocation, but it replaces the paper’s sequential decisions with cohort-level planning.
The stronger version could retain online arrivals by modelling mass flows across several periods. Yet with known flows, it again studies planning with advance knowledge of future mass. With unknown flows, population continuity does not remove uncertainty about future arrivals, so the learning problem remains. And in an atomless model, a single task owner has no effect on aggregate capacity; preserving the paper’s individual strategyproofness claims would require additional semantics for how a selected fraction of a cohort is allocated and paid.
That leaves a respectable Class A mirror of a deterministic, batched welfare-planning extension. It does not establish that the extension is unworthy; a cloud provider might well recognize it as useful. The negative case is therefore weak at its decisive point: it shows a gap between the paper’s sequential mechanism and the proposed cohort LP, but it cannot show that the cohort regime is implausible or that its computational question is not worth studying.
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.