probabilistic_serial_fractional_assignment_col_sum
Every item is fully eaten under probabilistic serial: the column sums of the probabilistic serial assignment are 1.
Statement
theorem probabilistic_serial_fractional_assignment_col_sum (n : ℕ) (hn : 1 ≤ n) (pref : Fin n → Equiv.Perm (Fin n)) (j : Fin n) : ∑ i, probabilistic_serial_fractional_assignment n pref i j = 1- Source
- step towards probabilistic_serial_line_metric_sharp_linear_distortion
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_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_assignment_row_sumUnder probabilistic serial each agent consumes exactly one unit in total: the row sums of the probabilistic serial assignment are 1.
The proof, explained
The probabilistic serial (PS) mechanism executes a sequence of phases, where in each phase agents eat their most preferred available item at unit rate until some item is exhausted. By induction on the phase index, an invariant is maintained: for every item, its remaining capacity plus the total fraction consumed so far always equals 1. Because capacities remain non-negative, the total fraction consumed of each item after n phases is at most 1. Since every agent receives a total allocation of 1, the sum of all item consumptions must equal n; because n quantities each at most 1 sum to n, every item must be fully consumed with a column sum of exactly 1.
The state after k + 1 phases is the result of applying one phase transition to the state after k phases.
The state after k phases is defined as the k-fold iterate of the phase function starting from the initial state (where all capacities are 1 and all consumed shares are 0). By `Function.iterate_succ_apply'`, the (k+1)-th iterate is the phase function applied to the k-th iterate.
uses
Function.iterate_succ_apply'show (probabilistic_serial_phase n pref)^[k+1] (fun x => 1, fun x x_1 => 0) = probabilistic_serial_phase n pref ((probabilistic_serial_phase n pref)^[k] (fun x => 1, fun x x_1 => 0)) rw [Function.iterate_succ_apply']
In any phase starting with non-negative item capacities, the amount of item j consumed during the phase does not exceed its remaining capacity.
We split into cases on whether any agent is currently eating item j. If cnt(j) = 0, the consumption is T * 0 = 0, which is at most the remaining capacity s.1(j) by non-negativity. If cnt(j) > 0, item j belongs to the non-empty set S of actively eaten items. The phase duration T is defined as the infimum of s.1(j') / cnt(j') over all j' ∈ S, so T ≤ s.1(j) / cnt(j). Multiplying both sides by the positive quantity cnt(j) yields T * cnt(j) ≤ s.1(j).
uses
mul_zero,Nat.pos_of_ne_zero,Finset.mem_filter,Finset.mem_univ,dif_pos,Finset.inf'_le,mul_le_mul_of_nonneg_right,le_of_lt,div_mul_cancel₀,ne_of_gtby_cases hc : probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j = 0 · rw [hc]; push_cast; rw [mul_zero]; exact hpos j · have hcpos : 0 < probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j := Nat.pos_of_ne_zero hc have hmem : j ∈ probabilistic_serial_fractional_assignment_col_sum_S n pref s := by rw [probabilistic_serial_fractional_assignment_col_sum_S, Finset.mem_filter] exact ⟨Finset.mem_univ _, hcpos⟩ have hcastpos : (0:ℝ) < (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := by exact_mod_cast hcpos have hS : (probabilistic_serial_fractional_assignment_col_sum_S n pref s).Nonempty := ⟨j, hmem⟩ have hT : probabilistic_serial_fractional_assignment_col_sum_T n pref s = (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS (fun j => s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) := by simp only [probabilistic_serial_fractional_assignment_col_sum_T]; exact dif_pos hS have hle : (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS (fun j => s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) ≤ s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := Finset.inf'_le _ hmem rw [hT] calc (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS (fun j => s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) ≤ (s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := mul_le_mul_of_nonneg_right hle (le_of_lt hcastpos) _ = s.1 j := div_mul_cancel₀ (s.1 j) (ne_of_gt hcastpos)
At every step k, the remaining capacity of each item is non-negative.
By induction on k. At step 0, all item capacities are initialized to 1, which is non-negative. For the induction step, the capacity of item j at step k + 1 is its capacity at step k minus T * cnt(j). By the previous lemma (`probabilistic_serial_fractional_assignment_col_sum_T_mul_le`) and the induction hypothesis, T * cnt(j) does not exceed the capacity at step k, so the difference remains non-negative.
uses
probabilistic_serial_fractional_assignment_col_sum_state_succ,probabilistic_serial_fractional_assignment_col_sum_phase_eq,probabilistic_serial_fractional_assignment_col_sum_T_mul_leinduction k with | zero => intro j; simp [probabilistic_serial_fractional_assignment_col_sum_cap, probabilistic_serial_phase_state] | succ k ih => intro j have hcap : probabilistic_serial_fractional_assignment_col_sum_cap n pref (k+1) j = probabilistic_serial_fractional_assignment_col_sum_cap n pref k j - probabilistic_serial_fractional_assignment_col_sum_T n pref (probabilistic_serial_phase_state n pref k) * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref (probabilistic_serial_phase_state n pref k) j : ℝ) := by simp only [probabilistic_serial_fractional_assignment_col_sum_cap, probabilistic_serial_fractional_assignment_col_sum_state_succ, probabilistic_serial_fractional_assignment_col_sum_phase_eq] have hle := probabilistic_serial_fractional_assignment_col_sum_T_mul_le n pref (probabilistic_serial_phase_state n pref k) (fun j => ih j) j rw [hcap] linarith
In a single phase, the total fraction of item j consumed across all agents increases by T * cnt(j).
Unfolding the phase update, agent i receives an additional share T of item j if agent i eats item j, and 0 otherwise. Distributing the sum over agents, we factor out T from the sum of indicators for whether agent i eats item j. By `Finset.sum_boole`, the sum of these indicators is precisely the count of agents eating item j, cnt(j).
uses
probabilistic_serial_fractional_assignment_col_sum_phase_eq,Finset.sum_add_distrib,Finset.sum_congr,Finset.mul_sum,Finset.sum_boolerw [probabilistic_serial_fractional_assignment_col_sum_phase_eq] simp only [Finset.sum_add_distrib] congr 1 calc (∑ x, if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j then probabilistic_serial_fractional_assignment_col_sum_T n pref s else (0:ℝ)) = ∑ x, probabilistic_serial_fractional_assignment_col_sum_T n pref s * (if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j then (1:ℝ) else 0) := by apply Finset.sum_congr rfl intro x _ by_cases hx : probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j · simp [hx] · simp [hx] _ = probabilistic_serial_fractional_assignment_col_sum_T n pref s * (∑ x, (if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j then (1:ℝ) else 0)) := by rw [Finset.mul_sum] _ = probabilistic_serial_fractional_assignment_col_sum_T n pref s * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := by congr 1 exact Finset.sum_boole (fun i => probabilistic_serial_fractional_assignment_col_sum_eats n pref s i j) Finset.univ
At every step k, the remaining capacity of item j plus the total fraction of item j consumed across all agents equals 1.
By induction on k. For k = 0, the initial capacity is 1 and the total fraction consumed is 0, summing to 1. In the inductive step from k to k + 1, the capacity of item j decreases by T * cnt(j) while the total consumed fraction increases by T * cnt(j) (by `probabilistic_serial_fractional_assignment_col_sum_col_phase`). The two changes cancel, preserving the sum of 1.
uses
probabilistic_serial_fractional_assignment_col_sum_state_succ,probabilistic_serial_fractional_assignment_col_sum_phase_eq,probabilistic_serial_fractional_assignment_col_sum_col_phaseinduction k with | zero => simp [probabilistic_serial_fractional_assignment_col_sum_cap, probabilistic_serial_fractional_assignment_col_sum_col, probabilistic_serial_phase_state] | succ k ih => have hcap : probabilistic_serial_fractional_assignment_col_sum_cap n pref (k+1) j = probabilistic_serial_fractional_assignment_col_sum_cap n pref k j - probabilistic_serial_fractional_assignment_col_sum_T n pref (probabilistic_serial_phase_state n pref k) * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref (probabilistic_serial_phase_state n pref k) j : ℝ) := by simp only [probabilistic_serial_fractional_assignment_col_sum_cap, probabilistic_serial_fractional_assignment_col_sum_state_succ, probabilistic_serial_fractional_assignment_col_sum_phase_eq] have hcol : probabilistic_serial_fractional_assignment_col_sum_col n pref (k+1) j = probabilistic_serial_fractional_assignment_col_sum_col n pref k j + probabilistic_serial_fractional_assignment_col_sum_T n pref (probabilistic_serial_phase_state n pref k) * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref (probabilistic_serial_phase_state n pref k) j : ℝ) := by simp only [probabilistic_serial_fractional_assignment_col_sum_col, probabilistic_serial_fractional_assignment_col_sum_state_succ] exact probabilistic_serial_fractional_assignment_col_sum_col_phase n pref (probabilistic_serial_phase_state n pref k) j rw [hcap, hcol] linarith [ih]
For every item j, the column sum of the final probabilistic serial assignment is at most 1.
After n phases, the conservation invariant (`probabilistic_serial_fractional_assignment_col_sum_col_form`) gives cap(n, j) + col(n, j) = 1. Since capacity is non-negative (`probabilistic_serial_fractional_assignment_col_sum_cap_nonneg`), the column sum col(n, j) = 1 - cap(n, j) is at most 1.
uses
probabilistic_serial_fractional_assignment_col_sum_col_form,probabilistic_serial_fractional_assignment_col_sum_cap_nonneglet c : Fin n → ℝ := fun j => ∑ i, probabilistic_serial_fractional_assignment n pref i j have hle : ∀ j, c j ≤ 1 := by intro j have hinv := probabilistic_serial_fractional_assignment_col_sum_col_form n pref n j have hnn := probabilistic_serial_fractional_assignment_col_sum_cap_nonneg n pref n j have e : probabilistic_serial_fractional_assignment_col_sum_col n pref n j = c j := rfl rw [e] at hinv linarith
The sum of all column sums of the assignment matrix equals n.
Summing all column sums corresponds to summing all entries of the assignment matrix. Exchanging the order of summation (`Finset.sum_comm`) rewrites this as the sum over all n agents of their row sums. Since every agent's row sum is 1 (`probabilistic_serial_fractional_assignment_row_sum`), the total sum across all n agents is n.
uses
probabilistic_serial_fractional_assignment_row_sum,Finset.sum_commhave hrow : ∀ i, ∑ j, probabilistic_serial_fractional_assignment n pref i j = 1 := fun i => probabilistic_serial_fractional_assignment_row_sum n hn pref i have htotal : ∑ j, c j = (n:ℝ) := by simp only [c] rw [Finset.sum_comm] simp [hrow]
Every column sum equals 1: every item is fully consumed.
Subtracting the total sum of column sums from n gives ∑_j (1 - c(j)) = n - n = 0. Since each column sum satisfies c(j) ≤ 1, each term 1 - c(j) is non-negative. A sum of non-negative real numbers is zero if and only if each term is zero (`Finset.sum_eq_zero_iff_of_nonneg`). Hence 1 - c(j) = 0, proving c(j) = 1 for every item j.
uses
Finset.sum_sub_distrib,Finset.sum_eq_zero_iff_of_nonneg,Finset.mem_univhave hd : ∑ j, (1 - c j) = 0 := by rw [Finset.sum_sub_distrib, htotal] simp have hnn : ∀ j ∈ (Finset.univ : Finset (Fin n)), 0 ≤ 1 - c j := by intro j _; linarith [hle j] have hz := (Finset.sum_eq_zero_iff_of_nonneg (s := Finset.univ) hnn).mp hd have hj := hz j (Finset.mem_univ j) show c j = 1 linarith
Function.iterate_succ_apply'- Iterating a function n + 1 times equals applying the function once to the n-th iterate.
mul_zero- Multiplying any element by zero yields zero.
Nat.pos_of_ne_zero- A natural number is strictly positive if and only if it is non-zero.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
dif_pos- A dependent if-then-else expression reduces to its 'then' branch when the condition is true.
Finset.inf'_le- The infimum of a function over a non-empty finite set is less than or equal to the function value at any element of the set.
mul_le_mul_of_nonneg_right- Multiplying both sides of an inequality by a non-negative value on the right preserves the inequality.
le_of_lt- A strict inequality implies the corresponding non-strict inequality.
div_mul_cancel₀- Dividing by a non-zero element and then multiplying by that element yields the original numerator.
ne_of_gt- If a is strictly greater than b, then a is not equal to b.
probabilistic_serial_fractional_assignment_col_sum_state_succ- The state of the probabilistic serial algorithm at step k + 1 is obtained by applying one phase update to the state at step k.
probabilistic_serial_fractional_assignment_col_sum_phase_eq- Unfolds the definition of a single phase transition, updating capacities by subtracting T * cnt and updating consumed shares by adding T for active agent-item pairs.
probabilistic_serial_fractional_assignment_col_sum_T_mul_le- In any phase starting with non-negative item capacities, the total consumption T * cnt(j) of item j during the phase cannot exceed its remaining capacity.
Finset.sum_add_distrib- The sum of a pointwise sum of two functions over a finite set equals the sum of their individual sums.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every index.
Finset.mul_sum- A constant factor can be factored out of or distributed into a finite sum.
Finset.sum_boole- The sum of an indicator (0-1) function over a finite set equals the cardinality of the subset satisfying the condition.
probabilistic_serial_fractional_assignment_col_sum_col_phase- The sum across all agents of the shares of item j consumed increases during one phase by exactly T * cnt(j).
probabilistic_serial_fractional_assignment_col_sum_col_form- At every step k, the remaining capacity of item j plus the total fraction of item j consumed so far equals 1.
probabilistic_serial_fractional_assignment_col_sum_cap_nonneg- At every step k, the remaining capacity of every item is non-negative.
probabilistic_serial_fractional_assignment_row_sum- Under the probabilistic serial mechanism, every agent receives a fractional assignment whose row sum across all items is 1.
Finset.sum_comm- The order of summation in a finite double sum can be exchanged.
Finset.sum_sub_distrib- The sum of a difference of two functions over a finite set equals the difference of their sums.
Finset.sum_eq_zero_iff_of_nonneg- A finite sum of non-negative real numbers is zero if and only if each individual term is zero.
- The probabilistic serial procedure is formalized by iterating a single phase transition function n times; if all items are fully eaten before n phases, subsequent phases have duration T = 0.
- All lemmas preceding the main theorem are private helper lemmas defined in the same file specifically to establish this column sum result.
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.
private noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_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' : Fin n), 0 < s.1 j' → (pref i).symm j ≤ (pref i).symm j'private noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_cnt (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (j : Fin n) : ℕ := (Finset.univ.filter (fun i => probabilistic_serial_fractional_assignment_col_sum_eats n pref s i j)).cardprivate noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_S (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) : Finset (Fin n) := Finset.univ.filter (fun j => 0 < probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j)private noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_T (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) : ℝ := if h : (probabilistic_serial_fractional_assignment_col_sum_S n pref s).Nonempty then (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' h (fun j => s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) else 0private theorem probabilistic_serial_fractional_assignment_col_sum_phase_eq (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) : probabilistic_serial_phase n pref s = (fun j => s.1 j - probabilistic_serial_fractional_assignment_col_sum_T n pref s * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ), fun i j => s.2 i j + if probabilistic_serial_fractional_assignment_col_sum_eats n pref s i j then probabilistic_serial_fractional_assignment_col_sum_T n pref s else 0) := rflprivate theorem probabilistic_serial_fractional_assignment_col_sum_state_succ (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) : probabilistic_serial_phase_state n pref (k + 1) = probabilistic_serial_phase n pref (probabilistic_serial_phase_state n pref k) := by show (probabilistic_serial_phase n pref)^[k+1] (fun x => 1, fun x x_1 => 0) = probabilistic_serial_phase n pref ((probabilistic_serial_phase n pref)^[k] (fun x => 1, fun x x_1 => 0)) rw [Function.iterate_succ_apply']private theorem probabilistic_serial_fractional_assignment_col_sum_T_mul_le (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (hpos : ∀ j, 0 ≤ s.1 j) (j : Fin n) : probabilistic_serial_fractional_assignment_col_sum_T n pref s * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) ≤ s.1 j := by by_cases hc : probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j = 0 · rw [hc]; push_cast; rw [mul_zero]; exact hpos j · have hcpos : 0 < probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j := Nat.pos_of_ne_zero hc have hmem : j ∈ probabilistic_serial_fractional_assignment_col_sum_S n pref s := by rw [probabilistic_serial_fractional_assignment_col_sum_S, Finset.mem_filter] exact ⟨Finset.mem_univ _, hcpos⟩ have hcastpos : (0:ℝ) < (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := by exact_mod_cast hcpos have hS : (probabilistic_serial_fractional_assignment_col_sum_S n pref s).Nonempty := ⟨j, hmem⟩ have hT : probabilistic_serial_fractional_assignment_col_sum_T n pref s = (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS (fun j => s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) := by simp only [probabilistic_serial_fractional_assignment_col_sum_T]; exact dif_pos hS have hle : (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS (fun j => s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) ≤ s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := Finset.inf'_le _ hmem rw [hT] calc (probabilistic_serial_fractional_assignment_col_sum_S n pref s).inf' hS (fun j => s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) ≤ (s.1 j / (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ)) * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := mul_le_mul_of_nonneg_right hle (le_of_lt hcastpos) _ = s.1 j := div_mul_cancel₀ (s.1 j) (ne_of_gt hcastpos)private noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_cap (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) : Fin n → ℝ := (probabilistic_serial_phase_state n pref k).1private noncomputable abbrev probabilistic_serial_fractional_assignment_col_sum_col (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) (j : Fin n) : ℝ := ∑ i, (probabilistic_serial_phase_state n pref k).2 i jprivate theorem probabilistic_serial_fractional_assignment_col_sum_cap_nonneg (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) : ∀ j, 0 ≤ probabilistic_serial_fractional_assignment_col_sum_cap n pref k j := by induction k with | zero => intro j; simp [probabilistic_serial_fractional_assignment_col_sum_cap, probabilistic_serial_phase_state] | succ k ih => intro j have hcap : probabilistic_serial_fractional_assignment_col_sum_cap n pref (k+1) j = probabilistic_serial_fractional_assignment_col_sum_cap n pref k j - probabilistic_serial_fractional_assignment_col_sum_T n pref (probabilistic_serial_phase_state n pref k) * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref (probabilistic_serial_phase_state n pref k) j : ℝ) := by simp only [probabilistic_serial_fractional_assignment_col_sum_cap, probabilistic_serial_fractional_assignment_col_sum_state_succ, probabilistic_serial_fractional_assignment_col_sum_phase_eq] have hle := probabilistic_serial_fractional_assignment_col_sum_T_mul_le n pref (probabilistic_serial_phase_state n pref k) (fun j => ih j) j rw [hcap] linarithprivate theorem probabilistic_serial_fractional_assignment_col_sum_col_phase (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) (j : Fin n) : (∑ i, (probabilistic_serial_phase n pref s).2 i j) = (∑ i, s.2 i j) + probabilistic_serial_fractional_assignment_col_sum_T n pref s * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := by rw [probabilistic_serial_fractional_assignment_col_sum_phase_eq] simp only [Finset.sum_add_distrib] congr 1 calc (∑ x, if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j then probabilistic_serial_fractional_assignment_col_sum_T n pref s else (0:ℝ)) = ∑ x, probabilistic_serial_fractional_assignment_col_sum_T n pref s * (if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j then (1:ℝ) else 0) := by apply Finset.sum_congr rfl intro x _ by_cases hx : probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j · simp [hx] · simp [hx] _ = probabilistic_serial_fractional_assignment_col_sum_T n pref s * (∑ x, (if probabilistic_serial_fractional_assignment_col_sum_eats n pref s x j then (1:ℝ) else 0)) := by rw [Finset.mul_sum] _ = probabilistic_serial_fractional_assignment_col_sum_T n pref s * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref s j : ℝ) := by congr 1 exact Finset.sum_boole (fun i => probabilistic_serial_fractional_assignment_col_sum_eats n pref s i j) Finset.univprivate theorem probabilistic_serial_fractional_assignment_col_sum_col_form (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) (j : Fin n) : probabilistic_serial_fractional_assignment_col_sum_cap n pref k j + probabilistic_serial_fractional_assignment_col_sum_col n pref k j = 1 := by induction k with | zero => simp [probabilistic_serial_fractional_assignment_col_sum_cap, probabilistic_serial_fractional_assignment_col_sum_col, probabilistic_serial_phase_state] | succ k ih => have hcap : probabilistic_serial_fractional_assignment_col_sum_cap n pref (k+1) j = probabilistic_serial_fractional_assignment_col_sum_cap n pref k j - probabilistic_serial_fractional_assignment_col_sum_T n pref (probabilistic_serial_phase_state n pref k) * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref (probabilistic_serial_phase_state n pref k) j : ℝ) := by simp only [probabilistic_serial_fractional_assignment_col_sum_cap, probabilistic_serial_fractional_assignment_col_sum_state_succ, probabilistic_serial_fractional_assignment_col_sum_phase_eq] have hcol : probabilistic_serial_fractional_assignment_col_sum_col n pref (k+1) j = probabilistic_serial_fractional_assignment_col_sum_col n pref k j + probabilistic_serial_fractional_assignment_col_sum_T n pref (probabilistic_serial_phase_state n pref k) * (probabilistic_serial_fractional_assignment_col_sum_cnt n pref (probabilistic_serial_phase_state n pref k) j : ℝ) := by simp only [probabilistic_serial_fractional_assignment_col_sum_col, probabilistic_serial_fractional_assignment_col_sum_state_succ] exact probabilistic_serial_fractional_assignment_col_sum_col_phase n pref (probabilistic_serial_phase_state n pref k) j rw [hcap, hcol] linarith [ih]/-- Every item is fully eaten under probabilistic serial: the column sums of the PS assignment equal 1. -/theorem probabilistic_serial_fractional_assignment_col_sum (n : ℕ) (hn : 1 ≤ n) (pref : Fin n → Equiv.Perm (Fin n)) (j : Fin n) : ∑ i, probabilistic_serial_fractional_assignment n pref i j = 1 := by let c : Fin n → ℝ := fun j => ∑ i, probabilistic_serial_fractional_assignment n pref i j have hle : ∀ j, c j ≤ 1 := by intro j have hinv := probabilistic_serial_fractional_assignment_col_sum_col_form n pref n j have hnn := probabilistic_serial_fractional_assignment_col_sum_cap_nonneg n pref n j have e : probabilistic_serial_fractional_assignment_col_sum_col n pref n j = c j := rfl rw [e] at hinv linarith have hrow : ∀ i, ∑ j, probabilistic_serial_fractional_assignment n pref i j = 1 := fun i => probabilistic_serial_fractional_assignment_row_sum n hn pref i have htotal : ∑ j, c j = (n:ℝ) := by simp only [c] rw [Finset.sum_comm] simp [hrow] have hd : ∑ j, (1 - c j) = 0 := by rw [Finset.sum_sub_distrib, htotal] simp have hnn : ∀ j ∈ (Finset.univ : Finset (Fin n)), 0 ≤ 1 - c j := by intro j _; linarith [hle j] have hz := (Finset.sum_eq_zero_iff_of_nonneg (s := Finset.univ) hnn).mp hd have hj := hz j (Finset.mem_univ j) show c j = 1 linarith