AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_line_cost_le_add_item_wait

theoremverified

For n agents at real positions a and n items at real positions b, each agent ranking the items by distance (ties broken arbitrarily), the probabilistic serial cost is at most OPT (the minimum perfect-matching cost) plus the sum over items of their waiting costs.

Statement

theorem probabilistic_serial_line_cost_le_add_item_wait {n : ℕ} (a b : Fin n → ℝ)
    (pref : Fin n → Equiv.Perm (Fin n)) (h : is_line_distance_preference_profile a b pref) :
    probabilistic_serial_line_cost a b pref ≤
      line_min_matching_cost a b + ∑ j, probabilistic_serial_line_item_wait b pref j
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 8
  • probabilistic_serial_line_costThe cost of the probabilistic serial assignment X for agents at a and items at b on the real line: PS = sum over agents i and items j of…
  • line_min_matching_costOPT: the minimum, over all permutations sigma of the n items, of the matching cost sum_i |a_i - b_{sigma(i)}|.
  • is_line_distance_preference_profileThere are n agents and n items, both indexed by {0, ..., n-1}; agent i sits at the real position a_i and item j at b_j. Each agent's…
  • 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_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_fractional_assignmentThe probabilistic serial rule for n agents and n unit-capacity items with strict rankings pref: starting from capacities 1 and nothing…
  • 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_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

The proof decomposes the continuous probabilistic serial allocation into n discrete phases and compares the cost incurred in each phase against an optimal matching permutation σ. In any phase, an agent eating item j incurs a cost bounded by the distance to σ(i) if σ(i) is still available, or by |a_i - b_{σ(i)}| plus the distance from b_{σ(i)} to the nearest available item if σ(i) has already been exhausted. Summing over all agents and phases, the matching distances scale by the sum of phase durations (which is at most 1), yielding OPT, while the exhausted-item terms sum to the items' waiting costs.

  1. A single phase of the probabilistic serial algorithm preserves the non-negativity of remaining item capacities and weakly decreases them.

    Unfolding the definition of a phase, the phase duration is t = min_{j ∈ S} (s_1(j) / c(j)), where S is the set of items currently being eaten and c(j) > 0 is the number of eaters of item j. If no items are being eaten (S is empty), capacities remain unchanged. Otherwise, t ≥ 0 since capacities and counts are non-negative. For each item j, if j ∈ S then t ≤ s_1(j) / c(j), so t * c(j) ≤ s_1(j) and the new capacity s_1(j) - t * c(j) is non-negative. If j ∉ S then c(j) = 0, so the capacity is unchanged and non-negative. Finally, subtracting t * c(j) with t ≥ 0 and c(j) ≥ 0 shows that the capacity weakly decreases.

    lines 4–33

    uses Finset.le_inf'_iff, Finset.inf'_le, le_div_iff₀

      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]
  2. The definition of probabilistic_serial_phase agrees with the explicit formulas using ps_wait_eats and ps_wait_time.

    The phase update in terms of remaining capacities and fractional assignments is definitionally equal to the explicit expressions defined via ps_wait_eats and ps_wait_time, verified by reflexivity.

    lines 46–53

    theorem ps_wait_phase_eq (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))
        (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) :
        probabilistic_serial_phase n pref s =
          (open Classical in fun j => s.1 j - ps_wait_time n pref s *
              (Finset.univ.filter (fun i => ps_wait_eats n pref s i j)).card,
           open Classical in fun i j => s.2 i j + if ps_wait_eats n pref s i j then ps_wait_time n pref s else 0) := by
      rfl
    
  3. In any phase, each agent eats at most one item.

    If agent i eats both item j and item j', then by definition of eating the most-preferred available item, (pref i)^{-1}(j) ≤ (pref i)^{-1}(j') and (pref i)^{-1}(j') ≤ (pref i)^{-1}(j). By antisymmetry, the ranks are equal, and injectivity of the preference permutation implies j = j'.

    lines 54–60

    uses le_antisymm

    theorem ps_wait_eats_unique (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))
        (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (i j j' : Fin n)
        (h : ps_wait_eats n pref s i j) (h' : ps_wait_eats n pref s i j') : j = j' := by
      have h1 := h.2 j' h'.1
      have h2 := h'.2 j h.1
      exact (pref i).symm.injective (le_antisymm h1 h2)
    
  4. As long as at least one item has strictly positive remaining capacity, every agent eats some item.

    The set of items with strictly positive remaining capacity is finite and nonempty. Therefore, it has a minimum element with respect to agent i's preference ranking, which is the item agent i eats.

    lines 61–69

    uses Finset.exists_min_image

    theorem ps_wait_eats_exists (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))
        (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (hA : ∃ j, 0 < s.1 j) (i : Fin n) :
        ∃ j, ps_wait_eats n pref s i j := by
      classical
      have hne : (Finset.univ.filter (fun j => 0 < s.1 j)).Nonempty := by
        obtain ⟨j, hj⟩ := hA; exact ⟨j, by simp [hj]⟩
      obtain ⟨j, hj, hmin⟩ := Finset.exists_min_image _ (fun j => (pref i).symm j) hne
      refine ⟨j, (Finset.mem_filter.mp hj).2, fun j' hj' => hmin j' (by simp [hj'])⟩
    
  5. Under line-distance preferences, the item an agent eats is at least as close to the agent as any other currently available item.

    If agent i eats item j, then for any available item j', agent i ranks j weakly ahead of j'. If the ranking is strictly better, line-distance preferences guarantee |a_i - b_j| ≤ |a_i - b_{j'}|. If the ranks are equal, injectivity gives j = j', so the distances are trivially equal.

    lines 70–80

    uses lt_or_eq_of_le

    theorem ps_wait_eats_nearest {n : ℕ} (a b : Fin n → ℝ) (pref : Fin n → Equiv.Perm (Fin n))
        (hp : is_line_distance_preference_profile a b pref)
        (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (i j j' : Fin n)
        (h : ps_wait_eats n pref s i j) (hj' : 0 < s.1 j') : |a i - b j| ≤ |a i - b j'| := by
      have hle := h.2 j' hj'
      rcases lt_or_eq_of_le hle with hlt | heq
      · have := hp i _ _ hlt
        simpa using this
      · have : j = j' := (pref i).symm.injective heq
        rw [this]
    
  6. The sum of eater counts over all items equals the total number of agents n.

    Since every agent eats exactly one item, the total number of agent-item eating pairs is n when summed over agents. Swapping the order of coordinates provides a bijection between pairs (i, j) and (j, i), so summing over items also yields n.

    lines 81–104

    uses ps_wait_eats_exists, ps_wait_eats_unique, Finset.card_bij

    open Classical in
    theorem ps_wait_card_sum (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))
        (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (hA : ∃ j, 0 < s.1 j) :
        (∑ j, ((Finset.univ.filter (fun i => ps_wait_eats n pref s i j)).card : ℝ)) = n := by
      classical
      have : (∑ j, (Finset.univ.filter (fun i => ps_wait_eats n pref s i j)).card) = n := by
        rw [← Finset.card_sigma]
        have : ∀ i, (Finset.univ.filter (fun j => ps_wait_eats n pref s i j)).card = 1 := by
          intro i
          obtain ⟨j, hj⟩ := ps_wait_eats_exists n pref s hA i
          rw [Finset.card_eq_one]
          refine ⟨j, ?_⟩
          ext j'
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton]
          exact ⟨fun h' => ps_wait_eats_unique n pref s i j' j h' hj, fun e => e ▸ hj⟩
        calc _ = ∑ i : Fin n, (Finset.univ.filter (fun j => ps_wait_eats n pref s i j)).card := by
                rw [← Finset.card_sigma]
                refine Finset.card_bij (fun p _ => ⟨p.2, p.1⟩) ?_ ?_ ?_
                · intro p hp; simp at hp ⊢; exact hp
                · intro p _ q _ e; simp at e; ext <;> simp [e.1, e.2]
                · intro q hq; refine ⟨⟨q.2, q.1⟩, by simpa using hq, rfl⟩
          _ = n := by simp [this]
      exact_mod_cast this
    
  7. The duration of each phase is non-negative.

    When available items exist, the phase duration is the minimum of s_1(j) / c(j) over active items. Since capacities and eater counts are non-negative, each ratio is non-negative, and hence so is their minimum. If no items are active, the duration is 0, which is also non-negative.

    lines 105–115

    uses Finset.le_inf'_iff

    theorem ps_wait_time_nonneg (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))
        (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (hs : ∀ j, 0 ≤ s.1 j) : 0 ≤ ps_wait_time n pref s := by
      classical
      unfold ps_wait_time
      simp only
      split_ifs with h
      · rw [Finset.le_inf'_iff]
        intro k _
        exact div_nonneg (hs k) (Nat.cast_nonneg _)
      · exact le_rfl
    
  8. When items remain available, the phase cost can be compared against any matching permutation σ by reindexing the exhausted-item terms.

    Assuming at least one item has positive remaining capacity, the phase duration L is positive. We rewrite the indicator condition for exhausted items, factor out L, and reindex the sum of distances from b_m to available items using the permutation σ so that both sums run over agents i.

    lines 116–147

    uses Equiv.sum_comp

    open Classical in
    theorem ps_wait_phase_cost_le {n : ℕ} (a b : Fin n → ℝ) (pref : Fin n → Equiv.Perm (Fin n))
        (hp : is_line_distance_preference_profile a b pref)
        (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (σ : Equiv.Perm (Fin n)) (L : ℝ) (hL0 : 0 ≤ L)
        (hL : (∃ j, 0 < s.1 j) → L = ps_wait_time n pref s) :
        ∑ i, ∑ j, (if ps_wait_eats n pref s i j then ps_wait_time n pref s else 0) * |a i - b j| ≤
          L * ∑ i, |a i - b (σ i)| +
          ∑ m, (if h : s.1 m ≤ 0 ∧ (Finset.univ.filter (fun j' => 0 < s.1 j')).Nonempty
            then L * (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' h.2 (fun j' => |b m - b j'|)
            else 0) := by
      by_cases hA : ∃ j, 0 < s.1 j
      · have hLt := hL hA
        rw [← hLt]
        have hne : (Finset.univ.filter (fun j' => 0 < s.1 j')).Nonempty := by
          obtain ⟨j, hj⟩ := hA; exact ⟨j, by simp [hj]⟩
        have hrhs : ∀ m, (if h : s.1 m ≤ 0 ∧ (Finset.univ.filter (fun j' => 0 < s.1 j')).Nonempty
            then L * (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' h.2 (fun j' => |b m - b j'|)
            else 0) = L * (if h : s.1 m ≤ 0 then
              (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' hne (fun j' => |b m - b j'|) else 0) := by
          intro m
          by_cases hm : s.1 m ≤ 0
          · rw [dif_pos ⟨hm, hne⟩, dif_pos hm]
          · rw [dif_neg (fun h => hm h.1), dif_neg hm, mul_zero]
        simp_rw [hrhs]
        rw [← Finset.mul_sum, ← mul_add]
        have hσ : ∑ m, (if h : s.1 m ≤ 0 then
              (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' hne (fun j' => |b m - b j'|) else 0) =
            ∑ i, (if h : s.1 (σ i) ≤ 0 then
              (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' hne (fun j' => |b (σ i) - b j'|) else 0) :=
          (Equiv.sum_comp σ (fun m => if h : s.1 m ≤ 0 then
              (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' hne (fun j' => |b m - b j'|) else 0)).symm
        rw [hσ, ← Finset.sum_add_distrib, Finset.mul_sum]
  9. For each agent i, the distance to their eaten item is bounded by |a_i - b_{σ(i)}| plus the distance from b_{σ(i)} to the nearest available item.

    Agent i eats a unique item j_i, reducing the inner sum over items to a single term. If σ(i) is still available, agent i chose j_i over σ(i), so |a_i - b_{j_i}| ≤ |a_i - b_{σ(i)}|. If σ(i) is exhausted, let j' be the nearest available item to b_{σ(i)}. By the triangle inequality, |a_i - b_{j'}| ≤ |a_i - b_{σ(i)}| + |b_{σ(i)} - b_{j'}|. Since j' is available, agent i's chosen item satisfies |a_i - b_{j_i}| ≤ |a_i - b_{j'}|, establishing the inequality.

    lines 148–165

    uses Finset.sum_eq_single, mul_le_mul_of_nonneg_left, Finset.exists_mem_eq_inf', ps_wait_eats_nearest, abs_sub_le, ps_wait_eats_unique

        apply Finset.sum_le_sum
        intro i _
        obtain ⟨ji, hji⟩ := ps_wait_eats_exists n pref s hA i
        rw [Finset.sum_eq_single ji]
        · rw [if_pos hji]
          apply mul_le_mul_of_nonneg_left _ hL0
          by_cases hm : s.1 (σ i) ≤ 0
          · rw [dif_pos hm]
            obtain ⟨j', hj'mem, hj'eq⟩ := Finset.exists_mem_eq_inf' hne (fun j' => |b (σ i) - b j'|)
            rw [hj'eq]
            have h1 := ps_wait_eats_nearest a b pref hp s i ji j' hji (Finset.mem_filter.mp hj'mem).2
            have h2 := abs_sub_le (a i) (b (σ i)) (b j')
            linarith
          · rw [dif_neg hm, add_zero]
            exact ps_wait_eats_nearest a b pref hp s i ji (σ i) hji (lt_of_not_ge hm)
        · intro j _ hj
          rw [if_neg (fun h => hj (ps_wait_eats_unique n pref s i j ji h hji)), zero_mul]
        · intro h; exact absurd (Finset.mem_univ _) h
  10. When no items have positive remaining capacity, the phase cost inequality holds trivially.

    If all item capacities are exhausted, no agent can eat any item, so the left-hand side is zero. The right-hand side is a sum of non-negative absolute values and distances multiplied by L ≥ 0, which is non-negative.

    lines 166–176

      · have hz : ∀ i j, ¬ ps_wait_eats n pref s i j := fun i j h => hA ⟨j, h.1⟩
        simp only [hz, if_false, zero_mul, Finset.sum_const_zero]
        apply add_nonneg
        · exact mul_nonneg hL0 (Finset.sum_nonneg (fun i _ => abs_nonneg _))
        · apply Finset.sum_nonneg
          intro m _
          split_ifs with h
          · exact absurd h.2 (by
              rintro ⟨j, hj⟩; exact hA ⟨j, (Finset.mem_filter.mp hj).2⟩)
          · exact le_rfl
    
  11. The phase states satisfy the recurrence relation, remaining capacities are non-negative and monotonically non-increasing, and the fractional assignment accumulates the increments of each phase.

    The phase state is defined by iterated application of probabilistic_serial_phase. Induction on the phase index k using ps_wait_phase_fst_le_and_nonneg shows that remaining capacities stay non-negative and decrease weakly at each phase. A second induction shows that the assignment matrix s_2(i, j) after k phases is the sum over previous phases m < k of the amounts eaten.

    lines 177–204

    uses ps_wait_phase_fst_le_and_nonneg, ps_wait_phase_eq

    theorem probabilistic_serial_line_cost_le_add_item_wait {n : ℕ} (a b : Fin n → ℝ)
        (pref : Fin n → Equiv.Perm (Fin n)) (h : is_line_distance_preference_profile a b pref) :
        probabilistic_serial_line_cost a b pref ≤
          line_min_matching_cost a b + ∑ j, probabilistic_serial_line_item_wait b pref j := by
      classical
      have hsucc : ∀ k, probabilistic_serial_phase_state n pref (k + 1) =
          probabilistic_serial_phase n pref (probabilistic_serial_phase_state n pref k) := by
        intro k; simp [probabilistic_serial_phase_state, Function.iterate_succ_apply']
      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
          rw [hsucc]; exact (ps_wait_phase_fst_le_and_nonneg n pref _ ih j).1
      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
        rw [hsucc]; exact (ps_wait_phase_fst_le_and_nonneg n pref _ (hnn k) j).2
      have hX : ∀ k i j, (probabilistic_serial_phase_state n pref k).2 i j =
          ∑ m ∈ Finset.range k, (if ps_wait_eats n pref (probabilistic_serial_phase_state n pref m) i j
            then ps_wait_time n pref (probabilistic_serial_phase_state n pref m) else 0) := by
        intro k
        induction k with
        | zero => intro i j; simp [probabilistic_serial_phase_state]
        | succ k ih =>
          intro i j
          rw [Finset.sum_range_succ, ← ih, hsucc, ps_wait_phase_eq]
  12. Phase lengths are non-negative, equal the phase duration when items remain, and their sum over the n phases is at most 1.

    The phase length is defined as the total capacity consumed in the phase divided by n; since capacities decrease, it is non-negative. When items remain, the n agents consume capacity at total rate n, so the phase length equals the duration ps_wait_time. The sum of phase lengths over n phases telescopes to (s_1(0) - s_1(n)) / n; since initial total capacity is n and final capacities are non-negative, the sum is at most n / n = 1.

    lines 205–235

    uses ps_wait_card_sum, Finset.sum_range_sub'

      have hlen0 : ∀ k, 0 ≤ probabilistic_serial_phase_length n pref k := by
        intro k
        unfold probabilistic_serial_phase_length
        apply div_nonneg _ (Nat.cast_nonneg _)
        have := Finset.sum_le_sum (fun j (_ : j ∈ Finset.univ) => hstep k j)
        linarith
      have hlenT : ∀ k, (∃ j, 0 < (probabilistic_serial_phase_state n pref k).1 j) →
          probabilistic_serial_phase_length n pref k =
            ps_wait_time n pref (probabilistic_serial_phase_state n pref k) := by
        intro k hA
        obtain ⟨j0, _⟩ := hA
        have hn : (n : ℝ) ≠ 0 := by
          have : 0 < n := Fin.pos j0
          exact_mod_cast this.ne'
        unfold probabilistic_serial_phase_length
        rw [hsucc, ps_wait_phase_eq]
        simp only [Finset.sum_sub_distrib, ← Finset.mul_sum]
        rw [ps_wait_card_sum n pref _ ⟨j0, by assumption⟩]
        field_simp
        ring
      have hlensum : ∑ k ∈ Finset.range n, probabilistic_serial_phase_length n pref k ≤ 1 := by
        unfold probabilistic_serial_phase_length
        rw [← Finset.sum_div, Finset.sum_range_sub']
        rcases Nat.eq_zero_or_pos n with hn | hn
        · subst hn; simp
        · have hnr : (0 : ℝ) < n := by exact_mod_cast hn
          rw [div_le_one hnr]
          have h0 : ∑ j, (probabilistic_serial_phase_state n pref 0).1 j = n := by
            simp [probabilistic_serial_phase_state]
          have := Finset.sum_nonneg (fun j (_ : j ∈ Finset.univ) => hnn n j)
          linarith
  13. The total probabilistic serial cost is decomposed into the sum over phases of the cost incurred in each phase, compared against an optimal matching permutation σ.

    Let σ be a permutation that minimizes the matching cost, achieving line_min_matching_cost. Substituting the cumulative fractional assignment into the definition of probabilistic serial cost and exchanging the summation over phases with the summations over agents and items expresses the total cost as a sum of individual phase costs.

    lines 236–246

    uses Finset.exists_mem_eq_inf'

      obtain ⟨σ, -, hσ⟩ := Finset.exists_mem_eq_inf' (Finset.univ_nonempty (α := Equiv.Perm (Fin n)))
        (fun σ : Equiv.Perm (Fin n) => ∑ i, |a i - b (σ i)|)
      have hopt : line_min_matching_cost a b = ∑ i, |a i - b (σ i)| := hσ
      have hC0 : 0 ≤ ∑ i, |a i - b (σ i)| := Finset.sum_nonneg (fun i _ => abs_nonneg _)
      unfold probabilistic_serial_line_cost probabilistic_serial_fractional_assignment
      have hst : ((probabilistic_serial_phase n pref)^[n] (fun _ => 1, fun _ _ => 0)) =
          probabilistic_serial_phase_state n pref n := rfl
      rw [hst]
      simp_rw [hX n, Finset.sum_mul]
      conv_lhs => arg 2; ext x; rw [Finset.sum_comm]
      rw [Finset.sum_comm]
  14. The total probabilistic serial cost is at most OPT plus the sum over items of their waiting costs.

    Applying the single-phase bound ps_wait_phase_cost_le to each phase k bounds the phase cost by L_k * OPT plus the phase waiting cost of exhausted items. Summing over k, the OPT term factors as (∑_k L_k) * OPT ≤ 1 * OPT = OPT because ∑_k L_k ≤ 1 and OPT ≥ 0. Exchanging the order of summation between phases and items shows the second term is exactly the sum of probabilistic_serial_line_item_wait over all items, concluding the proof.

    lines 247–264

    uses ps_wait_phase_cost_le, mul_le_mul_of_nonneg_right

      calc _ ≤ ∑ k ∈ Finset.range n, (probabilistic_serial_phase_length n pref k * ∑ i, |a i - b (σ i)| +
            ∑ m, (if h : (probabilistic_serial_phase_state n pref k).1 m ≤ 0 ∧
              (Finset.univ.filter (fun j' => 0 < (probabilistic_serial_phase_state n pref k).1 j')).Nonempty
            then probabilistic_serial_phase_length n pref k *
              (Finset.univ.filter (fun j' => 0 < (probabilistic_serial_phase_state n pref k).1 j')).inf' h.2
                (fun j' => |b m - b j'|)
            else 0)) := by
            apply Finset.sum_le_sum
            intro k _
            exact ps_wait_phase_cost_le a b pref h _ σ _ (hlen0 k) (hlenT k)
        _ = (∑ k ∈ Finset.range n, probabilistic_serial_phase_length n pref k) * ∑ i, |a i - b (σ i)| +
            ∑ j, probabilistic_serial_line_item_wait b pref j := by
            rw [Finset.sum_add_distrib, Finset.sum_mul, Finset.sum_comm (s := Finset.range n)]
            rfl
        _ ≤ _ := by
            rw [hopt]
            have := mul_le_mul_of_nonneg_right hlensum hC0
            linarith
Finset.le_inf'_iff
A value is at most the infimum of a function over a nonempty finite set if and only if it is at most the function value at every element of the set.
Finset.inf'_le
The infimum of a function over a finite set is at most the function value at any element belonging to the set.
le_div_iff₀
For a positive divisor c, a is at most b / c if and only if a * c is at most b.
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
Finset.exists_min_image
A nonempty finite set contains an element achieving the minimum of a given function into a linear order.
lt_or_eq_of_le
If a ≤ b in a partial order, then either a < b or a = b.
ps_wait_eats_exists
Whenever at least one item has strictly positive remaining capacity, every agent eats some item.
ps_wait_eats_unique
In any phase of probabilistic serial, an agent eats at most one item.
Finset.card_bij
Two finite sets have equal cardinality if there exists a bijection between them.
Equiv.sum_comp
Summing a function over a finite type is invariant under precomposition with a bijection of that type.
Finset.sum_eq_single
A sum over a finite set whose terms vanish outside a single element equals the value at that element.
mul_le_mul_of_nonneg_left
Multiplying both sides of an inequality on the left by a non-negative number preserves the inequality.
Finset.exists_mem_eq_inf'
On a nonempty finite set, the infimum of a function into a linear order is achieved by some element of the set.
ps_wait_eats_nearest
Under line-distance preferences, the item an agent eats is at least as close to the agent as any other item with positive remaining capacity.
abs_sub_le
The triangle inequality for the absolute difference: |a - c| ≤ |a - b| + |b - c|.
ps_wait_phase_fst_le_and_nonneg
A single phase of probabilistic serial preserves the non-negativity of remaining item capacities and weakly decreases each capacity.
ps_wait_phase_eq
The probabilistic serial phase update coincides with the explicit formula defined via active eating relations and phase duration.
ps_wait_card_sum
When at least one item is available, the sum over all items of the number of eaters equals the total number of agents n.
Finset.sum_range_sub'
The telescoping sum of differences f(i) - f(i + 1) for i from 0 to n - 1 equals f(0) - f(n).
ps_wait_phase_cost_le
In any phase of duration L, the total cost incurred is at most L times the cost of any matching permutation σ plus L times the distance from each exhausted item to the nearest available item.
mul_le_mul_of_nonneg_right
Multiplying both sides of an inequality on the right by a non-negative number preserves the 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

theorem ps_wait_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]abbrev ps_wait_eats (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (i j : Fin n) : Prop :=  0 < s.1 j ∧ ∀ j', 0 < s.1 j' → (pref i).symm j ≤ (pref i).symm j'noncomputable def ps_wait_time (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) : ℝ :=  open Classical in  let cnt : Fin n → ℕ := fun j => (Finset.univ.filter (fun i => ps_wait_eats n pref s i j)).card  let S := Finset.univ.filter (fun j => 0 < cnt j)  if h : S.Nonempty then S.inf' h (fun j => s.1 j / cnt j) else 0theorem ps_wait_phase_eq (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) :    probabilistic_serial_phase n pref s =      (open Classical in fun j => s.1 j - ps_wait_time n pref s *          (Finset.univ.filter (fun i => ps_wait_eats n pref s i j)).card,       open Classical in fun i j => s.2 i j + if ps_wait_eats n pref s i j then ps_wait_time n pref s else 0) := by  rfltheorem ps_wait_eats_unique (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (i j j' : Fin n)    (h : ps_wait_eats n pref s i j) (h' : ps_wait_eats n pref s i j') : j = j' := by  have h1 := h.2 j' h'.1  have h2 := h'.2 j h.1  exact (pref i).symm.injective (le_antisymm h1 h2)theorem ps_wait_eats_exists (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (hA : ∃ j, 0 < s.1 j) (i : Fin n) :    ∃ j, ps_wait_eats n pref s i j := by  classical  have hne : (Finset.univ.filter (fun j => 0 < s.1 j)).Nonempty := by    obtain ⟨j, hj⟩ := hA; exact ⟨j, by simp [hj]⟩  obtain ⟨j, hj, hmin⟩ := Finset.exists_min_image _ (fun j => (pref i).symm j) hne  refine ⟨j, (Finset.mem_filter.mp hj).2, fun j' hj' => hmin j' (by simp [hj'])⟩theorem ps_wait_eats_nearest {n : ℕ} (a b : Fin n → ℝ) (pref : Fin n → Equiv.Perm (Fin n))    (hp : is_line_distance_preference_profile a b pref)    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (i j j' : Fin n)    (h : ps_wait_eats n pref s i j) (hj' : 0 < s.1 j') : |a i - b j| ≤ |a i - b j'| := by  have hle := h.2 j' hj'  rcases lt_or_eq_of_le hle with hlt | heq  · have := hp i _ _ hlt    simpa using this  · have : j = j' := (pref i).symm.injective heq    rw [this]open Classical intheorem ps_wait_card_sum (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (hA : ∃ j, 0 < s.1 j) :    (∑ j, ((Finset.univ.filter (fun i => ps_wait_eats n pref s i j)).card : ℝ)) = n := by  classical  have : (∑ j, (Finset.univ.filter (fun i => ps_wait_eats n pref s i j)).card) = n := by    rw [← Finset.card_sigma]    have : ∀ i, (Finset.univ.filter (fun j => ps_wait_eats n pref s i j)).card = 1 := by      intro i      obtain ⟨j, hj⟩ := ps_wait_eats_exists n pref s hA i      rw [Finset.card_eq_one]      refine ⟨j, ?_⟩      ext j'      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton]      exact ⟨fun h' => ps_wait_eats_unique n pref s i j' j h' hj, fun e => e ▸ hj⟩    calc _ = ∑ i : Fin n, (Finset.univ.filter (fun j => ps_wait_eats n pref s i j)).card := by            rw [← Finset.card_sigma]            refine Finset.card_bij (fun p _ => ⟨p.2, p.1⟩) ?_ ?_ ?_            · intro p hp; simp at hp ⊢; exact hp            · intro p _ q _ e; simp at e; ext <;> simp [e.1, e.2]            · intro q hq; refine ⟨⟨q.2, q.1⟩, by simpa using hq, rfl⟩      _ = n := by simp [this]  exact_mod_cast thistheorem ps_wait_time_nonneg (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n))    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (hs : ∀ j, 0 ≤ s.1 j) : 0 ≤ ps_wait_time n pref s := by  classical  unfold ps_wait_time  simp only  split_ifs with h  · rw [Finset.le_inf'_iff]    intro k _    exact div_nonneg (hs k) (Nat.cast_nonneg _)  · exact le_rflopen Classical intheorem ps_wait_phase_cost_le {n : ℕ} (a b : Fin n → ℝ) (pref : Fin n → Equiv.Perm (Fin n))    (hp : is_line_distance_preference_profile a b pref)    (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (σ : Equiv.Perm (Fin n)) (L : ℝ) (hL0 : 0 ≤ L)    (hL : (∃ j, 0 < s.1 j) → L = ps_wait_time n pref s) :    ∑ i, ∑ j, (if ps_wait_eats n pref s i j then ps_wait_time n pref s else 0) * |a i - b j| ≤      L * ∑ i, |a i - b (σ i)| +      ∑ m, (if h : s.1 m ≤ 0 ∧ (Finset.univ.filter (fun j' => 0 < s.1 j')).Nonempty        then L * (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' h.2 (fun j' => |b m - b j'|)        else 0) := by  by_cases hA : ∃ j, 0 < s.1 j  · have hLt := hL hA    rw [← hLt]    have hne : (Finset.univ.filter (fun j' => 0 < s.1 j')).Nonempty := by      obtain ⟨j, hj⟩ := hA; exact ⟨j, by simp [hj]⟩    have hrhs : ∀ m, (if h : s.1 m ≤ 0 ∧ (Finset.univ.filter (fun j' => 0 < s.1 j')).Nonempty        then L * (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' h.2 (fun j' => |b m - b j'|)        else 0) = L * (if h : s.1 m ≤ 0 then          (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' hne (fun j' => |b m - b j'|) else 0) := by      intro m      by_cases hm : s.1 m ≤ 0      · rw [dif_pos ⟨hm, hne⟩, dif_pos hm]      · rw [dif_neg (fun h => hm h.1), dif_neg hm, mul_zero]    simp_rw [hrhs]    rw [← Finset.mul_sum, ← mul_add]    have hσ : ∑ m, (if h : s.1 m ≤ 0 then          (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' hne (fun j' => |b m - b j'|) else 0) =        ∑ i, (if h : s.1 (σ i) ≤ 0 then          (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' hne (fun j' => |b (σ i) - b j'|) else 0) :=      (Equiv.sum_comp σ (fun m => if h : s.1 m ≤ 0 then          (Finset.univ.filter (fun j' => 0 < s.1 j')).inf' hne (fun j' => |b m - b j'|) else 0)).symm    rw [hσ, ← Finset.sum_add_distrib, Finset.mul_sum]    apply Finset.sum_le_sum    intro i _    obtain ⟨ji, hji⟩ := ps_wait_eats_exists n pref s hA i    rw [Finset.sum_eq_single ji]    · rw [if_pos hji]      apply mul_le_mul_of_nonneg_left _ hL0      by_cases hm : s.1 (σ i) ≤ 0      · rw [dif_pos hm]        obtain ⟨j', hj'mem, hj'eq⟩ := Finset.exists_mem_eq_inf' hne (fun j' => |b (σ i) - b j'|)        rw [hj'eq]        have h1 := ps_wait_eats_nearest a b pref hp s i ji j' hji (Finset.mem_filter.mp hj'mem).2        have h2 := abs_sub_le (a i) (b (σ i)) (b j')        linarith      · rw [dif_neg hm, add_zero]        exact ps_wait_eats_nearest a b pref hp s i ji (σ i) hji (lt_of_not_ge hm)    · intro j _ hj      rw [if_neg (fun h => hj (ps_wait_eats_unique n pref s i j ji h hji)), zero_mul]    · intro h; exact absurd (Finset.mem_univ _) h  · have hz : ∀ i j, ¬ ps_wait_eats n pref s i j := fun i j h => hA ⟨j, h.1⟩    simp only [hz, if_false, zero_mul, Finset.sum_const_zero]    apply add_nonneg    · exact mul_nonneg hL0 (Finset.sum_nonneg (fun i _ => abs_nonneg _))    · apply Finset.sum_nonneg      intro m _      split_ifs with h      · exact absurd h.2 (by          rintro ⟨j, hj⟩; exact hA ⟨j, (Finset.mem_filter.mp hj).2⟩)      · exact le_rfltheorem probabilistic_serial_line_cost_le_add_item_wait {n : ℕ} (a b : Fin n → ℝ)    (pref : Fin n → Equiv.Perm (Fin n)) (h : is_line_distance_preference_profile a b pref) :    probabilistic_serial_line_cost a b pref ≤      line_min_matching_cost a b + ∑ j, probabilistic_serial_line_item_wait b pref j := by  classical  have hsucc : ∀ k, probabilistic_serial_phase_state n pref (k + 1) =      probabilistic_serial_phase n pref (probabilistic_serial_phase_state n pref k) := by    intro k; simp [probabilistic_serial_phase_state, Function.iterate_succ_apply']  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      rw [hsucc]; exact (ps_wait_phase_fst_le_and_nonneg n pref _ ih j).1  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    rw [hsucc]; exact (ps_wait_phase_fst_le_and_nonneg n pref _ (hnn k) j).2  have hX : ∀ k i j, (probabilistic_serial_phase_state n pref k).2 i j =      ∑ m ∈ Finset.range k, (if ps_wait_eats n pref (probabilistic_serial_phase_state n pref m) i j        then ps_wait_time n pref (probabilistic_serial_phase_state n pref m) else 0) := by    intro k    induction k with    | zero => intro i j; simp [probabilistic_serial_phase_state]    | succ k ih =>      intro i j      rw [Finset.sum_range_succ, ← ih, hsucc, ps_wait_phase_eq]  have hlen0 : ∀ k, 0 ≤ probabilistic_serial_phase_length n pref k := by    intro k    unfold probabilistic_serial_phase_length    apply div_nonneg _ (Nat.cast_nonneg _)    have := Finset.sum_le_sum (fun j (_ : j ∈ Finset.univ) => hstep k j)    linarith  have hlenT : ∀ k, (∃ j, 0 < (probabilistic_serial_phase_state n pref k).1 j) →      probabilistic_serial_phase_length n pref k =        ps_wait_time n pref (probabilistic_serial_phase_state n pref k) := by    intro k hA    obtain ⟨j0, _⟩ := hA    have hn : (n : ℝ) ≠ 0 := by      have : 0 < n := Fin.pos j0      exact_mod_cast this.ne'    unfold probabilistic_serial_phase_length    rw [hsucc, ps_wait_phase_eq]    simp only [Finset.sum_sub_distrib, ← Finset.mul_sum]    rw [ps_wait_card_sum n pref _ ⟨j0, by assumption⟩]    field_simp    ring  have hlensum : ∑ k ∈ Finset.range n, probabilistic_serial_phase_length n pref k ≤ 1 := by    unfold probabilistic_serial_phase_length    rw [← Finset.sum_div, Finset.sum_range_sub']    rcases Nat.eq_zero_or_pos n with hn | hn    · subst hn; simp    · have hnr : (0 : ℝ) < n := by exact_mod_cast hn      rw [div_le_one hnr]      have h0 : ∑ j, (probabilistic_serial_phase_state n pref 0).1 j = n := by        simp [probabilistic_serial_phase_state]      have := Finset.sum_nonneg (fun j (_ : j ∈ Finset.univ) => hnn n j)      linarith  obtain ⟨σ, -, hσ⟩ := Finset.exists_mem_eq_inf' (Finset.univ_nonempty (α := Equiv.Perm (Fin n)))    (fun σ : Equiv.Perm (Fin n) => ∑ i, |a i - b (σ i)|)  have hopt : line_min_matching_cost a b = ∑ i, |a i - b (σ i)| := hσ  have hC0 : 0 ≤ ∑ i, |a i - b (σ i)| := Finset.sum_nonneg (fun i _ => abs_nonneg _)  unfold probabilistic_serial_line_cost probabilistic_serial_fractional_assignment  have hst : ((probabilistic_serial_phase n pref)^[n] (fun _ => 1, fun _ _ => 0)) =      probabilistic_serial_phase_state n pref n := rfl  rw [hst]  simp_rw [hX n, Finset.sum_mul]  conv_lhs => arg 2; ext x; rw [Finset.sum_comm]  rw [Finset.sum_comm]  calc _ ≤ ∑ k ∈ Finset.range n, (probabilistic_serial_phase_length n pref k * ∑ i, |a i - b (σ i)| +        ∑ m, (if h : (probabilistic_serial_phase_state n pref k).1 m ≤ 0 ∧          (Finset.univ.filter (fun j' => 0 < (probabilistic_serial_phase_state n pref k).1 j')).Nonempty        then probabilistic_serial_phase_length n pref k *          (Finset.univ.filter (fun j' => 0 < (probabilistic_serial_phase_state n pref k).1 j')).inf' h.2            (fun j' => |b m - b j'|)        else 0)) := by        apply Finset.sum_le_sum        intro k _        exact ps_wait_phase_cost_le a b pref h _ σ _ (hlen0 k) (hlenT k)    _ = (∑ k ∈ Finset.range n, probabilistic_serial_phase_length n pref k) * ∑ i, |a i - b (σ i)| +        ∑ j, probabilistic_serial_line_item_wait b pref j := by        rw [Finset.sum_add_distrib, Finset.sum_mul, Finset.sum_comm (s := Finset.range n)]        rfl    _ ≤ _ := by        rw [hopt]        have := mul_le_mul_of_nonneg_right hlensum hC0        linarith
See it in the graphDiscuss this resultChallenge it