AFTD Auto-Formalizing Theoretical Domains

nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio

theoremverifiedformalization

Let n be a natural number and let x, a, z : Fin n → ℝ with x = a + z, where a and z have non-negative coordinates (∀ i, 0 ≤ a i and ∀ i, 0 ≤ z i). Suppose an algorithm accumulates non-negative cost C_T ≥ 0 by time T and incurs total completion cost alg_cost ≤ C_T + (2 * n / (n + 1)) * nonclairvoyant_scheduling_offline_opt z by running Round-Robin after time T. If nonclairvoyant_scheduling_offline_opt a > 0, then the competitive ratio satisfies alg_cost / nonclairvoyant_scheduling_offline_opt x ≤ max (C_T / nonclairvoyant_scheduling_offline_opt a) (2 * (n : ℝ) / ((n : ℝ) + 1)).

Statement

theorem nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio
    {n : ℕ} (x a z : Fin n → ℝ)
    (hxz : x = a + z)
    (ha : ∀ i, 0 ≤ a i)
    (hz : ∀ i, 0 ≤ z i)
    (C_T : ℝ) (hC_T : 0 ≤ C_T) (alg_cost : ℝ)
    (h_alg : alg_cost ≤ C_T + (2 * (n : ℝ) / ((n : ℝ) + 1)) * nonclairvoyant_scheduling_offline_opt z)
    (h_opt_a : 0 < nonclairvoyant_scheduling_offline_opt a) :
    alg_cost / nonclairvoyant_scheduling_offline_opt x ≤
      max (C_T / nonclairvoyant_scheduling_offline_opt a) (2 * (n : ℝ) / ((n : ℝ) + 1))
Formalizes
arXiv:2610.29037 Lemma 4.2
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

Read back from the Lean

For any natural number $n$, vectors $x, a, z : \text{Fin } n \to \mathbb{R}$, and real numbers $C_T$ and $\text{alg\_cost}$, suppose that: 1. $x = a + z$ (pointwise), 2. $a(i) \ge 0$ for all $i \in \text{Fin } n$, 3. $z(i) \ge 0$ for all $i \in \text{Fin } n$, 4. $C_T \ge 0$, 5. $\text{alg\_cost} \le C_T + \left(\frac{2n}{n + 1}\right) \cdot \text{offline\_opt}(z)$, and 6. $0 < \text{offline\_opt}(a)$, where $\text{offline\_opt}(w)$ denotes nonclairvoyant_scheduling_offline_opt applied to $w$. Then: $$\frac{\text{alg\_cost}}{\text{offline\_opt}(x)} \le \max\left(\frac{C_T}{\text{offline\_opt}(a)}, \, \frac{2n}{n + 1}\right).$$

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

The proof, explained

The proof first establishes that offline opt is non-negative on non-negative vectors. It then uses the superadditivity of offline opt to lower bound opt(x) by opt(a) + opt(z). Together with the given upper bound on the algorithm's cost, this bounds the ratio by (C_T + rho * opt(z)) / (opt(a) + opt(z)), which is at most max(C_T / opt(a), rho) by a standard mediant inequality.

  1. opt(z) is non-negative

    Each term in the sum defining opt(z) is a product of non-negative terms.

    lines 4–10

      unfold nonclairvoyant_scheduling_offline_opt
      refine Finset.le_inf' _ _ (fun π _ => ?_)
      refine Finset.sum_nonneg (fun i _ => ?_)
      have hi : (i : ℝ) ≤ (n : ℝ) := by
        exact le_of_lt (Nat.cast_lt.mpr i.isLt)
      have h_diff : 0 ≤ (n : ℝ) - (i : ℝ) := sub_nonneg.mpr hi
      exact mul_nonneg h_diff (hz (π i))
  2. The competitive ratio bound holds.

    We bound alg_cost / opt(x) by (C_T + rho * opt(z)) / (opt(a) + opt(z)) and apply ratio_add_le_max_of_nonneg.

    lines 23–46

      set rho := 2 * (n : ℝ) / ((n : ℝ) + 1)
      have hz_nonneg : 0 ≤ nonclairvoyant_scheduling_offline_opt z :=
        nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio_opt_nonneg z hz
      have h_super : nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z ≤
          nonclairvoyant_scheduling_offline_opt x := by
        have hs := nonclairvoyant_scheduling_offline_opt_superadditive a z
        rw [hxz]
        exact hs
      have h_rho_nonneg : 0 ≤ rho := by
        dsimp [rho]
        refine div_nonneg ?_ ?_
        · positivity
        · positivity
      have hc_nonneg : 0 ≤ C_T + rho * nonclairvoyant_scheduling_offline_opt z := by
        refine add_nonneg hC_T (mul_nonneg h_rho_nonneg hz_nonneg)
      have hd_pos : 0 < nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z :=
        add_pos_of_pos_of_nonneg h_opt_a hz_nonneg
      have h_div : alg_cost / nonclairvoyant_scheduling_offline_opt x ≤
          (C_T + rho * nonclairvoyant_scheduling_offline_opt z) /
            (nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z) :=
        div_le_div₀ hc_nonneg h_alg hd_pos h_super
      have h_ratio := ratio_add_le_max_of_nonneg C_T (nonclairvoyant_scheduling_offline_opt a)
        (nonclairvoyant_scheduling_offline_opt z) rho h_opt_a hz_nonneg
      exact le_trans h_div h_ratio

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

lemma nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio_opt_nonneg    {n : ℕ} (z : Fin n → ℝ) (hz : ∀ i, 0 ≤ z i) :    0 ≤ nonclairvoyant_scheduling_offline_opt z := by  unfold nonclairvoyant_scheduling_offline_opt  refine Finset.le_inf' _ _ (fun π _ => ?_)  refine Finset.sum_nonneg (fun i _ => ?_)  have hi : (i : ℝ) ≤ (n : ℝ) := by    exact le_of_lt (Nat.cast_lt.mpr i.isLt)  have h_diff : 0 ≤ (n : ℝ) - (i : ℝ) := sub_nonneg.mpr hi  exact mul_nonneg h_diff (hz (π i))/-- Robustness reduction to error-detection time for Round-Robin hybrid schedules. -/theorem nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio    {n : ℕ} (x a z : Fin n → ℝ)    (hxz : x = a + z)    (ha : ∀ i, 0 ≤ a i)    (hz : ∀ i, 0 ≤ z i)    (C_T : ℝ) (hC_T : 0 ≤ C_T) (alg_cost : ℝ)    (h_alg : alg_cost ≤ C_T + (2 * (n : ℝ) / ((n : ℝ) + 1)) * nonclairvoyant_scheduling_offline_opt z)    (h_opt_a : 0 < nonclairvoyant_scheduling_offline_opt a) :    alg_cost / nonclairvoyant_scheduling_offline_opt x ≤      max (C_T / nonclairvoyant_scheduling_offline_opt a) (2 * (n : ℝ) / ((n : ℝ) + 1)) := by  set rho := 2 * (n : ℝ) / ((n : ℝ) + 1)  have hz_nonneg : 0 ≤ nonclairvoyant_scheduling_offline_opt z :=    nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio_opt_nonneg z hz  have h_super : nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z ≤      nonclairvoyant_scheduling_offline_opt x := by    have hs := nonclairvoyant_scheduling_offline_opt_superadditive a z    rw [hxz]    exact hs  have h_rho_nonneg : 0 ≤ rho := by    dsimp [rho]    refine div_nonneg ?_ ?_    · positivity    · positivity  have hc_nonneg : 0 ≤ C_T + rho * nonclairvoyant_scheduling_offline_opt z := by    refine add_nonneg hC_T (mul_nonneg h_rho_nonneg hz_nonneg)  have hd_pos : 0 < nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z :=    add_pos_of_pos_of_nonneg h_opt_a hz_nonneg  have h_div : alg_cost / nonclairvoyant_scheduling_offline_opt x ≤      (C_T + rho * nonclairvoyant_scheduling_offline_opt z) /        (nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z) :=    div_le_div₀ hc_nonneg h_alg hd_pos h_super  have h_ratio := ratio_add_le_max_of_nonneg C_T (nonclairvoyant_scheduling_offline_opt a)    (nonclairvoyant_scheduling_offline_opt z) rho h_opt_a hz_nonneg  exact le_trans h_div h_ratio
See it in the graphDiscuss this resultChallenge it