| paper | d4-conf-ijcai-2016-0374 |
| 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: Polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite horizon, a rational price-scenario tree, \(K\) candidate rational threshold pairs, and a binary-rational distribution \(\mu\) over finitely many complete EV types, choose the pair that maximizes expected social welfare under Algorithm 1 and output each type's per-vehicle schedule and transfers from Theorem 1. Types within each cohort share public parking and battery parameters and differ privately only in discharge cost \(c\). Require dominant-strategy truthfulness for unilateral zero-mass reports, which leave \(\mu\) and the selected pair unchanged; determine the running time in the horizon, scenario-tree size, support size \(\tau\), \(K\), and input bit length \(L\).
A distribution \(\mu\) over atomless EV owners grouped by complete type; Algorithm 1 assigns each reported type a per-vehicle schedule, aggregate flow is \(\bar r_t=\sum_\theta \mu_\theta r_{\theta,t}\), and welfare combines grid costs on \(\bar r_t\) with mass-weighted battery degradation. A threshold pair is selected from the finite candidate set using \(\mu\), and transfers are computed per vehicle using Theorem 1.
Theorem 2 covers a fixed threshold pair, while welfare-based threshold selection could depend on reported costs and disrupt truthfulness in an atomic population; the continuous formulation must make explicit that a single agent's report leaves the selector unchanged.
fatal: False
The mirror covers Algorithm 1's cost-monotonicity guarantee and its use with Theorem 1's transfers. It leaves the globally optimal online scheduling problem, Algorithms 2 and 3, and the experimental results unclassified.
A credible mirror exists for the paper’s cost-monotonicity result, in a large workplace or fleet car park. Imagine thousands of EVs arriving each day, with a modest number \(\tau\) of recurring cohorts. Within a cohort, vehicles share the same arrival and departure window, charge target, battery limits, and charging rates; the private attribute that varies is the owner’s discharge cost. Those parameters define a complete type. The cohort’s mass is its fraction of the fleet, given as a binary rational. This is a plausible high-multiplicity regime: the number of vehicles is large relative to the number of distinct types. It does not require treating merely similar costs as equal; any cost categories must be genuine shared types in the model.
My anchor is Theorem 2, proved in this paper. It says that Algorithm 1 is monotone in the discharge-cost parameter when the capacity loss per unit charge is constant and independent of charging speed and state of charge: if \(c_i\ge c'_i\), then the higher-cost type receives no more work, \(W_i(f_i(\theta_i))\le W_i(f_i(\theta'_i))\). This is a mechanism-design result, not a P-versus-NP result. The paper does not give a numbered theorem classifying the complexity of its global scheduling problem.
The continuous question I would hand to a prover is Mass Threshold V2G Tuning. An instance consists of a finite horizon of time slots; a finite price path, or a finite price-scenario tree; candidate rational charging and discharging thresholds; and a list of \(\tau\) positive-mass types. Each type includes its cohort’s public parking and battery parameters and its private discharge cost \(c\). The question is to choose a threshold pair from the given candidate sets and return the resulting online rate policy and per-vehicle transfers, maximizing expected social welfare within this threshold-policy family. A solution must satisfy each type’s battery and departure-charge constraints and make truthful cost reporting a dominant strategy. Its output includes the per-type schedule and transfers, not just the chosen thresholds.
For a type \(\theta\), let \(r_{\theta,t}\) be its per-vehicle rate and \(\mu_\theta\) its mass. Aggregate flow per vehicle is \(\bar r_t=\sum_\theta\mu_\theta r_{\theta,t}\). The objective weights degradation costs by mass and evaluates grid costs on aggregate flow:
\[
\mathrm{SW}=\sum_\theta \mu_\theta\bigl(-c_\theta W_\theta(r_\theta)\bigr)
+\sum_t\left[-\min(0,\bar r_t)p^{\mathrm{sell}}_t-\max(0,\bar r_t)p^{\mathrm{buy}}_t\right].
\]
Transfers cancel from social welfare. Because the population is continuous, both the input masses and the resulting aggregate flows are fractional.
I expect this restricted tuning problem to be tractable: enumerate candidate threshold pairs, evaluate the finite policy for each type and price scenario, and compute its mass-weighted welfare. For Algorithm 1 under the theorem’s constant-loss assumption, the cost response changes at finitely many price-dependent breakpoints, so the transfer calculation can use the paper’s payment formula without enumerating individual vehicles. The tractability claim is for this named algorithm family, not for globally optimal truthful online scheduling.
The mechanism has a direct connection to the paper’s other proved results. Theorem 1 gives sufficient conditions for truthfulness: monotonicity of work under the relevant type ordering, its specified transfer formula using the observed departure and work above the minimum needed charge, and the condition that the state of charge equals the reported target from the reported departure onward. Theorem 4, also proved here, establishes the required work monotonicity for Algorithms 1 and 2 with respect to departure time and required charge: an earlier departure or higher target has no greater work than the corresponding later-departure or lower-target type. Along with Theorem 2’s cost monotonicity, these results support the truthful cohort mechanism; they do not prove that its schedule maximizes welfare over all possible online mechanisms.
The mirror’s weakest point is its scope. It lifts the paper’s threshold heuristic and truthfulness guarantee, while the paper’s larger motivation is the intractability of globally optimizing online schedules under uncertain prices and arrivals. The continuous exact-optimum problem—given a mass distribution over complete EV types, find a welfare-maximizing truthful online mechanism—remains a worthwhile further question, but these anchors do not settle its complexity.
The proponent’s anchor is weak at its root: Theorem 2 proves a monotonicity property of a fixed scheduling rule. Theorem 1 gives sufficient conditions for truthfulness, and Theorems 3 and 4 establish further monotonicity properties. None states a complexity bound, classifies an optimization problem, or gives an exact or approximation algorithm. The paper says global optimization is intractable, but that claim appears in the motivation for its heuristics rather than as a numbered complexity result.
“Mass Threshold V2G Tuning” adds a separate problem: choose among supplied threshold pairs to maximize welfare. With finite candidate sets, a finite horizon, and an explicit price path or scenario tree, one can evaluate each pair against the \(\tau\) types and choose the best. That is a straightforward policy-selection procedure; Theorem 2 supplies a truthfulness property for each fixed policy. If the selected thresholds depend on reported costs or type masses, however, a report can change the chosen policy. The theorem’s monotonicity claim for a fixed threshold pair does not establish truthfulness of that selector. In an atomless model, an individual report has zero effect on the selected pair, which changes the strategic setting from the paper’s ex-post dominant-strategy problem.
The same limitation applies to Theorem 4: its work monotonicity in departure time and charge target may support truthful payments, but it does not identify a population-level computational problem. Aggregating identical agents simply weights their work by mass. That yields a continuous restatement of the mechanism property, while the proposed tuning problem supplies the computational content from elsewhere.
There is a stronger replacement mirror available: optimize social welfare over online schedules for a distribution of complete EV types, subject to truthful reporting and battery constraints. A large workplace fleet with recurring arrival windows, vehicle classes, and charge targets is a plausible high-multiplicity regime, and the authors would recognize the scheduling question. A finite scenario tree might admit a type-by-time optimization formulation; richer uncertainty could require a much larger policy or state representation. I cannot dismiss this mirror on the grounds that its answer may be easy, hard, or unchanged by continuization.
So the case against is strongest against the proposed anchor and its threshold-tuning formulation: neither gives a compelling complexity question anchored in the paper’s named results. It is weak against the paper’s central scheduling problem. The absence of a numbered complexity theorem is a serious mismatch with ChoCo’s usual target, but it does not rule out a worthwhile continuous mirror of the paper’s stated optimization problem.
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.