| paper | d4-journals-jair-2013-0025 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Such a DSIC mechanism exists, with exact computation polynomial in \(H,\tau,K,L\) and the guarantee \(W_{\mathrm{online}}\ge\tfrac12W_{\mathrm{offline}}\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
For a finite horizon \(H\), a stream of rational masses over a support of vehicle types, and per-capita supply revealed each period, can an on-departure mass mechanism allocate integral charging bundles to individuals, preserve dominant-strategy truthfulness under the paper’s limited-misreport assumptions, achieve \(W_{\mathrm{online}}\ge \tfrac12 W_{\mathrm{offline}}\), and compute its allocations and threshold payments in time polynomial in \(H,\tau,K,L\)?
Types specify identical marginal values, arrival and departure windows, and rate caps; the state tracks each type’s mass by endowment, allocation splits mass across integral individual bundles, and threshold payments implement truthful reporting while the objective is online welfare against the full-information offline optimum.
Theorem 6 gives a competitive guarantee, not a complexity classification, and weighted cohort simulation may make the continuous algorithm straightforward; the remaining result could be a technical lift more than a broad complexity landscape.
fatal: False
The mirror covers the on-departure welfare guarantee of Theorem 6 and the cancellation bound of Theorem 5; it leaves the immediate-cancellation bounds of Theorems 3–4 and the empirical results outside scope.
The strongest honest mirror is the paper’s on-departure (OD) mechanism in a large managed fleet of plug-in hybrid vehicles. The fleet might have thousands of vehicles but only a modest number \(\tau\) of recurring types: each type has the same marginal fuel savings, arrival and departure window, and maximum charging rate. Those details define the type; mass \(\mu_\theta\) is the share of vehicles of type \(\theta\). Hourly charging capacity is given per vehicle, so total supply scales with fleet size. A type’s mass can be split across service schedules, while each individual vehicle still receives integral charging units.
Here is the lead question, OD-Mass-Efficiency. An instance is a finite horizon \(H\), a stream of arriving type masses \(\mu_\theta\) with binary-rational values and arrival/departure windows, and per-capita supply \(\sigma_h\) revealed each period. Each type has a non-increasing marginal value vector \(v_{\theta,1}\ge\cdots\ge v_{\theta,K}\) and a per-period rate cap \(r_\theta\). The task is to compute a causal direct mechanism: at each period it assigns supply among active vehicle mass without seeing future arrivals or supply, and at departure it may cancel provisional units. Allocations to individuals remain integral; only the shares assigned to identical individuals are fractional. Per-unit threshold payments must make truthful reporting a dominant strategy for an individual vehicle, subject to the paper’s limited-misreport assumptions. The welfare target is at least half the offline optimum that knows the whole stream.
Theorem 6, proved in this paper, is the anchor: with non-increasing marginal values, the OD mechanism is 2-competitive with the optimal offline allocation. In the mass version, the precise question is whether a causal, truthful type-mass mechanism can guarantee \(W_{\mathrm{online}}\ge \tfrac12 W_{\mathrm{offline}}\) for every rational input stream, and whether its decisions and payments can be computed in time polynomial in \(H,\tau,K\), and the input bit length \(L\). I expect a Class A answer: weighted order statistics and type-level state tracking look compatible with a polynomial algorithm. The paper does not prove that compression or the continuum guarantee, so this is a research question, not a result transferred for free.
A second, narrower question is OD-Mass-Cancellation. Given the same kind of stream and a target type, compute its provisional and retained mass of units under OD cancellation; across all valid streams, determine the tight supremum of the canceled fraction. Theorem 5, also proved here, says that the worst-case cancellation ratio is exactly \(\tfrac12\): no agent loses more than half its provisional units, and the bound is tight. For the mass mirror, the target is the same bound for the aggregate mass of identical vehicles. Replicating the paper’s tight finite witness with positive rational masses makes that target plausible. This is a structural bound rather than a complexity-class result; I expect it to remain tractable to establish.
These are approximation and structural anchors, not NP-hardness or \(P\)/FPT classifications: the paper gives no named result of those kinds. Theorem 2’s DSIC result supplies useful finite-agent context, but the main anchors here are Theorems 6 and 5. The scope is OD welfare and cancellation behavior; it does not extend to the immediate-cancellation bounds of Theorems 3–4 or claim to cover the paper’s empirical results.
This is a plausible author-recognizable mirror because it keeps their core computational question: how to allocate a perishable resource online among agents with multi-unit, non-increasing demand, while preserving incentives. The paper itself studies PHEV charging and constrained neighborhood supply. The fleet regime simply makes high multiplicity and a small support explicit. This continuizes the population: time remains discrete, charging units remain integral for each vehicle, and the decision is still a mechanism.
The soft spot is the incentive model. In an atomless population, a single vehicle has zero mass and cannot change aggregate prices; dominant-strategy truthfulness for that individual is therefore a price-taking condition. That is not identical to the finite-agent externality calculation in the paper, and positive-mass coalitions could behave differently. The 2-competitive charging argument also needs to be lifted from individual units to a measure argument, and its price and allocation computations need an exact bit-complexity analysis. Those are real obligations—but they leave a coherent, narrow continuous question that retains the paper’s problem rather than replacing it.
The best case against these anchors is that they are a poor fit for ChoCo’s main deliverable: a complexity landscape for computational problems on continuous societies. Theorem 6 proves a competitive ratio for a particular online mechanism; it does not classify the complexity of an underlying problem. The paper already gives an implementation bound for OD. In a mass model, one can track each type’s mass by its current endowment and replace counts with weighted order statistics. That makes the proposed polynomial-time question plausible, but also makes it look like a fluid implementation of the existing algorithm rather than a new complexity landscape.
That objection has limits. A fluid implementation still raises real questions about exact computation, causal decisions, and individual incentives. And the proposed fleet scenario is credible: many similar vehicles can share values, charging rates, and time windows. The fact that the paper’s actual data are heterogeneous does not rule out that regime.
Theorem 5 is a weaker independent anchor. It bounds cancellations for each agent; summing those bounds over a cohort gives the same bound for its mass, and scaling the paper’s tight witness gives tightness. That is a short structural extension, not a computational classification. It adds little as a separate ChoCo question, though the programme’s rules mean that an easy or already-known answer alone cannot disqualify a well-posed mirror.
The stronger possible objection is that the online mechanism depends on each vehicle’s history of allocations, so a mass model must track how each cohort splits across endowment states. But those states are finite when demand is bounded, and random selection within a type can preserve integral bundles for individual vehicles. This is a modelling obligation, not a fundamental barrier.
So the negative case is honest but weak against the universal claim. Theorem 5 is not a compelling computational anchor, and Theorem 6 is outside ChoCo’s central style of complexity result; neither establishes that the mirror is worthless. A large, repetitive fleet gives the proponent a sensible continuous-population model, and I cannot rule out a worthwhile question about computing its truthful online allocations.
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.