AFTD Auto-Formalizing Theoretical Domains

gen_k_server_uniform_one_server_competitive_one

theoremverified

With one server (k = 1, configurations Fin 1 → Fin m) and any start configuration a, there are transition probabilities P with gen_k_server_uniform_is_rand_alg P whose expected cost on every request list ρ is at most gen_k_server_uniform_opt a ρ.

Statement

theorem gen_k_server_uniform_one_server_competitive_one (m : ℕ) (a : Fin 1 → Fin m) :
    ∃ P, gen_k_server_uniform_is_rand_alg P ∧ ∀ ρ : List (Fin 1 → Fin m),
      gen_k_server_uniform_expected_cost P a ρ ≤ (gen_k_server_uniform_opt a ρ : ℝ)
Source
Smallest case k = 1 of OP-613 (arXiv:2610.37192, Sec. 6): with one server the request determines the configuration, so following the requests is optimal
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • gen_k_server_uniform_path_costFor a start configuration x : Fin k → Fin m and a list of configurations, the path cost is defined by recursion on the list: 0 for the…
  • gen_k_server_uniform_expected_cost_fromGeneralized k-server on k uniform metrics with m points each: both configurations and requests are functions Fin k → Fin m (one point per…

The proof, explained

To prove that the 1-server problem has a 1-competitive online algorithm, we consider the deterministic greedy policy P_det that moves the single server directly to the requested position at each arrival. For a single server (k = 1), any configuration serving request r must equal r because the server index set Fin 1 is a singleton; therefore, the only sequence of configurations that can service request list ρ is ρ itself. Consequently, the offline optimal cost opt(a, ρ) is uniquely attained by ρ and equals the direct path cost path_cost(a, ρ). Since the deterministic algorithm follows exactly this sequence of transitions, its expected cost also equals path_cost(a, ρ), achieving a competitive ratio of 1.

  1. The transition probabilities P_det are non-negative. automation

    For any past history, request r, and current configuration x, the probability P_det past r x y is defined as 1 if y = r and 0 otherwise. Splitting on whether y = r gives either 1 or 0, both of which are non-negative by linear arithmetic.

    lines 9–13

      intro past r x
      refine ⟨?_, ?_, ?_⟩
      · intro y
        dsimp [gen_k_server_uniform_one_server_competitive_one_P_det]
        split_ifs <;> linarith
  2. The transition probabilities from any configuration sum to 1.

    Summing the indicator of y = r over all configurations y in the universe collapses to 1 using sum_ite_eq', since the target request r is an element of the universe (mem_univ, ite_true).

    lines 14–15

    uses sum_ite_eq', mem_univ, ite_true

      · dsimp [gen_k_server_uniform_one_server_competitive_one_P_det]
        simp only [sum_ite_eq', mem_univ, ite_true]
  3. Any transition with positive probability serves the requested configuration.

    If P_det past r x y ≠ 0, then y must equal r since the probability is 0 otherwise. In the 1-server setting, server 0 satisfies y(0) = r(0), which witnesses that y serves r.

    lines 16–21

      · intro y hy
        dsimp [gen_k_server_uniform_one_server_competitive_one_P_det] at hy
        split_ifs at hy with h
        · subst h
          exact ⟨0, rfl⟩
        · contradiction
  4. Base case: on an empty request list, the expected cost equals the path cost (both are 0).

    We proceed by induction on the request list ρ. When ρ = [], both gen_k_server_uniform_expected_cost_from and gen_k_server_uniform_path_cost are 0 by definition.

    lines 28–30

      induction ρ generalizing past x with
      | nil =>
        simp [gen_k_server_uniform_expected_cost_from, gen_k_server_uniform_path_cost]
  5. The expected cost of serving the first request r starting from configuration x is hammingDist(x, r).

    For request list r :: rs, the one-step expected cost sums over x' and y the initial distribution (a point mass at x), the transition probability P_det(x' → y), and the Hamming distance from x' to y. Since the initial distribution is 0 for x' ≠ x and 1 for x' = x, the sum over x' isolates x using one_mul, zero_mul, and sum_const_zero. The sum over y of the indicator of y = r times hammingDist(x, y) collapses via sum_ite_eq', mem_univ, and ite_true to hammingDist(x, r).

    lines 31–56

    uses one_mul, zero_mul, sum_const_zero, sum_ite_eq', mem_univ, ite_true

      | cons r rs ih =>
        simp only [gen_k_server_uniform_expected_cost_from, gen_k_server_uniform_path_cost]
        have h1 : (∑ x', ∑ y, (if x' = x then (1:ℝ) else 0) *
            gen_k_server_uniform_one_server_competitive_one_P_det past r x' y * (hammingDist x' y : ℝ)) =
            (hammingDist x r : ℝ) := by
          have : (fun x' => (∑ y, (if x' = x then (1:ℝ) else 0) *
              gen_k_server_uniform_one_server_competitive_one_P_det past r x' y * (hammingDist x' y : ℝ))) =
              (fun x' => if x' = x then
                (∑ y, gen_k_server_uniform_one_server_competitive_one_P_det past r x y * (hammingDist x y : ℝ))
                else 0) := by
            ext x'
            split_ifs with h
            · subst h
              simp only [one_mul]
            · simp only [zero_mul, sum_const_zero]
          rw [this, sum_ite_eq' univ x]
          simp only [mem_univ, ite_true]
          dsimp [gen_k_server_uniform_one_server_competitive_one_P_det]
          have : (fun y => (if y = r then (1:ℝ) else 0) * (hammingDist x y : ℝ)) =
              (fun y => if y = r then (hammingDist x r : ℝ) else 0) := by
            ext y
            split_ifs with h
            · subst h; ring
            · ring
          rw [this, sum_ite_eq' univ r]
          simp only [mem_univ, ite_true]
  6. After serving request r, the updated server distribution is the point mass at r.

    The distribution on configurations after the transition assigns to each y the probability ∑_{x'} δ_x(x') P_det(x' → y). The sum over x' collapses to P_det(x → y) using sum_ite_eq', mem_univ, and ite_true, which equals 1 if y = r and 0 otherwise.

    lines 57–70

    uses sum_ite_eq', mem_univ, ite_true

        have h2 : (fun y => ∑ x', (if x' = x then (1:ℝ) else 0) *
            gen_k_server_uniform_one_server_competitive_one_P_det past r x' y) =
            (fun y => if y = r then (1:ℝ) else 0) := by
          ext y
          have : (fun x' => (if x' = x then (1:ℝ) else 0) *
              gen_k_server_uniform_one_server_competitive_one_P_det past r x' y) =
              (fun x' => if x' = x then gen_k_server_uniform_one_server_competitive_one_P_det past r x y else 0) := by
            ext x'
            split_ifs with h
            · subst h; ring
            · ring
          rw [this, sum_ite_eq' univ x]
          simp only [mem_univ, ite_true]
          dsimp [gen_k_server_uniform_one_server_competitive_one_P_det]
  7. Inductive step: the expected cost on r :: rs equals the total path cost on r :: rs.

    Substituting the first-step cost hammingDist(x, r) and the updated state distribution δ_r into the recursive formula, the future expected cost matches the path cost from r on rs by the induction hypothesis. Adding hammingDist(x, r) gives the full path cost on r :: rs.

    lines 71–73

        rw [h1, h2, ih (past ++ [r]) r]
        push_cast
        rfl
  8. For a single server, any configuration o serving request r must be identical to r.

    Configuration o serves r if o(i) = r(i) for some server index i ∈ Fin 1. Since Fin 1 has only one element, any index j satisfies j = i by Subsingleton.elim, so o(j) = r(j) for all j, establishing o = r by function extensionality.

    lines 77–81

    uses Subsingleton.elim

      obtain ⟨i, hi⟩ := h
      funext j
      have : j = i := Subsingleton.elim j i
      rw [this]
      exact hi
  9. Any configuration sequence that serves request list ρ step-by-step is identical to ρ.

    By induction on the relation List.Forall₂: the empty sequence can only match the empty sequence. For a cons step, the head configuration serves the head request and thus equals it by gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_serves, while the tails are identical by the induction hypothesis.

    lines 86–89

    uses gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_serves

      induction h with
      | nil => rfl
      | cons h1 h2 ih =>
        rw [gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_serves h1, ih]
  10. The request sequence ρ validly serves itself.

    By induction on ρ: the empty list serves itself via List.Forall₂.nil. For r :: rs, configuration r serves request r at server 0 (since r(0) = r(0)), and combining this with the induction hypothesis via List.Forall₂.cons completes the proof.

    lines 94–97

    uses List.Forall₂.nil, List.Forall₂.cons

      induction ρ with
      | nil => exact List.Forall₂.nil
      | cons r rs ih =>
        exact List.Forall₂.cons ⟨0, rfl⟩ ih
  11. For 1 server, the offline optimal cost opt(a, ρ) equals the path cost path_cost(a, ρ).

    By definition, opt(a, ρ) is the infimum of path costs over all sequences serving ρ. Serving ρ with itself (gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl) shows path_cost(a, ρ) is achievable, so opt(a, ρ) ≤ path_cost(a, ρ) by Nat.sInf_le. Conversely, any valid sequence must equal ρ by gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_serves, making path_cost(a, ρ) a lower bound for all valid costs and giving the reverse inequality by le_csInf. Antisymmetry (le_antisymm) yields equality.

    lines 102–110

    uses gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl, le_antisymm, Nat.sInf_le, le_csInf, gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_serves

      dsimp [gen_k_server_uniform_opt]
      have h_mem : gen_k_server_uniform_path_cost a ρ ∈
          {c | ∃ os, List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ ∧ gen_k_server_uniform_path_cost a os = c} := by
        exact ⟨ρ, gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl ρ, rfl⟩
      apply le_antisymm
      · exact Nat.sInf_le h_mem
      · apply le_csInf ⟨_, h_mem⟩
        rintro c ⟨os, hos, rfl⟩
        rw [gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_serves hos]
  12. Algorithm P_det is a valid randomized algorithm whose expected cost on any request sequence ρ is at most the offline optimum opt(a, ρ).

    We provide P_det as witness, which is valid by gen_k_server_uniform_one_server_competitive_one_is_rand_alg. Unfolding gen_k_server_uniform_expected_cost and rewriting with gen_k_server_uniform_one_server_competitive_one_expected_cost_from shows the expected cost is path_cost(a, ρ), while gen_k_server_uniform_one_server_competitive_one_opt_eq_path_cost shows the offline optimum is also path_cost(a, ρ). Since path_cost(a, ρ) ≤ path_cost(a, ρ), the 1-competitiveness bound holds.

    lines 115–120

    uses gen_k_server_uniform_one_server_competitive_one_is_rand_alg, gen_k_server_uniform_one_server_competitive_one_expected_cost_from, gen_k_server_uniform_one_server_competitive_one_opt_eq_path_cost

      use gen_k_server_uniform_one_server_competitive_one_P_det
      refine ⟨gen_k_server_uniform_one_server_competitive_one_is_rand_alg m, ?_⟩
      intro ρ
      dsimp [gen_k_server_uniform_expected_cost]
      rw [gen_k_server_uniform_one_server_competitive_one_expected_cost_from,
          gen_k_server_uniform_one_server_competitive_one_opt_eq_path_cost]
sum_ite_eq'
The sum over a finite set s of an indicator term (which is b(x) when x = a and 0 otherwise) equals b(a) if a ∈ s, and 0 otherwise.
mem_univ
In any finite type, every element belongs to the universal finite set Finset.univ.
ite_true
An if-then-else expression whose condition is True evaluates to its then-branch.
one_mul
Multiplying any element by 1 on the left leaves it unchanged (1 * a = a).
zero_mul
Multiplying any element by 0 on the left yields 0 (0 * a = 0).
sum_const_zero
The sum of the constant zero function over any finite set is 0.
Subsingleton.elim
Any two elements of a subsingleton type are equal.
gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_serves
For a single server (k = 1), if a configuration o serves request r (i.e. agrees with r at some server index), then o = r.
List.Forall₂.nil
The pointwise relation List.Forall₂ R holds vacuously between two empty lists.
List.Forall₂.cons
If R(a, b) holds and R holds pointwise between lists l₁ and l₂, then R holds pointwise between a :: l₁ and b :: l₂.
gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl
Every request sequence ρ of 1-server configurations serves itself step-by-step.
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.
Nat.sInf_le
The infimum (minimum) of a set of natural numbers is less than or equal to any element in the set.
le_csInf
In a conditionally complete lattice, any lower bound of a non-empty set is at most the infimum of the set.
gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_serves
For a single server (k = 1), any configuration sequence os that serves request sequence ρ step-by-step is identical to ρ.
gen_k_server_uniform_one_server_competitive_one_is_rand_alg
The transition probability function P_det defines a valid randomized algorithm (probabilities are non-negative, sum to 1, and only transition to configurations serving the request).
gen_k_server_uniform_one_server_competitive_one_expected_cost_from
Under transition function P_det, the expected cost on request sequence ρ from an initial point-mass distribution at configuration x equals the deterministic path cost from x along ρ.
gen_k_server_uniform_one_server_competitive_one_opt_eq_path_cost
For a single server (k = 1), the offline optimal cost opt(a, ρ) from initial configuration a equals the direct path cost path_cost(a, ρ).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Finsetdef gen_k_server_uniform_one_server_competitive_one_P_det {k m : ℕ} :    List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ :=  fun _past r _x y => if y = r then 1 else 0lemma gen_k_server_uniform_one_server_competitive_one_is_rand_alg (m : ℕ) :    gen_k_server_uniform_is_rand_alg (gen_k_server_uniform_one_server_competitive_one_P_det (k := 1) (m := m)) := by  intro past r x  refine ⟨?_, ?_, ?_⟩  · intro y    dsimp [gen_k_server_uniform_one_server_competitive_one_P_det]    split_ifs <;> linarith  · dsimp [gen_k_server_uniform_one_server_competitive_one_P_det]    simp only [sum_ite_eq', mem_univ, ite_true]  · intro y hy    dsimp [gen_k_server_uniform_one_server_competitive_one_P_det] at hy    split_ifs at hy with h    · subst h      exact ⟨0, rfl⟩    · contradictionlemma gen_k_server_uniform_one_server_competitive_one_expected_cost_from {k m : ℕ}    (past : List (Fin k → Fin m)) (x : Fin k → Fin m) (ρ : List (Fin k → Fin m)) :    gen_k_server_uniform_expected_cost_from gen_k_server_uniform_one_server_competitive_one_P_det past      (fun z => if z = x then 1 else 0) ρ =      (gen_k_server_uniform_path_cost x ρ : ℝ) := by  induction ρ generalizing past x with  | nil =>    simp [gen_k_server_uniform_expected_cost_from, gen_k_server_uniform_path_cost]  | cons r rs ih =>    simp only [gen_k_server_uniform_expected_cost_from, gen_k_server_uniform_path_cost]    have h1 : (∑ x', ∑ y, (if x' = x then (1:ℝ) else 0) *        gen_k_server_uniform_one_server_competitive_one_P_det past r x' y * (hammingDist x' y : ℝ)) =        (hammingDist x r : ℝ) := by      have : (fun x' => (∑ y, (if x' = x then (1:ℝ) else 0) *          gen_k_server_uniform_one_server_competitive_one_P_det past r x' y * (hammingDist x' y : ℝ))) =          (fun x' => if x' = x then            (∑ y, gen_k_server_uniform_one_server_competitive_one_P_det past r x y * (hammingDist x y : ℝ))            else 0) := by        ext x'        split_ifs with h        · subst h          simp only [one_mul]        · simp only [zero_mul, sum_const_zero]      rw [this, sum_ite_eq' univ x]      simp only [mem_univ, ite_true]      dsimp [gen_k_server_uniform_one_server_competitive_one_P_det]      have : (fun y => (if y = r then (1:ℝ) else 0) * (hammingDist x y : ℝ)) =          (fun y => if y = r then (hammingDist x r : ℝ) else 0) := by        ext y        split_ifs with h        · subst h; ring        · ring      rw [this, sum_ite_eq' univ r]      simp only [mem_univ, ite_true]    have h2 : (fun y => ∑ x', (if x' = x then (1:ℝ) else 0) *        gen_k_server_uniform_one_server_competitive_one_P_det past r x' y) =        (fun y => if y = r then (1:ℝ) else 0) := by      ext y      have : (fun x' => (if x' = x then (1:ℝ) else 0) *          gen_k_server_uniform_one_server_competitive_one_P_det past r x' y) =          (fun x' => if x' = x then gen_k_server_uniform_one_server_competitive_one_P_det past r x y else 0) := by        ext x'        split_ifs with h        · subst h; ring        · ring      rw [this, sum_ite_eq' univ x]      simp only [mem_univ, ite_true]      dsimp [gen_k_server_uniform_one_server_competitive_one_P_det]    rw [h1, h2, ih (past ++ [r]) r]    push_cast    rfllemma gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_serves    {m : ℕ} {o r : Fin 1 → Fin m} (h : ∃ i : Fin 1, o i = r i) : o = r := by  obtain ⟨i, hi⟩ := h  funext j  have : j = i := Subsingleton.elim j i  rw [this]  exact hilemma gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_serves    {m : ℕ} {os ρ : List (Fin 1 → Fin m)}    (h : List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ) : os = ρ := by  induction h with  | nil => rfl  | cons h1 h2 ih =>    rw [gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_serves h1, ih]lemma gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl    {m : ℕ} (ρ : List (Fin 1 → Fin m)) :    List.Forall₂ (fun o r => ∃ i, o i = r i) ρ ρ := by  induction ρ with  | nil => exact List.Forall₂.nil  | cons r rs ih =>    exact List.Forall₂.cons ⟨0, rfl⟩ ihlemma gen_k_server_uniform_one_server_competitive_one_opt_eq_path_cost    (m : ℕ) (a : Fin 1 → Fin m) (ρ : List (Fin 1 → Fin m)) :    gen_k_server_uniform_opt a ρ = gen_k_server_uniform_path_cost a ρ := by  dsimp [gen_k_server_uniform_opt]  have h_mem : gen_k_server_uniform_path_cost a ρ ∈      {c | ∃ os, List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ ∧ gen_k_server_uniform_path_cost a os = c} := by    exact ⟨ρ, gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl ρ, rfl⟩  apply le_antisymm  · exact Nat.sInf_le h_mem  · apply le_csInf ⟨_, h_mem⟩    rintro c ⟨os, hos, rfl⟩    rw [gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_serves hos]theorem gen_k_server_uniform_one_server_competitive_one (m : ℕ) (a : Fin 1 → Fin m) :    ∃ P, gen_k_server_uniform_is_rand_alg P ∧ ∀ ρ : List (Fin 1 → Fin m),      gen_k_server_uniform_expected_cost P a ρ ≤ (gen_k_server_uniform_opt a ρ : ℝ) := by  use gen_k_server_uniform_one_server_competitive_one_P_det  refine ⟨gen_k_server_uniform_one_server_competitive_one_is_rand_alg m, ?_⟩  intro ρ  dsimp [gen_k_server_uniform_expected_cost]  rw [gen_k_server_uniform_one_server_competitive_one_expected_cost_from,      gen_k_server_uniform_one_server_competitive_one_opt_eq_path_cost]
See it in the graphDiscuss this resultChallenge it