probabilistic_serial_line_cost_le_add_item_wait
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
- 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
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.
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.
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]
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.
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
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'.
uses
le_antisymmtheorem 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)
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.
uses
Finset.exists_min_imagetheorem 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'])⟩
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.
uses
lt_or_eq_of_letheorem 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]
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.
uses
ps_wait_eats_exists,ps_wait_eats_unique,Finset.card_bijopen 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
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.
uses
Finset.le_inf'_ifftheorem 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
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.
uses
Equiv.sum_compopen 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]
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.
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_uniqueapply 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
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.
· 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
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.
uses
ps_wait_phase_fst_le_and_nonneg,ps_wait_phase_eqtheorem 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]
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.
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
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.
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]
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.
uses
ps_wait_phase_cost_le,mul_le_mul_of_nonneg_rightcalc _ ≤ ∑ 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.
- The phase length `probabilistic_serial_phase_length` is formally defined as the decrease in total item capacity divided by n, which is proven to equal the phase duration `ps_wait_time` whenever items with positive capacity remain.
- Ties in agent preferences are broken by arbitrary permutations; the theorem holds for any profile that orders items by line distance.
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_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