Theorem 1.1 — Harmonic is -competitive against adaptive online adversaries
ProvedHarmonicKServer.Competitive.harmonic_competitiveLet be any metric space, let , and let be arbitrary labelled initial configurations, allowing collocations. For the fixed Harmonic algorithm of Section 2 there is a finite , depending only on the metric, and the two initial configurations, such that every causal adaptive online adversary and every finite horizon satisfy
The adversary selects and serves each request before the fresh Harmonic sample, and may react to every previous online move. Arbitrary private random seeds and adaptive service schedules are admitted; infinite expected adversary cost is retained as an extended nonnegative value. The additive constant is quantified before seed spaces, seed laws, policies and horizons. No movement property, potential bound, distinct starting positions or finite-metric assumption is a hypothesis.
The paper proves this result mathematically. This item asks for its Lean proof, including the case and the causal lazification and private-edge reductions from the analysis convention with distinct lazy adversary locations.
Differences from the source:
- encoding: multisets of k servers on an arbitrary metric → labelled configurations Fin k → V, with k ≥ 1; reason: labels only distinguish server choices and movement charges; collocations and every original metric remain admissible
- encoding: expected costs against arbitrary randomized adaptive online adversaries → arbitrary measurable private-seed mixtures of full completed-label-history policies and nonnegative extended expectations; reason: the complete past is reconstructible from the seed and label prefix, so requests remain adaptive; the explicit interaction and conditioning bridge retain randomized policies and infinite expected costs
import Definitions.Def_HarmonicKServer_Competitive_Interaction
namespace HarmonicKServer.Competitive
open scoped BigOperators ENNReal
open MeasureTheory
/-- Theorem 1.1: every metric, k>=1, arbitrary starts, all adaptive online adversaries.
No potential or movement-property hypotheses are assumed. -/
theorem harmonic_competitive {k : ℕ} (hk : 1 ≤ k) {V : Type*} [MetricSpace V]
(X₀ Y₀ : KServer.Config k V) :
AdaptiveCompetitive X₀ Y₀ (2 * (k : ℝ)^4) := by sorry
end HarmonicKServer.Competitive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.