Answer: Polynomial-time solvable
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 guarantees monotonicity of work w.r.t. cost parameter ci, i.e., ci ≥c0 i ! Wi(fi(✓i)) Wi(fi(✓0 i)), when the cost per unit charge is constant (i.e., independent of charging speed or state of charge).
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 society is given by its support: \(\tau\) complete EV types with positive binary-rational masses \(\mu_j\), summing to \(1\); \(\tau\) counts supported types, not possible types. There are \(m\) public cohorts, a horizon of \(H\) unit slots, an explicit price-scenario tree with \(S\) nodes and rational transition probabilities, and \(K\geq1\) indexed rational threshold pairs \(\rho_{\mathrm{low}}\leq\rho_{\mathrm{high}}\). Let \(L\) be the total input bit length; prices satisfy \(0\leq p^{\mathrm{sell}}\leq p^{\mathrm{buy}}\).
Each cohort has public integer arrival and departure times \(0\leq a<d\leq H\), rational initial charge \(s_a\), battery bounds \(0\leq s_{\min}\leq s_a\leq q\leq s_{\max}\), charging and discharging limits \(C,D>0\), and degradation coefficient \(\alpha>0\); assume \(q-s_a\leq C(d-a)\). Types in a cohort differ privately only in rational discharge cost \(c\geq0\); admissible reports are all nonnegative costs.
For a fixed pair, each vehicle acts independently at each observed tree node during its stay. At time \(t\), set the requested rate \(u=C\) if \(p^{\mathrm{buy}}\leq\rho_{\mathrm{low}}\) and \(s_t<q\); otherwise set \(u=-D\) if \(p^{\mathrm{sell}}-\alpha c\geq\rho_{\mathrm{high}}\), and \(u=0\) otherwise. Charge therefore takes priority when both tests hold.
Set \(b_{t+1}=\max\{s_{\min},q-C(d-t-1)\}\). The actual rate \(r_t\) is the projection of \(u\) onto \([\max\{-D,b_{t+1}-s_t\},\min\{C,q-s_t\}]\), and \(s_{t+1}=s_t+r_t\); rates are zero outside the stay. This enforces recharge feasibility and \(s_d=q\).
On a realized price path, work is \(W(c)=\alpha\sum_{t=a}^{d-1}\max\{0,-r_t(c)\}\). The departure transfer per vehicle is \(P(c)=cW(c)+\int_c^\infty W(x)\,dx\), where counterfactual work uses the same public cohort, selected pair and realized price path; the report-independent transfer constant is zero. Utility is \(P(\widehat c)-cW(\widehat c)\).
At node \(n\), aggregate rate is \(R_n=\sum_j\mu_jr_{j,n}\), with unrestricted grid exchange. Expected welfare is \(\sum_n\Pr(n)[p_n^{\mathrm{sell}}\max\{0,-R_n\}-p_n^{\mathrm{buy}}\max\{0,R_n\}-\sum_j\mu_jc_j\alpha_j\max\{0,-r_{j,n}\}]\).
Select the candidate pair of greatest expected welfare, breaking ties by index, and compute each supported type's contingent per-vehicle schedule and departure transfers. Require ex-post dominant-strategy truthfulness for unilateral zero-mass cost reports, which leave \(\mu\) and the selected pair unchanged.
Is this exact threshold-selection, scheduling and transfer problem solvable in polynomial time in \(H,S,m,\tau,K,L\), with the stated truthfulness requirement, or is it NP-hard?
For finitely many vehicles, the threshold scheduling rule is known to have work nonincreasing in reported discharge cost under constant per-unit degradation; the associated integral transfers implement truthful cost reporting. [Discrete monotonicity and transfer results](https://www.ijcai.org/Proceedings/16/Papers/048.pdf).
No verified complexity classification for this precise mass, finite-candidate selection and exact-transfer problem was found.
The stated problem is solvable exactly in polynomial time in \(H,S,m,\tau,K,L\), and its prescribed transfers satisfy the stated ex-post truthfulness requirement.
The proof requires two facts: work is nonincreasing in reported cost for the precise projection rule, and the transfer integral has only polynomially many relevant breakpoints. Both are proved below.
Fix a cohort, a candidate pair, and a realized price path. Suppress cohort indices. Define, for \(a\leq t\leq d\),
\(b_t=\max\{s_{\min},q-C(d-t)\}\).
The initial assumptions imply \(b_a\leq s_a\leq q\). Suppose inductively that \(b_t\leq s_t\leq q\). Then
\(b_{t+1}\leq s_t+C\), and \(b_{t+1}\leq q\).
Indeed, both entries defining \(b_{t+1}\) are at most \(s_t+C\): we have \(s_{\min}\leq s_t\), and \(q-C(d-t-1)\leq s_t+C\).
Consequently, the projection interval
\([\ell_t,h_t]=[\max\{-D,b_{t+1}-s_t\},\min\{C,q-s_t\}]\)
is nonempty. To verify this, each entry defining \(\ell_t\) is at most both entries defining \(h_t\): use \(D,C>0\), \(q-s_t\geq0\), \(b_{t+1}-s_t\leq C\), and \(b_{t+1}\leq q\).
Projection therefore gives
\(-D\leq r_t\leq C\), and \(b_{t+1}\leq s_{t+1}\leq q\).
Induction proves feasibility throughout the stay. Since \(b_d=q\), it also proves \(s_d=q\).
Writing \(s=s_t\) and \(b=b_{t+1}\), the three possible requests have the following exact next-state formulas:
| Requested rate | Next state |
|---|---|
| \(C\) | \(\min\{q,s+C\}\) |
| \(0\) | \(\max\{s,b\}\) |
| \(-D\) | \(\max\{s-D,b\}\) |
For request \(C\), projection selects the upper endpoint. For request \(-D\), it selects the lower endpoint. For request \(0\), the upper endpoint is nonnegative, so projection gives rate \(\max\{0,b-s\}\). These observations establish all three formulas.
Fix the same cohort, pair, and price path, and compare reports \(x<y\), with \(x,y\geq0\). Let \(s_t(x)\) and \(s_t(y)\) be their respective states.
We first prove the state-order invariant
\(s_t(x)\leq s_t(y)\)
at every time. It holds at arrival because the initial state is public and identical.
Define the discharge-test indicator
\(E_t(z)=\mathbf{1}\{p_t^{\mathrm{sell}}-\alpha z\geq\rho_{\mathrm{high}}\}\).
Since \(\alpha>0\), we have \(E_t(x)\geq E_t(y)\).
Suppose the state-order invariant holds at time \(t\). There are two cases.
Case 1: \(p_t^{\mathrm{buy}}>\rho_{\mathrm{low}}\). Neither report requests priority charging. The transition is therefore
\(s_{t+1}(z)=\max\{b_{t+1},s_t(z)-DE_t(z)\}\).
Because \(s_t(x)\leq s_t(y)\) and \(E_t(x)\geq E_t(y)\),
\(s_t(x)-DE_t(x)\leq s_t(y)-DE_t(y)\).
Taking maxima with the same \(b_{t+1}\) preserves this inequality.
Case 2: \(p_t^{\mathrm{buy}}\leq\rho_{\mathrm{low}}\). Since \(y>x\geq0\), we have \(y>0\). The price and threshold assumptions give
\(p_t^{\mathrm{sell}}-\alpha y<p_t^{\mathrm{sell}}\leq p_t^{\mathrm{buy}}\leq\rho_{\mathrm{low}}\leq\rho_{\mathrm{high}}\).
Thus \(E_t(y)=0\). The higher report’s next state is consequently
\(s_{t+1}(y)=\min\{q,s_t(y)+C\}\),
including when its current state is already \(q\).
If \(s_t(x)<q\), priority charging gives the same transition formula for the lower report, and state order follows from monotonicity of \(s\mapsto\min\{q,s+C\}\).
If \(s_t(x)=q\), the induction hypothesis forces \(s_t(y)=q\). The higher report remains at \(q\), whereas feasibility guarantees \(s_{t+1}(x)\leq q\).
This completes the state-order induction, including the boundary case \(x=0\).
Now define total charging and discharging energies:
\(Q^+(z)=\sum_{t=a}^{d-1}\max\{0,r_t(z)\}\), and \(Q^-(z)=\sum_{t=a}^{d-1}\max\{0,-r_t(z)\}\).
We prove that the lower report receives at least as much positive charging in every slot.
Therefore \(Q^+(x)\geq Q^+(y)\). Both schedules start at \(s_a\) and end at \(q\), so telescoping the state changes gives
\(Q^+(z)-Q^-(z)=q-s_a\).
It follows that \(Q^-(x)\geq Q^-(y)\). Multiplication by \(\alpha>0\) proves
\(W(x)\geq W(y)\).
Thus work is nonincreasing on the entire nonnegative report domain. This verifies the monotonicity needed for the stated rule directly; the [cited IJCAI paper](https://www.ijcai.org/Proceedings/16/Papers/048.pdf) develops the corresponding threshold-rule and integral-transfer approach.
Continue to fix one cohort, one candidate pair, and one realized path through departure. At every slot during the stay, define
\(\beta_t=\dfrac{p_t^{\mathrm{sell}}-\rho_{\mathrm{high}}}{\alpha}\).
The discharge test for report \(z\) is exactly \(z\leq\beta_t\).
On any open interval containing no \(\beta_t\), every discharge-test indicator is constant. The entire schedule is then constant on that interval: the initial state is fixed, and induction through the slots shows that the requested rates, projected rates, and subsequent states are identical. Hence \(W(z)\) is constant there.
There are at most \(d-a\leq H\) distinct breakpoints. Moreover, if
\(B=\max\bigl(\{0\}\cup\{\beta_t:a\leq t<d\}\bigr)\),
then \(W(z)=0\) for every \(z>B\). Such a report never requests discharge; requests \(C\) and \(0\) both produce nonnegative rates.
To compute the integral for a supported rational cost \(c\), list the distinct breakpoints strictly greater than \(c\) in increasing order:
\(z_1<\cdots<z_M\), with \(z_0=c\).
If the list is empty, the integral is zero. Otherwise \(z_M=B\), and the exact formula is
\(\displaystyle \int_c^\infty W(z)\,dz=\sum_{i=0}^{M-1}(z_{i+1}-z_i)\,W\!\left(\frac{z_i+z_{i+1}}{2}\right)\).
Every midpoint lies in an interval on which work is constant. Values at the finitely many endpoints do not affect the integral.
Compute \(W(c)\) separately using the stipulated weak inequalities and charge priority. This preserves the exact allocation at a breakpoint. The required transfer is then exactly
\(\displaystyle P(c)=cW(c)+\sum_{i=0}^{M-1}(z_{i+1}-z_i)\,W\!\left(\frac{z_i+z_{i+1}}{2}\right)\).
Sorting uses \(O(H\log(1+H))\) comparisons. Simulating every midpoint uses \(O(H^2)\) arithmetic operations. All quantities are rational.
Fix a realized path and the selected pair. By the zero-mass assumption, a unilateral report leaves the support masses and selected pair unchanged. Therefore the preceding monotonicity result applies to all counterfactual reports of that vehicle.
Write
\(I(z)=\int_z^\infty W(v)\,dv\).
For true cost \(c\) and reported cost \(y\), utility is
\(U(y;c)=(y-c)W(y)+I(y)\),
whereas truthful utility is \(U(c;c)=I(c)\).
If \(y>c\), then
\(\displaystyle U(c;c)-U(y;c)=\int_c^y\bigl(W(v)-W(y)\bigr)\,dv\geq0\).
If \(y<c\), then
\(\displaystyle U(c;c)-U(y;c)=\int_y^c\bigl(W(y)-W(v)\bigr)\,dv\geq0\).
Both inequalities follow from the proved monotonicity. Equality of reports gives equality of utilities.
These arguments hold for every realized path and every nonnegative report, including breakpoint reports. Thus truthful reporting is an ex-post dominant strategy under the precise unilateral zero-mass requirement.
The complete algorithm is as follows.
The tree structure is essential: every node has one ancestral history. Thus a type has one state per active node. Also, the number of distinct prefixes ending at any departure time is at most \(S\), including prefixes of probability zero.
Precomputing feasibility bounds costs \(O(mH)\) operations. Evaluating all candidates costs \(O(K\tau S)\). Computing all departure transfers costs at most
\(O\bigl(\tau S[H^2+H\log(1+H)]\bigr)\).
Schedules and departure transfers have at most \(O(\tau S)\) entries.
It remains to check that exact rational arithmetic has polynomial bit cost.
Let \(Q\) be the product of the denominators of all input rationals, and let \(A\) be the product of the positive numerators of the public degradation coefficients, each written as a reduced fraction. Both products have bit length \(O(L)\).
The magnitudes of these quantities are bounded by sums of polynomially many terms involving a fixed number of input rational factors, with at most an additional factor \(H\). Consequently, their numerators also have polynomial bit length. Exact comparisons, sorting, arithmetic, and output encoding therefore take polynomial time.
Finite candidate enumeration, explicit-tree simulation, and finite-breakpoint integration give an exact polynomial-time algorithm. The state-order and energy-balance argument proves cost monotonicity for the specified projection rule, and the prescribed integral transfer then proves ex-post dominant-strategy truthfulness.
This settles the stated problem with all its requested outputs and its zero-mass truthfulness requirement.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes an exact polynomial-time algorithm for the stated problem and proves the required ex-post truthfulness under unilateral zero-mass reports. I found no major or minor mathematical issues.
The conclusion concerns the explicit scenario tree, the supplied finite candidate list, and supported types. It does not rely on enumerating possible types or choosing thresholds outside that list.
The initial invariant \(b_a\leq s_a\leq q\) follows from the stated assumptions: both \(s_{\min}\) and \(q-C(d-a)\) are at most \(s_a\).
The induction step is correct. From \(b_t\leq s_t\), the proof obtains \(b_{t+1}-s_t\leq C\); from \(b_{t+1}\leq q\), it obtains \(b_{t+1}-s_t\leq q-s_t\). Together with \(D,C>0\) and \(s_t\leq q\), these inequalities verify that every candidate lower endpoint is at most every candidate upper endpoint. Thus the projection interval is nonempty.
Projection into that interval preserves the rate bounds and gives \(b_{t+1}\leq s_{t+1}\leq q\). At departure, \(b_d=q\), so the terminal equality \(s_d=q\) follows.
All three simplified transitions are correct:
There is no omitted feasibility exception for a one-slot stay, an initially full battery, or \(s_{\min}=q\).
The comparison correctly fixes the cohort, candidate pair, and realized price path while allowing arbitrary reports \(0\leq x<y\).
The indicator inequality \(E_t(x)\geq E_t(y)\) follows from \(\alpha>0\).
When the charging price test fails, the transition formula is correct, including cases where projection forces charging. The two inequalities \(s_t(x)\leq s_t(y)\) and \(E_t(x)\geq E_t(y)\) imply the stated order before taking the maximum with the common feasibility bound.
When the charging price test holds, the strict inequality
\(p_t^{\mathrm{sell}}-\alpha y<\rho_{\mathrm{high}}\)
is justified: \(y>0\), \(\alpha>0\), and the price and threshold inequalities supply the remaining chain. Hence the higher report cannot request discharge in this case.
The resulting higher-report transition is valid even at state \(q\): its zero request keeps it at \(q\), agreeing with the displayed formula. For the lower report, priority charging applies below \(q\); at \(q\), state order forces both current states to equal \(q\), and feasibility supplies the required next-state inequality. This handles \(x=0\), including possible discharge-test equality.
The positive-charging comparison is also correct:
These expressions have the stated dependence on state, establishing \(Q^+(x)\geq Q^+(y)\).
Finally, feasibility gives the same initial and terminal states for both schedules. The identity \(Q^+(z)-Q^-(z)=q-s_a\) therefore justifies the passage from total charging monotonicity to total discharging monotonicity. Multiplication by the positive coefficient \(\alpha\) proves the claimed work monotonicity.
The [IJCAI reference](https://www.ijcai.org/Proceedings/16/Papers/048.pdf) is contextual; the output supplies its own monotonicity argument rather than relying on an unstated external theorem.
The breakpoint equation is correct because division by \(\alpha>0\) preserves the inequality: discharge eligibility is exactly \(z\leq\beta_t\).
The constancy argument accounts for the state-dependent charging test. On an interval with fixed discharge indicators, identical initial states and induction give identical states, charging decisions, requests, and projections. Consequently, work is constant on that interval.
There are at most \(d-a\leq H\) distinct breakpoints. Beyond \(B\), no discharge request occurs, and the verified transitions for requests \(C\) and \(0\) have nonnegative rates. Thus work vanishes there and the integral is finite.
The integration formula correctly handles:
When the list is nonempty, its largest entry is indeed \(B\): it is positive and exceeds \(c\geq0\). The midpoint evaluations therefore cover the entire potentially nonzero tail. Values at finitely many endpoints do not affect the integral.
Computing \(W(c)\) separately preserves the specified allocation at equality. The formula for \(P(c)\), the sorting bound, and the simulation bound are all correct.
The argument uses precisely the report-independence stipulated by the task: a unilateral zero-mass report leaves the masses and selected pair unchanged.
Both utility-difference identities have the correct signs. For \(y>c\), monotonicity makes \(W(v)-W(y)\) nonnegative throughout the integration interval. For \(y<c\), it makes \(W(y)-W(v)\) nonnegative. Equal reports yield equal utilities.
These comparisons hold for every realized path and every admissible nonnegative report. Discontinuities and equality at breakpoints do not invalidate either identity or inequality.
The output therefore proves the requested ex-post dominant-strategy property. It does not require truthfulness for reports that change the selected pair.
The algorithm evaluates the specified welfare, including aggregation before applying the grid purchase/sale terms.
Because the input is a tree, each node has a unique ancestral history. Propagating each supported type’s state therefore produces a well-defined contingent schedule without enumerating an implicit collection of histories.
Exact comparison of candidate welfare values implements greatest-welfare selection and the prescribed index tie-break.
For each departure time, the number of relevant prefixes is at most \(S\). Computing a transfer separately for each supported type and departure prefix consequently gives the stated polynomial bound. Probability-zero prefixes can also be processed without increasing that bound.
The schedule and transfer representation has at most \(O(\tau S)\) entries. Thus the algorithm produces the requested outputs with polynomial representation size.
The denominator argument is valid.
The products \(Q\) and \(A\) have bit length \(O(L)\), since their factor bit lengths are included in the input.
States and rates retain denominators dividing \(Q\): their transitions use public rational quantities, integer multiples, addition, subtraction, and selection by minima or maxima.
A tree path uses distinct input edges, so its probability denominator divides \(Q\). The stated bounds \(Q^2\) for aggregate rates and \(Q^5\) for probability-weighted welfare contributions are sufficient. Summation preserves the common denominator bound.
The breakpoint denominator bound \(Q^2A\) is sufficient. Although midpoint reports may introduce a denominator factor of \(2\), this does not introduce that factor into work: the report determines branch decisions, while the resulting states and rates still have denominators dividing \(Q\). Thus the stated work and integral-summand denominator bounds remain valid. The bound for \(cW(c)\) is also correct.
The magnitude argument adequately bounds numerator lengths: there are polynomially many terms, with a fixed number of input rational factors and polynomial factors from accumulation. Consequently, exact arithmetic, comparisons, sorting, and output encoding have polynomial bit cost.
None. The argument resolves the assigned problem as written, including exact transfers and the specified truthfulness requirement.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.