not_threshold_schedule_competitive_ratio_two
The statement threshold_schedule_competitive_ratio_two is false: The reset price K : ℝ is unrestricted, and for negative K the claim fails. Take T = 2, a ≡ 0 : Fin 1 → NNReal, K = -1, and the schedule r ≡ true.
- schedule_history 2 a r 0 = 0 and schedule_history 2 a r 1 = 0 (the increment is 0), so
rent_or_buy_cost 2 a (-1) (fun _ => true) = (0 + (-1)) + (0 + (-1)) = -2.
- The threshold state starts at (0,0), so at t = 0 the rule buys iff -1 ≤ 0, i.e. true; then the state at t = 1 is (a 0, 0) = (0,0) and it again buys. Hence threshold_schedule 2 a (-1) ≡ true and
rent_or_buy_cost 2 a (-1) (threshold_schedule 2 a (-1)) = -2.
The required inequality then reads -2 ≤ 2 * (-2) = -4, which is false. This is counterexample to the theorem with no hypothesis on the sign of K; the published Proposition presumably assumes the reset price is nonnegative. I have verified ¬ (∀ T a K r, rent_or_buy_cost T a K (threshold_schedule T a K) ≤ 2 * rent_or_buy_cost T a K r) in Lean.
Statement
theorem not_threshold_schedule_competitive_ratio_two : ¬ (∀ (T : ℕ) (a : Fin (T - 1) → NNReal) (K : ℝ)
(r : Fin T → Bool), rent_or_buy_cost T a K (threshold_schedule T a K) ≤ 2 * rent_or_buy_cost T a K r)- Related work
- refutes `threshold_schedule_competitive_ratio_two`
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- threshold_stateGiven horizon T : ℕ, increments a : Fin (T - 1) → NNReal, and reset price K : ℝ, threshold_state T a K : Fin T → NNReal × NNReal is…
- schedule_historyGiven a horizon T : ℕ, increments a : Fin (T - 1) → NNReal, and a schedule r : Fin T → Bool, schedule_history T a r : Fin T → NNReal is…
- rent_or_buy_costGiven horizon T : ℕ, increments a : Fin (T - 1) → NNReal, reset price K : ℝ, and a schedule r : Fin T → Bool, rent_or_buy_cost T a K r : ℝ…
- threshold_scheduleGiven horizon T : ℕ, increments a : Fin (T - 1) → NNReal, reset price K : ℝ, and call t : Fin T, threshold_schedule T a K t : Bool is…
The proof, explained
The theorem refutes the claim that the threshold schedule is 2-competitive by providing an explicit counterexample when the reset price K is allowed to be negative. Assuming for contradiction that the inequality holds universally, we specialize to horizon T = 2, zero increments a = 0, reset price K = -1, and the schedule r that buys at every step. On this instance, both the reference schedule r and the threshold schedule buy at both steps, each incurring a total cost of -2. The competitive ratio bound would then require -2 ≤ 2 * (-2) = -4, which is impossible.
Assuming the 2-competitive ratio holds universally, it must hold for horizon T = 2, increments a ≡ 0, reset price K = -1, and the constant schedule r ≡ true.
We assume for contradiction that the 2-competitive bound holds for all instances. Specializing the universal quantifier to horizon T = 2, cost increments identically 0, negative reset price K = -1, and the schedule r that buys at every step produces an inequality between the threshold schedule cost and twice the cost of r.
intro h have hh := h 2 (fun _ => (0 : NNReal)) (-1) (fun _ => true)
The cost of the constant-true schedule on this counterexample instance is -2.
Using rent_or_buy_cost.eq_def and Fin.sum_univ_two, the total cost expands to the sum over t = 0 and t = 1. Applying schedule_history.eq_def shows that the history cost is 0 at both steps, while buying at each step adds K = -1, resulting in (0 + (-1)) + (0 + (-1)) = -2.
uses
rent_or_buy_cost.eq_def,Fin.sum_univ_two,schedule_history.eq_defhave e1 : rent_or_buy_cost 2 (fun _ => (0 : NNReal)) (-1) (fun _ => true) = -2 := by rw [rent_or_buy_cost.eq_def] simp only [Fin.sum_univ_two] rw [schedule_history.eq_def, schedule_history.eq_def] norm_num
The cost of the threshold schedule on this counterexample instance is also -2.
We again expand the cost sum over the two time steps using rent_or_buy_cost.eq_def, Fin.sum_univ_two, and schedule_history.eq_def. Unfolding threshold_schedule.eq_def and threshold_state.eq_def, the state starts at (0, 0), so at t = 0 the threshold condition -1 ≤ 0 holds and the algorithm buys. At t = 1, the state transitions to (a(0), 0) = (0, 0), so it buys again. Incurring K = -1 at each step with 0 history gives a total cost of -2.
uses
rent_or_buy_cost.eq_def,Fin.sum_univ_two,schedule_history.eq_def,threshold_schedule.eq_def,threshold_state.eq_defhave e2 : rent_or_buy_cost 2 (fun _ => (0 : NNReal)) (-1) (threshold_schedule 2 (fun _ => (0 : NNReal)) (-1)) = -2 := by rw [rent_or_buy_cost.eq_def] simp only [Fin.sum_univ_two] rw [schedule_history.eq_def, schedule_history.eq_def] norm_num [threshold_schedule.eq_def, threshold_state.eq_def]
A contradiction is reached, refuting the universal 2-competitiveness claim.
Substituting the computed costs of -2 into the specialized inequality yields -2 ≤ 2 * (-2) = -4, which is false by elementary arithmetic.
rw [e1, e2] at hh norm_num at hh
Fin.sum_univ_two- A sum over the two-element type Fin 2 decomposes into the sum of the term at 0 and the term at 1.
rent_or_buy_cost.eq_def- The total cost under a schedule is defined as the sum over all time steps t of the accumulated history cost plus K if the schedule buys at step t (and 0 otherwise).
schedule_history.eq_def- The accumulated history cost is 0 at time 0; at time t + 1, it is a(t) if the schedule bought at time t, and the previous history plus a(t) otherwise.
threshold_schedule.eq_def- The threshold policy buys at time t if and only if K is at most the sum of the accumulated cost and current increment in the threshold state at time t.
threshold_state.eq_def- The threshold tracking state starts at (0, 0) at time 0; at step t + 1, it resets to (a(t), 0) if K is at most the sum of the accumulated cost and increment, and updates to (h + a(t), acc + h) otherwise.
- The original proposition in the literature assumes the reset price is nonnegative ($K \ge 0$). Without that hypothesis, taking $K = -1$ makes buying yield a negative cost (a reward), which reverses the expected direction of the competitive inequality.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem not_threshold_schedule_competitive_ratio_two : ¬ (∀ (T : ℕ) (a : Fin (T - 1) → NNReal) (K : ℝ) (r : Fin T → Bool), rent_or_buy_cost T a K (threshold_schedule T a K) ≤ 2 * rent_or_buy_cost T a K r) := by intro h have hh := h 2 (fun _ => (0 : NNReal)) (-1) (fun _ => true) have e1 : rent_or_buy_cost 2 (fun _ => (0 : NNReal)) (-1) (fun _ => true) = -2 := by rw [rent_or_buy_cost.eq_def] simp only [Fin.sum_univ_two] rw [schedule_history.eq_def, schedule_history.eq_def] norm_num have e2 : rent_or_buy_cost 2 (fun _ => (0 : NNReal)) (-1) (threshold_schedule 2 (fun _ => (0 : NNReal)) (-1)) = -2 := by rw [rent_or_buy_cost.eq_def] simp only [Fin.sum_univ_two] rw [schedule_history.eq_def, schedule_history.eq_def] norm_num [threshold_schedule.eq_def, threshold_state.eq_def] rw [e1, e2] at hh norm_num at hh