| paper | d4-journals-jair-2016-0018 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2.4
statement extracted from the paper’s text layer
Fix a per-capita processing capacity \(b>0\). Given a finite-support rational population over job types \(\theta=(r,d,\ell,v)\), with \(\ell\in[1,\kappa]\), whose cohort masses are revealed only when they arrive, what is the optimal worst-case competitive ratio of deterministic, individually truthful and individually rational online mechanisms against a clairvoyant fluid schedule at capacity \(b\)? In particular, do the lower bounds \(5\) at \(\kappa=1\) and \(\kappa/\ln\kappa+1-o(1)\) for large \(\kappa\) persist?
A finite-support rational measure \(\mu\) over job types \((r,d,\ell,v)\) arrives in cohorts over time, with future arrivals hidden. A mechanism assigns service to cohort mass subject to fixed per-capita capacity \(b\); each individual job remains all-or-nothing for completion, and payments and truthfulness are assessed per individual. Compare its welfare \(\sum_\theta\mu_\theta v_\theta q_\theta\) with the clairvoyant optimum under the same fluid feasibility constraints.
The frontier covers the lower bounds in Theorems 2.4 and 2.5; it does not directly mirror Theorem 3.1’s truthfulness proof or the upper-bound analyses for Γ₁.
The best positive case is a fluid, high multiplicity version of online scheduling mechanism design. A plausible regime is a cloud provider serving large cohorts of standardized requests: workload template, runtime, value, and deadline window determine a request’s type. There may be millions of requests but far fewer distinct types. Capacity is measured per unit of population, as it would be in a system that scales its compute supply with demand. That co-modification is part of the mirror.
For the mirror, let each type be \(\theta=(r,d,\ell,v)\), with release time \(r\), deadline \(d\), processing requirement \(\ell\), and value \(v\). An instance has finite rational support \(T\) and masses \(\mu_\theta\) summing to \(1\). Mass is the fraction of requests in each cohort. In the resumable model, the mechanism sees cohorts arrive online and allocates service rates to their unfinished mass, subject to the normalized processor-capacity constraint. Its decision is how much mass of each type to complete by each deadline, and what to charge per completed request. Each individual’s outcome remains complete or incomplete; the fractional quantity is the amount of a cohort that receives each outcome. Utility and truthfulness remain at the individual-request level, with the paper’s report restrictions. Welfare is \(\sum_\theta \mu_\theta v_\theta q_\theta\), compared against the clairvoyant optimum under the same fluid feasibility constraints.
My lead anchor is Theorem 2.4, proved in this paper. It says that when \(\kappa=1\), so every job has equal length, no deterministic incentive-compatible online mechanism can have competitive ratio below \(5\). The result applies to both restart and resume jobs. Its continuous question is the Equal-Length Fluid IC Scheduling Frontier: over all finite-support rational populations with equal processing requirements, what is the best competitive ratio achievable by a deterministic, individually truthful online mechanism? In particular, can any such mechanism beat \(5\), or does the lower bound persist? A solution would be either a mechanism with a proved ratio below \(5\), or an impossibility proof establishing the lower bound for this fluid model.
A second anchor is Theorem 2.5, also proved here. For sufficiently large \(\kappa\), it says that no deterministic incentive-compatible online mechanism in either scheduling model can achieve a ratio below \(\kappa/\ln\kappa+1-o(1)\); more concretely, for \(\kappa\ge16\), none can achieve a ratio below \(\kappa/\ln\kappa+0.94\). Its mirror is the Bounded-Length-Range Fluid IC Scheduling Frontier: allow types with \(\ell\in[1,\kappa]\), and determine whether that asymptotic lower bound still holds for the optimal deterministic truthful online mechanism. The required result is a mechanism or a lower-bound proof for every such fluid population.
I expect the lower-bound phenomena to have a Class B-style explanation: the adversarial structure in these theorems is built from arrival times, deadlines, processing lengths, and the shadow-job argument enforcing incentives. Those features remain in the cohort model; the reductions are not driven merely by having many named agents. A repeated cohort of a type is a natural high-multiplicity input, and the paper’s cloud-computing motivation gives a plausible setting for it.
One scope caveat matters: the paper gives competitive-ratio bounds and mechanisms, not NP-hardness, membership in \(P\), or parameterized-complexity results. These anchors therefore mirror a computational question about the performance frontier of online mechanisms, not a conventional complexity classification. The proposed questions cover the deterministic truthful lower bounds for equal and bounded job lengths; they do not claim to mirror every result in the paper.
The soft spot is the fluid limit itself. The paper’s strategic object is an individual job with positive processing time. In the mirror, a type’s mass can be split, and the service supply must be scaled and interpreted per unit population. That could change the effect of a shadow job or let a mechanism smooth away a loss that is unavoidable for indivisible jobs. Individual-level truthfulness must also survive the aggregation; a model that makes an entire cohort jointly report would no longer be the paper’s problem. So I would put the two frontier questions to the authors as real mirrors, while treating persistence of the numerical bounds as open rather than claiming it follows from their proofs.
The strongest objection is that the proposed mirrors are fluid online scheduling questions, not continuous computational social choice questions. Here a type records a job’s release time, deadline, length, and value; the mechanism allocates scarce machine time against an adversarial future stream. There are no preferences over collective outcomes and no voting rule. The paper’s named results concern competitive ratios against a clairvoyant scheduler, not the complexity of computing a social choice rule. That makes them a poor fit for ChoCo’s stated complexity landscape.
Theorem 2.4’s lower bound of \(5\) comes from unit jobs that compete for one machine, with the shadow job argument forcing a particular indivisible completion. Replicating those jobs as a high multiplicity cohort while keeping one machine fixed drives the completed population fraction toward zero. Scaling capacity with population avoids that degeneracy, but changes the object into parallel or fluid scheduling: the mechanism can serve fractions of a cohort, and the paper’s argument no longer establishes a bound for it. The more careful fluid frontier the proponent proposes could still be asked, but it would be a new competitive analysis problem in online scheduling.
Theorem 2.5 has the same limitation. Its adversary releases jobs at specific times in response to the mechanism’s choices; those release times make the jobs distinct types. A known distribution over all types would disclose future arrivals, while an unknown sequence of arriving masses preserves the online problem but no longer mirrors the paper’s single machine and indivisible jobs. Replicating each arrival into a cohort retains the timing pattern, but fractional service changes how the mechanism can hedge. The shadow job proof therefore does not carry over. Again, a fluid competitive ratio frontier is conceivable; it is not the complexity question these theorems answered.
There is an established neighboring research home for that reformulation: for example, Carroll and Grosu study incentive compatible online scheduling of malleable jobs on parallel systems, with individual deadlines and values. That is evidence of a related mechanism design literature, not evidence that the proposed fluid frontier has already been solved. [Carroll and Grosu, “Incentive Compatible Online Scheduling of Malleable Parallel Jobs with Individual Deadlines”](https://doi.org/10.1109/ICPP.2010.60)
So I can make a case against these as ChoCo anchors: their closest defensible mirrors change the subject to fluid online scheduling and competitive analysis. I cannot honestly defend the stronger universal claim that no worthwhile mirror exists in any scenario. A cohort based model with per capita capacity and individual level truthfulness is plausible, and its optimal competitive ratio could be a worthwhile question for scheduling researchers. The negative case is weak precisely there: it establishes a programme boundary, not that the improved question is unworthy.
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.