Proposition 2 — frequent re-solving loses Ω(√T) against hindsight
ProvedResolvingNRM.FRLower.fr_regret_lower_boundConsider two independent rate-one Poisson customer classes that each consume one unit of a single resource. The initial resource capacity is the positive integer horizon , and their prices satisfy . For every choice of optimal DLP solution used by Algorithm 2, there are constants and , depending only on the prices, such that for every ,
Thus frequent re-solving can lose order even though it reoptimizes every period; the benchmark is the expected hindsight optimum.
Formalization Note Proposition 2 states existence of an instance, while its Appendix C.1 proof supplies this explicit two-class family. The assumption is the positive-price reading needed for the paper's LP allocation formula; the inequality is stated on pp. 18 and 32. The threshold and constant are chosen before the LP selector and the horizon. The printed phase proof uses although the proposition is stated for all sufficiently large horizons; this gap is recorded in the moderation notes.
import Mathlib import Definitions.Def_ResolvingNRM_FRLower_Instance
namespace ResolvingNRM.FRLower
/-- Proposition 2 on the explicit two-class instance of Appendix C.1. The positive
constant and horizon threshold may depend on the two prices, but not on the DLP
tie-breaking selector or the horizon. -/
theorem fr_regret_lower_bound (r₁ r₂ : ℝ) (hr₂ : 0 < r₂) (hr : r₂ < r₁) :
∃ M : ℝ, 0 < M ∧ ∃ T₀ : ℕ, 1 ≤ T₀ ∧
∀ sel : (Fin 1 → ℝ) → Fin 2 → ℝ,
IsDLPSelector (twoClass r₁ r₂ (le_of_lt hr₂) (le_of_lt hr)) sel →
∀ T : ℕ, T₀ ≤ T →
hindsightValue (twoClass r₁ r₂ (le_of_lt hr₂) (le_of_lt hr)) (T : ℝ)
(initialCapacity T) -
frTail (twoClass r₁ r₂ (le_of_lt hr₂) (le_of_lt hr)) sel T
(initialCapacity T) ≥ M * Real.sqrt (T : ℝ) := by sorry
end ResolvingNRM.FRLower
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.