probabilistic_serial_line_item_wait_exists_eq_zero
For n >= 1 items, some item has waiting cost 0 in the probabilistic serial procedure: an item still unfinished at the start of the last phase in which some item is unfinished is never counted.
Statement
theorem probabilistic_serial_line_item_wait_exists_eq_zero {n : ℕ} (hn : 1 ≤ n) (b : Fin n → ℝ)
(pref : Fin n → Equiv.Perm (Fin n)) :
∃ j, probabilistic_serial_line_item_wait b pref j = 0- Source
- Reduction step for OP-1158 (probabilistic serial on the line, PS <= n*OPT); reduction found 2026-11-07 for IN-608, experiments 17916, 17917
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- probabilistic_serial_line_item_waitThe waiting cost of item j in the probabilistic serial procedure, items at real positions b: the integral, over the times t in [0,1] after…
- probabilistic_serial_phase_stateThe state of the probabilistic serial (simultaneous eating) procedure for n agents and n unit-capacity items with rankings pref after its…
- probabilistic_serial_phaseOne phase of the simultaneous-eating (probabilistic serial) procedure for n agents and n items. Agent i's ranking is the permutation pref…
- probabilistic_serial_phase_lengthThe duration of phase k of the probabilistic serial procedure (k = 0, 1, ...): the total remaining item capacity before the phase minus…
- Used by 1
- probabilistic_serial_line_distortion_le_of_item_wait_leIf on an instance (agents at a, items at b, distance rankings pref) every item's waiting cost is at most OPT, then the probabilistic…
The proof, explained
First, a single phase of the probabilistic serial algorithm preserves non-negativity and weakly decreases remaining item amounts, which by induction implies that remaining amounts are non-negative and monotonically non-increasing across all phases. Next, let K be the latest phase index up to n - 1 at which at least one item remains unfinished, and pick an item j that is still unfinished at phase K. For any phase k < n, the waiting cost condition requires that j is already finished while some other item remains unfinished. This is impossible: if k ≤ K, item j has not finished yet by monotonicity, and if k > K, no items remain unfinished by maximality of K; hence, every term in the waiting cost sum vanishes.
Unfold the phase transition definition and case-split on whether any item is currently being eaten.
By unfolding probabilistic_serial_phase and simplifying, S is defined as the set of items that at least one agent wants to eat. We then split into cases depending on whether S is nonempty.
classical unfold probabilistic_serial_phase simp only set S := Finset.univ.filter (fun j => 0 < (Finset.univ.filter (fun i => 0 < s.1 j ∧ ∀ j', 0 < s.1 j' → (pref i).symm j ≤ (pref i).symm j')).card) with hS split_ifs with h
When items are being eaten, the phase duration and the consumption rate for item j are non-negative.
Let c(j) be the count of agents eating item j. The phase duration t is the minimum of s.1 k / c(k) over k ∈ S; since each remaining amount s.1 k is non-negative and c(k) ≥ 0, by Finset.le_inf'_iff and div_nonneg, t is non-negative. The count c(j) is also non-negative by Nat.cast_nonneg.
uses
Finset.le_inf'_iff,div_nonneg,Nat.cast_nonneg· set c : Fin n → ℕ := fun j => (Finset.univ.filter (fun i => 0 < s.1 j ∧ ∀ j', 0 < s.1 j' → (pref i).symm j ≤ (pref i).symm j')).card with hc have ht0 : 0 ≤ S.inf' h (fun j => s.1 j / (c j : ℝ)) := by rw [Finset.le_inf'_iff] intro k _ exact div_nonneg (hs k) (Nat.cast_nonneg _) have hcn : (0 : ℝ) ≤ (c j : ℝ) := Nat.cast_nonneg _
If item j is being eaten, its remaining amount after the phase is non-negative.
When j ∈ S, the phase duration t is at most s.1 j / c(j) by Finset.inf'_le, and c(j) > 0. Multiplying through by c(j) via le_div_iff₀ gives t * c(j) ≤ s.1 j, so the updated amount s.1 j - t * c(j) is non-negative.
uses
Finset.inf'_le,Finset.mem_filter.mp,le_div_iff₀constructor · by_cases hj : j ∈ S · have hle := Finset.inf'_le (fun j => s.1 j / (c j : ℝ)) hj have hpos : (0 : ℝ) < c j := by have := (Finset.mem_filter.mp hj).2 exact_mod_cast this have := (le_div_iff₀ hpos).mp hle show 0 ≤ s.1 j - S.inf' h (fun j => s.1 j / (c j : ℝ)) * (c j : ℝ) linarith
If item j is not being eaten, its consumption rate is zero and its remaining amount stays non-negative.
When j ∉ S, no agent eats j, so c(j) = 0 (by contradiction using Finset.mem_filter.mpr, Finset.mem_univ, and Nat.pos_of_ne_zero). The updated amount is then simply s.1 j, which is non-negative by hypothesis.
uses
Finset.mem_filter.mpr,Finset.mem_univ,Nat.pos_of_ne_zero· have h0 : c j = 0 := by by_contra hne exact hj (Finset.mem_filter.mpr ⟨Finset.mem_univ _, Nat.pos_of_ne_zero hne⟩) show 0 ≤ s.1 j - S.inf' h (fun j => s.1 j / (c j : ℝ)) * (c j : ℝ) rw [h0]; simp [hs j]
The remaining amount of item j after the phase is at most its amount before the phase. automation
Since the phase duration t and the consumption count c(j) are non-negative, their product t * c(j) is non-negative, so s.1 j - t * c(j) ≤ s.1 j, established by non-linear arithmetic.
· show s.1 j - S.inf' h (fun j => s.1 j / (c j : ℝ)) * (c j : ℝ) ≤ s.1 j nlinarith
If no items are being eaten, remaining amounts are unchanged and satisfy both bounds. automation
When S is empty, the phase duration is 0, so remaining amounts do not change, trivially satisfying 0 ≤ s.1 j ≤ s.1 j.
· simp [hs j]The remaining amount of every item is non-negative at every phase step k.
By induction on the phase index k. At step 0, all items start with remaining amount 1, which is non-negative. In the inductive step, applying ps_wait_zero_phase_fst_le_and_nonneg shows that one phase preserves non-negativity.
uses
ps_wait_zero_phase_fst_le_and_nonneg,Function.iterate_succ_apply'classical have hnn : ∀ k, ∀ j, 0 ≤ (probabilistic_serial_phase_state n pref k).1 j := by intro k induction k with | zero => intro j; simp [probabilistic_serial_phase_state] | succ k ih => intro j have := (ps_wait_zero_phase_fst_le_and_nonneg n pref _ ih j).1 simpa [probabilistic_serial_phase_state, Function.iterate_succ_apply'] using this
The remaining amount of each item weakly decreases in each phase step.
Applying ps_wait_zero_phase_fst_le_and_nonneg with the non-negativity established in the previous step shows that the remaining amount after step k + 1 is at most that at step k.
uses
ps_wait_zero_phase_fst_le_and_nonneg,Function.iterate_succ_apply'have hstep : ∀ k j, (probabilistic_serial_phase_state n pref (k + 1)).1 j ≤ (probabilistic_serial_phase_state n pref k).1 j := by intro k j have := (ps_wait_zero_phase_fst_le_and_nonneg n pref _ (hnn k) j).2 simpa [probabilistic_serial_phase_state, Function.iterate_succ_apply'] using this
The remaining amount of each item is monotonically non-increasing across phases.
By induction on m ≥ k using Nat.le_induction: the base case m = k is reflexive (le_rfl), and the inductive step transitivity combines the one-step decrease with the induction hypothesis.
uses
Nat.le_induction,le_rflhave hmono : ∀ k m, k ≤ m → ∀ j, (probabilistic_serial_phase_state n pref m).1 j ≤ (probabilistic_serial_phase_state n pref k).1 j := by intro k m hkm j induction m, hkm using Nat.le_induction with | base => exact le_rfl | succ m _ ih => exact (hstep m j).trans ih
There exists an item j that has strictly positive remaining amount at the last phase K ≤ n - 1 where some item is unfinished.
Let P(k) be the property that some item is unfinished at phase k. At phase 0, all items have amount 1 > 0 and n ≥ 1, so P(0) holds. Taking K to be the greatest index ≤ n - 1 satisfying P via Nat.findGreatest, P(K) holds, which provides an item j with remaining amount strictly positive at phase K.
uses
Nat.findGreatest_spec,Nat.zero_le,Finset.mem_filter.mplet P : ℕ → Prop := fun k => (Finset.univ.filter (fun j' => 0 < (probabilistic_serial_phase_state n pref k).1 j')).Nonempty have hP0 : P 0 := ⟨⟨0, hn⟩, by simp [probabilistic_serial_phase_state]⟩ set K := Nat.findGreatest P (n - 1) with hK have hPK : P K := Nat.findGreatest_spec (P := P) (Nat.zero_le _) hP0 obtain ⟨j, hj⟩ := hPK have hjpos : 0 < (probabilistic_serial_phase_state n pref K).1 j := (Finset.mem_filter.mp hj).2
To show that item j has waiting cost 0, it suffices to show that for every phase k < n, the waiting condition is violated.
Unfolding probabilistic_serial_line_item_wait, the total waiting cost is a sum over k < n. By Finset.sum_eq_zero, it suffices to show each term is 0. Each term is an if-then-else whose condition requires both that item j is already finished at phase k (amount ≤ 0) and that some item remains unfinished (P(k)). By dif_neg, each term vanishes once we show that this conjunction is impossible.
uses
Finset.sum_eq_zero,dif_negrefine ⟨j, ?_⟩ unfold probabilistic_serial_line_item_wait apply Finset.sum_eq_zero intro k hk rw [dif_neg] rintro ⟨h1, h2⟩
If k ≤ K, item j cannot be finished at phase k.
If k ≤ K, monotonicity implies that the remaining amount of j at phase K is at most that at phase k. But j has strictly positive amount at phase K, so its amount at phase k cannot be ≤ 0.
uses
le_or_gtrcases le_or_gt k K with hkK | hkK · have := hmono k K hkK j linarith
If k > K, no item remains unfinished at phase k, so the second condition fails. automation
Since k is in range n, k < n so k ≤ n - 1 by linear arithmetic. Because k > K and K is the greatest index ≤ n - 1 satisfying P, Nat.findGreatest_is_greatest implies that P(k) cannot hold, contradicting the second condition.
uses
Finset.mem_range.mp,Nat.findGreatest_is_greatest· have hkn : k ≤ n - 1 := by have := Finset.mem_range.mp hk; omega exact Nat.findGreatest_is_greatest hkK hkn h2
Finset.le_inf'_iff- A value is bounded above by the infimum of a nonempty finite set under f if and only if it is bounded above by f(b) for all b in the set.
div_nonneg- The quotient of two non-negative numbers is non-negative.
Nat.cast_nonneg- The coercion of any natural number into an ordered ring is non-negative.
Finset.inf'_le- The infimum of a nonempty finite set under a function is less than or equal to the function's value at any element of the set.
Finset.mem_filter.mp- An element belongs to a filtered finite set only if it belongs to the base set and satisfies the filter predicate.
le_div_iff₀- For a strictly positive divisor, a ≤ b / c if and only if a * c ≤ b.
Finset.mem_filter.mpr- An element of a set satisfying a predicate belongs to the set filtered by that predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set.
Nat.pos_of_ne_zero- A non-zero natural number is strictly positive.
ps_wait_zero_phase_fst_le_and_nonneg- One phase of the probabilistic serial procedure preserves non-negativity of remaining amounts and does not increase them.
Function.iterate_succ_apply'- Applying n + 1 iterations of a function f to x is equal to applying f to the result of n iterations of f on x.
Nat.le_induction- Induction principle for natural numbers starting from a base m: if P(m) holds and P(n) implies P(n+1) for all n ≥ m, then P(n) holds for all n ≥ m.
le_rfl- Any element in a preorder is less than or equal to itself.
Nat.findGreatest_spec- If a predicate P holds for some natural number m ≤ n, then P holds for the greatest natural number ≤ n satisfying P.
Nat.zero_le- Zero is less than or equal to any natural number.
Finset.sum_eq_zero- If every term in a finite sum is zero, then the sum is zero.
dif_neg- A dependent conditional whose condition is false evaluates to the else branch.
le_or_gt- In any linear order, either a ≤ b or b < a.
Finset.mem_range.mp- An element of Finset.range n is strictly less than n.
Nat.findGreatest_is_greatest- Any natural number strictly between the greatest witness ≤ n and n does not satisfy P.
- Non-linear arithmetic (`nlinarith`) closes the monotonicity of remaining amounts after one phase, and Presburger arithmetic (`omega`) closes the index bound k ≤ n - 1.
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 ps_wait_zero_phase_fst_le_and_nonneg (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (hs : ∀ j, 0 ≤ s.1 j) (j : Fin n) : 0 ≤ (probabilistic_serial_phase n pref s).1 j ∧ (probabilistic_serial_phase n pref s).1 j ≤ s.1 j := by classical unfold probabilistic_serial_phase simp only set S := Finset.univ.filter (fun j => 0 < (Finset.univ.filter (fun i => 0 < s.1 j ∧ ∀ j', 0 < s.1 j' → (pref i).symm j ≤ (pref i).symm j')).card) with hS split_ifs with h · set c : Fin n → ℕ := fun j => (Finset.univ.filter (fun i => 0 < s.1 j ∧ ∀ j', 0 < s.1 j' → (pref i).symm j ≤ (pref i).symm j')).card with hc have ht0 : 0 ≤ S.inf' h (fun j => s.1 j / (c j : ℝ)) := by rw [Finset.le_inf'_iff] intro k _ exact div_nonneg (hs k) (Nat.cast_nonneg _) have hcn : (0 : ℝ) ≤ (c j : ℝ) := Nat.cast_nonneg _ constructor · by_cases hj : j ∈ S · have hle := Finset.inf'_le (fun j => s.1 j / (c j : ℝ)) hj have hpos : (0 : ℝ) < c j := by have := (Finset.mem_filter.mp hj).2 exact_mod_cast this have := (le_div_iff₀ hpos).mp hle show 0 ≤ s.1 j - S.inf' h (fun j => s.1 j / (c j : ℝ)) * (c j : ℝ) linarith · have h0 : c j = 0 := by by_contra hne exact hj (Finset.mem_filter.mpr ⟨Finset.mem_univ _, Nat.pos_of_ne_zero hne⟩) show 0 ≤ s.1 j - S.inf' h (fun j => s.1 j / (c j : ℝ)) * (c j : ℝ) rw [h0]; simp [hs j] · show s.1 j - S.inf' h (fun j => s.1 j / (c j : ℝ)) * (c j : ℝ) ≤ s.1 j nlinarith · simp [hs j]theorem probabilistic_serial_line_item_wait_exists_eq_zero {n : ℕ} (hn : 1 ≤ n) (b : Fin n → ℝ) (pref : Fin n → Equiv.Perm (Fin n)) : ∃ j, probabilistic_serial_line_item_wait b pref j = 0 := by classical have hnn : ∀ k, ∀ j, 0 ≤ (probabilistic_serial_phase_state n pref k).1 j := by intro k induction k with | zero => intro j; simp [probabilistic_serial_phase_state] | succ k ih => intro j have := (ps_wait_zero_phase_fst_le_and_nonneg n pref _ ih j).1 simpa [probabilistic_serial_phase_state, Function.iterate_succ_apply'] using this have hstep : ∀ k j, (probabilistic_serial_phase_state n pref (k + 1)).1 j ≤ (probabilistic_serial_phase_state n pref k).1 j := by intro k j have := (ps_wait_zero_phase_fst_le_and_nonneg n pref _ (hnn k) j).2 simpa [probabilistic_serial_phase_state, Function.iterate_succ_apply'] using this have hmono : ∀ k m, k ≤ m → ∀ j, (probabilistic_serial_phase_state n pref m).1 j ≤ (probabilistic_serial_phase_state n pref k).1 j := by intro k m hkm j induction m, hkm using Nat.le_induction with | base => exact le_rfl | succ m _ ih => exact (hstep m j).trans ih let P : ℕ → Prop := fun k => (Finset.univ.filter (fun j' => 0 < (probabilistic_serial_phase_state n pref k).1 j')).Nonempty have hP0 : P 0 := ⟨⟨0, hn⟩, by simp [probabilistic_serial_phase_state]⟩ set K := Nat.findGreatest P (n - 1) with hK have hPK : P K := Nat.findGreatest_spec (P := P) (Nat.zero_le _) hP0 obtain ⟨j, hj⟩ := hPK have hjpos : 0 < (probabilistic_serial_phase_state n pref K).1 j := (Finset.mem_filter.mp hj).2 refine ⟨j, ?_⟩ unfold probabilistic_serial_line_item_wait apply Finset.sum_eq_zero intro k hk rw [dif_neg] rintro ⟨h1, h2⟩ rcases le_or_gt k K with hkK | hkK · have := hmono k K hkK j linarith · have hkn : k ≤ n - 1 := by have := Finset.mem_range.mp hk; omega exact Nat.findGreatest_is_greatest hkK hkn h2