AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_line_item_wait_exists_eq_zero

theoremverified

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

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.

  1. 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.

    lines 4–9

      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
  2. 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.

    lines 10–16

    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 _
  3. 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.

    lines 17–25

    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
  4. 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.

    lines 26–30

    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]
  5. 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.

    lines 31–32

        · show s.1 j - S.inf' h (fun j => s.1 j / (c j : ℝ)) * (c j : ℝ) ≤ s.1 j
          nlinarith
  6. 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.

    line 33

      · simp [hs j]
  7. 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.

    lines 38–46

    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
  8. 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.

    lines 47–51

    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
  9. 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.

    lines 52–57

    uses Nat.le_induction, le_rfl

      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
  10. 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.

    lines 58–64

    uses Nat.findGreatest_spec, Nat.zero_le, Finset.mem_filter.mp

      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
  11. 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.

    lines 65–70

    uses Finset.sum_eq_zero, dif_neg

      refine ⟨j, ?_⟩
      unfold probabilistic_serial_line_item_wait
      apply Finset.sum_eq_zero
      intro k hk
      rw [dif_neg]
      rintro ⟨h1, h2⟩
  12. 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.

    lines 71–73

    uses le_or_gt

      rcases le_or_gt k K with hkK | hkK
      · have := hmono k K hkK j
        linarith
  13. 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.

    lines 74–76

    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.

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

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
See it in the graphDiscuss this resultChallenge it