Exact local potential certificates for Bellman lower bounds
ProvedKServer.chunk_potential_iffLet X and Ω be finite, with a metric on X. Fix an escape price p, horizon n, real weights P on Ω, request sequences σ, and a function v:X→ℝ. The local potential conditions characterize Bellman lower bounds exactly:
The local conditions use an escape bound, branch lower values, movement inequalities for every legal serving position, recursively certified continuation potentials, and terminal inequalities at depth zero. For fixed metric, weights and requests, the expanded conditions are finite linear inequalities in real potential variables; they contain no nested minima.
The characterization is algebraic and requires no sign or normalization condition on P. When the weights, requests and horizon satisfy the hypotheses of the online Bellman lower-bound theorem, any such potential is consequently a valid online cost lower bound. The equivalence does not supply a regrouping distribution or claim an efficient algorithm for searching all possible distributions.
import Definitions.Def_KServer_chunk_potentials open KServer
theorem KServer.chunk_potential_iff {X : Type*} [MetricSpace X] [Fintype X]
{Ω : Type*} [Fintype Ω] (p : ℝ) (n : ℕ) (P : Ω → ℝ)
(σ : Ω → List (Set X)) (v : X → ℝ) :
IsChunkPotential p n P σ v ↔ ∀ x, v x ≤ chunkBellman p n P σ x := by sorry