| paper | d4-conf-aaai-2017-0715 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given an ordered sequence of \(\tau\) cohorts with binary-rational masses \(\mu_i\) summing to \(1\), each cohort consists of individually strategic members sharing a complete reservation type \(\theta_i=(a_i,d_i,t_i,c_i,v_i)\), including its arrival stage; future cohorts are hidden. With normalized capacity \(B\), request densities \(\rho_i=v_i/(c_it_i)\in[1,k]\), and lengths \(t_i\in[1,T]\), each member must receive either a complete reservation or none. What is the supremal worst-case expected social-welfare competitive ratio achievable by a randomized, individually truthful online policy that chooses accepted mass and feasible start times as each cohort arrives, compared with the offline optimum for the same cohort sequence?
Online admission and scheduling over an ordered, finite-support distribution of complete reservation types. Cohort mass is the population decision variable, accepted members receive whole reservations, capacity scales per unit population mass, and members pay per-member prices under individual truthfulness.
Revealing a cohort together changes the paper's request-by-request decision process; within a cohort, a policy cannot adapt separately to each member's arrival and prior allocation.
fatal: False
Covers Theorem 5's general welfare competitive upper bound as a frontier question, and Theorem 4's Binary-Filter welfare and revenue guarantees as an algorithmic benchmark. It leaves Theorems 1–3, Theorem 2's bounded-request guarantee, and other results outside the proposed mirror.
The strongest mirror is online reservation admission for a fluid population of cloud users. A mass element represents a customer who still requests a complete reservation: accepting mass \(x\) from a cohort means serving that fraction of its members, each with their full requested reservation. It does not mean dividing an individual customer’s reservation into fractional machines or time.
Concretely, take a known total population mass of \(1\), arriving in an ordered sequence of cohorts. Cohort \(i\) has binary-rational mass \(\mu_i\), with \(\sum_i\mu_i=1\), and request type \(\theta_i=(a_i,d_i,t_i,c_i,v_i)\), including its arrival stage. Normalize resource supply and requests per unit population mass. A mechanism sees each cohort only when it arrives and must immediately and irrevocably choose what mass to accept and when to schedule it. If \(\nu_i\) is the measure of accepted mass over feasible start times, then \(\nu_i([a_i,d_i-t_i])\leq\mu_i\), and feasibility requires
\[
\sum_i c_i\,\nu_i\bigl(\{s:z\in[s,s+t_i)\}\bigr)\leq B
\]
at every time \(z\), where \(B\) is normalized capacity. Each served member pays a per-member price; truthfulness means an individual member maximizes utility by reporting their request and value honestly. The offline welfare benchmark sees the whole cohort sequence and maximizes \(\sum_i v_i\nu_i([a_i,d_i-t_i])\).
A plausible regime is a large cloud or internal compute pool serving many recurring jobs from a few standardized profiles: the same reservation window, duration, resource demand, and value recur across many users. Here the population size \(N\) can greatly exceed the number \(\tau\) of cohort types, with resource supply scaling alongside the population. The aggregate action is fractional because it selects a fraction of a cohort; every selected user still receives a complete reservation. That keeps the paper’s admission, scheduling, and online-information problem intact.
My lead is Fluid Online Reservation Competitive Frontier. Its anchor is Theorem 5, proved in this paper: for general \(k\) and \(T\), no randomized mechanism can achieve a social-welfare competitive ratio better than \(2/\log_2(8kT)\). The continuous question is: for the cohort model above, with value densities \(\rho_i=v_i/(c_it_i)\in[1,k]\) and lengths \(t_i\in[1,T]\), what is the supremal worst-case welfare ratio over randomized truthful online mechanisms, against the offline fluid optimum? A solution would give a policy and guarantee, and an upper-bound argument showing whether any better guarantee is possible. Theorem 5’s exact statement is an impossibility bound for the discrete online problem; I would not assume that its numerical bound carries over. In the fluid version, the question is whether that barrier survives when the mechanism can serve part of a cohort.
A useful second anchor is Theorem 4, proved in this paper. It establishes that Binary-Filter is truthful and achieves competitive ratio \(1/(42\lceil\log_2 k\rceil\lceil\log_2 T\rceil)\) for both social welfare and provider revenue. Its continuous counterpart asks for a truthful randomized online policy that accepts cohort mass and schedules it feasibly while attaining those same two guarantees against the respective offline benchmarks. A policy and proof would count as a solution. The theorem makes this a particularly recognizable mirror: it concerns the same reservation parameters, immediate decisions, unknown future demand, and welfare and revenue objectives, while the population is the object being aggregated.
I expect the constructive question behind Theorem 4 to be Class A: fractional cohort scheduling seems amenable to online primal-dual or related continuous-optimization methods, with computation parameterized by \(\tau\), the horizon representation, and input bit length \(L\). For the frontier question behind Theorem 5, I also expect the fluid version to admit stronger guarantees than its discrete counterpart; whether its *exact* frontier is tractable is an additional question. Both problems should ask how the answer changes with \(\tau\), \(L\), the horizon, and the scaling of per-capita capacity. In particular, does requiring truthfulness lower the best fluid ratio, and can a discrete-to-fluid comparison quantify how quickly any gap closes as cohort sizes grow?
The scope here is Theorems 4 and 5: the paper’s online welfare and revenue guarantees, and its general randomized welfare upper bound. I would not claim this covers every result in the paper. Nor is Theorem 5 a conventional NP-hardness theorem; its anchor is a competitive-ratio impossibility bound, so this is a somewhat less direct fit to a programme focused on complexity classes and optimization algorithms.
That is also the main weakness. Theorem 5’s Yao construction uses a short sequence of bundles with very large individual requests. It does not itself exhibit the \(N\gg\tau\) regime, and accepting only a fraction of a cohort may defeat the construction’s discrete tradeoffs. That weakens the case that the *bound* transfers, but not the case for asking the continuous problem: it makes the paper’s own online reservation problem a concrete test of whether a discrete competitive barrier dissolves when the society is represented by mass. The paper’s authors should recognize that as a mirror of their problem, even if the fluid answer turns out to be substantially better.
The strongest objection is that the paper’s hard object is the ordered stream of arrivals, while ChoCo’s continuous society is a distribution over a finite set of complete types. Here a complete online type would have to include not just \((a,d,t,c,v)\), but when the request is revealed: its position in the sequence changes what the mechanism knows and what capacity remains. If arrival stage is part of the type, a faithful instance can have essentially one type per arrival, so the support need not be small. If it is left out, the type no longer captures everything the problem uses.
That tension weakens Theorem 4 as an anchor. Run Binary-Filter on individual requests and the paper’s question and guarantee remain, but there is no population compression. Allowing a mechanism to accept an arbitrary fraction of a cohort instead creates a batch online scheduling problem: the mechanism sees a group together and can split it across start times. That is a reasonable cloud model, but it is a material change to the paper’s one-by-one, immediate decisions. And mass allocation alone does not specify truthfulness or revenue; those require individual-level allocation probabilities and payments for members of a cohort. The stated cohort guarantee is therefore not yet a mirror of Theorem 4’s mechanism-design result.
Theorem 5 has the same problem in sharper form. Its Yao construction exploits a sequence of revealed bundles, with later bundles blocking earlier choices. A fluid cohort can be split, potentially removing that tradeoff. To retain the original sequence uncertainty, one must preserve the arrival stages—and thus the potentially large support. To keep a compact set of types, one must batch arrivals or otherwise simplify the online information structure. The proposed “does the barrier survive?” question is coherent, but it asks about a new batch-fluid online problem, not the continuous-population version of the paper’s adversarial stream.
A stronger mirror would ask for the optimal competitive frontier of truthful mechanisms for recurring, standardized jobs arriving in a small number of large cohorts, with capacity scaled to population. That is plausible, and I cannot rule out the authors recognizing it as useful. But its central difficulty is online packing and incentive design; the population continuum mainly supplies divisible cohort decisions. The case against is therefore one of fit and leverage: unlike a static society over a small support, arrival order resists aggregation, and the clean aggregated model changes the feature that drives both anchors.
I can’t honestly make the universal negative airtight. The recurring-cohort scenario is a credible mirror, and a result about its competitive frontier could be worthwhile. The negative case is strongest against treating Theorems 4 and 5 as ready-made anchors for ChoCo; it is weak against the claim that no useful continuous version exists in any scenario.
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.