AFTD Auto-Formalizing Theoretical Domains

gen_k_server_uniform_competitive

def

Generalized k-server on k uniform metrics with m points each: configurations and requests are functions Fin k → Fin m. With k m : ℕ implicit, the predicate takes, in this order, P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ, a start configuration a : Fin k → Fin m and a real γ, and holds when gen_k_server_uniform_is_rand_alg P and there is a real constant c such that for every ρ : List (Fin k → Fin m), gen_k_server_uniform_expected_cost P a ρ ≤ γ * (gen_k_server_uniform_opt a ρ : ℝ) + c.

Statement

def gen_k_server_uniform_competitive {k m : ℕ}
    (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ)
    (a : Fin k → Fin m) (γ : ℝ) : Prop
Defined in
arXiv:2610.37192, Sec. 2: a randomized online algorithm is γ-competitive against an oblivious adversary if E[ALG(ρ)] ≤ γ·OPT(ρ) + c for every finite request sequence ρ, with c allowed to depend on the start configuration a
Verified
28 Oct 2026
Axioms
none listed
Built on 3
  • gen_k_server_uniform_is_rand_algGeneralized k-server where each of the k servers moves in its own copy of the uniform metric on m points: configurations and requests are…
  • gen_k_server_uniform_expected_costGeneralized k-server on k uniform metrics with m points each: configurations and requests are functions Fin k → Fin m. With k m : ℕ…
  • gen_k_server_uniform_optFor a start configuration a : Fin k → Fin m and a request list ρ, OPT is the infimum (sInf in ℕ) of the natural numbers c such that some…

Read back from the Lean

Given implicit natural numbers k and m, a transition probability function P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ, an initial configuration a : Fin k → Fin m, and a competitive ratio γ : ℝ, gen_k_server_uniform_competitive P a γ asserts that: 1. P is a valid randomized online algorithm (gen_k_server_uniform_is_rand_alg P), meaning that for all request histories past : List (Fin k → Fin m), current requests r : Fin k → Fin m, and current states x : Fin k → Fin m: - for every state y : Fin k → Fin m, 0 ≤ P past r x y, - the sum over all y : Fin k → Fin m of P past r x y equals 1, and - for every y : Fin k → Fin m, if P past r x y ≠ 0, then there exists some coordinate i : Fin k such that y i = r i (the request is served); AND 2. There exists an additive constant c : ℝ such that for all request sequences ρ : List (Fin k → Fin m), the expected cost of running P on ρ starting from configuration a is at most γ * (gen_k_server_uniform_opt a ρ : ℝ) + c.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- `P` is a γ-competitive randomized online algorithm (oblivious adversary) for generalized k-server on uniform metrics `Fin m`, started in `a`. -/
def gen_k_server_uniform_competitive {k m : ℕ}
    (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ)
    (a : Fin k → Fin m) (γ : ℝ) : Prop :=
  gen_k_server_uniform_is_rand_alg P ∧
    ∃ c : ℝ, ∀ ρ : List (Fin k → Fin m),
      gen_k_server_uniform_expected_cost P a ρ ≤ γ * (gen_k_server_uniform_opt a ρ : ℝ) + c
See it in the graphDiscuss this resultChallenge it