probabilistic_serial_fractional_assignment_two_same
Sanity check: when both of two agents rank item 0 first, probabilistic serial gives each agent half of each item.
Statement
theorem probabilistic_serial_fractional_assignment_two_same
(pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 0) (h1 : pref 1 0 = 0) (i j : Fin 2) :
probabilistic_serial_fractional_assignment 2 pref i j = 1 / 2- Source
- sanity lemma for probabilistic_serial_fractional_assignment (OP-1158)
- Verified
- 05 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_phaseOne phase of the simultaneous-eating (probabilistic serial) procedure for n agents and n items. Agent i's ranking is the permutation pref…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 3
- probabilistic_serial_equispaced_distortion_two_agents_attainedFor n = 2 with equispaced items at 0 and 1, agents at 0 and 1/2 with ties broken toward the smaller-index item attain the harmonic…
- probabilistic_serial_line_distortion_le_two_agentsCase n = 2 of OP-1158: for two agents at real positions a_0, a_1 and two items at real positions b_0, b_1, with each agent ranking the…
- probabilistic_serial_line_cost_two_sameSanity check: two agents at 0, items at 0 and 1, both ranking item 0 first: the probabilistic serial cost is 1.
The proof, explained
The probabilistic serial mechanism proceeds in phases where agents consume their most preferred available item at unit rate until an item is depleted. When two agents both rank item 0 first and item 1 second, both consume item 0 in the first phase, exhausting it at time t = 1/2 and each receiving half of it. In the second phase, only item 1 remains available, so both agents consume item 1 until time t = 1/2, each receiving half of it as well. The proof verifies these two phases by explicitly computing the phase transition function twice, concluding that each agent receives exactly half of each item.
Both agents rank item 0 first (rank 0) and item 1 second (rank 1).
The hypotheses h0 and h1 state that each agent's preference permutation maps rank 0 to item 0. Inverting this via Equiv.symm_apply_eq shows that item 0 has rank 0 for both agents (e0, e1). Since the preference permutations act bijectively on {0, 1}, injectivity forces item 1 to have non-zero rank, which by linear integer arithmetic (omega) means item 1 has rank 1 for both agents (f0, f1).
uses
Equiv.symm_apply_eqhave e0 : (pref 0).symm 0 = 0 := by rw [Equiv.symm_apply_eq]; exact h0.symm have e1 : (pref 1).symm 0 = 0 := by rw [Equiv.symm_apply_eq]; exact h1.symm have f0 : (pref 0).symm 1 = 1 := by have : (pref 0).symm 1 ≠ 0 := fun h => by have := (pref 0).symm.injective (h.trans e0.symm); simp at this omega have f1 : (pref 1).symm 1 = 1 := by have : (pref 1).symm 1 ≠ 0 := fun h => by have := (pref 1).symm.injective (h.trans e1.symm); simp at this omega
In Phase 1, both agents strictly prefer item 0, so the active item set is {0}.
When both items 0 and 1 are available, an item is weakly preferred to all available items if and only if it is item 0 (hr and hr2). Consequently, both agents choose to consume item 0, making S = {0} the set of items with positive eating rate (hS). These characterisations are proved by finite case exhaustion (fin_cases) on the agents and items.
have hr : ∀ i x : Fin 2, ((pref i).symm x ≤ (pref i).symm 0 ∧ (pref i).symm x ≤ (pref i).symm 1) ↔ x = 0 := by intro i x; fin_cases i <;> fin_cases x <;> simp [e0, e1, f0, f1] have hr2 : ∀ i x : Fin 2, ((pref i).symm x = 0 ∧ (pref i).symm x ≤ 1) ↔ x = 0 := by intro i x; fin_cases i <;> fin_cases x <;> simp [e0, e1, f0, f1] have hS : (Finset.univ.filter fun x : Fin 2 => (if x = 0 then (Finset.univ : Finset (Fin 2)) else ∅).Nonempty) = {0} := by ext x; fin_cases x <;> simp
Phase 1 consumes item 0 to depletion in time 1/2, giving each agent half of item 0.
Unfolding probabilistic_serial_phase, both agents consume item 0 at unit speed, giving a total consumption rate of 2 for item 0 and 0 for item 1. The bottleneck duration is t = 1/2 (the initial capacity 1 divided by rate 2). After time t, item 0 is fully depleted, item 1 still has capacity 1, and each agent has accumulated a fraction 1/2 of item 0 and 0 of item 1 (p1). This is verified on all components using the characterisations hr, hr2, and hS, together with Fin.forall_fin_two and Finset.filter_true_of_mem.
uses
Fin.forall_fin_two,Finset.filter_true_of_memhave p1 : probabilistic_serial_phase 2 pref (fun _ => 1, fun _ _ => 0) = (fun j => if j = 0 then 0 else 1, fun _ j => if j = 0 then 1 / 2 else 0) := by unfold probabilistic_serial_phase ext j <;> fin_cases j <;> simp [Fin.forall_fin_two, hr, hr2, Finset.filter_true_of_mem, hS, e0, e1, f0, f1]
In Phase 2, with item 0 depleted, both agents prefer the only remaining item 1, so the active item set is {1}.
With item 0 at capacity 0, only item 1 has positive remaining capacity. For each agent, an item is available and weakly preferred to item 1 if and only if it is item 1 (hq). Hence both agents eat item 1, so the set of actively consumed items is S = {1} (hS2), proved by finite case exhaustion over Fin 2.
have hq : ∀ i x : Fin 2, ((0 < if x = 0 then (0:ℝ) else 1) ∧ (pref i).symm x ≤ (pref i).symm 1) ↔ x = 1 := by intro i x; fin_cases i <;> fin_cases x <;> simp [e0, e1, f0, f1] have hS2 : (Finset.univ.filter fun x : Fin 2 => (if x = 1 then (Finset.univ : Finset (Fin 2)) else ∅).Nonempty) = {1} := by ext x; fin_cases x <;> simp
Phase 2 consumes item 1 to depletion in time 1/2, giving each agent an additional half of item 1.
Unfolding probabilistic_serial_phase, both agents consume item 1 at total rate 2, so the phase duration is t = 1/2. At the conclusion of this second phase, both items have 0 capacity remaining, and each agent's cumulative fraction is 1/2 of item 0 and 1/2 of item 1 (p2). The goal is closed by evaluating each component with simp using hq, hS2, and Fin.forall_fin_two across all cases.
uses
Fin.forall_fin_twohave p2 : probabilistic_serial_phase 2 pref (fun j => if j = 0 then 0 else 1, fun _ j => if j = 0 then 1 / 2 else 0) = (fun _ => 0, fun _ _ => 1 / 2) := by unfold probabilistic_serial_phase ext a <;> fin_cases a <;> simp [Fin.forall_fin_two, hq, hS2, e0, e1, f0, f1] <;> (rename_i y; fin_cases y <;> simp [e0, e1, f0, f1])
The probabilistic serial fractional assignment gives every agent half of each item.
By definition, probabilistic_serial_fractional_assignment for n = 2 runs probabilistic_serial_phase twice starting from initial capacities 1 and assignment 0, and returns the accumulated assignment. Expanding the two iterations using Function.iterate_succ, Function.iterate_zero, Function.comp_apply, and id, and substituting the phase outcomes p1 and p2, evaluates the fractional assignment to 1/2 for all agents i and items j.
uses
Function.iterate_succ,Function.iterate_zero,Function.comp_apply,idunfold probabilistic_serial_fractional_assignment simp only [Function.iterate_succ, Function.iterate_zero, Function.comp_apply, id, p1, p2]
Equiv.symm_apply_eq- For an equivalence e, e.symm x = y if and only if x = e y.
Fin.forall_fin_two- A universal quantifier over the two-element type Fin 2 is equivalent to the conjunction of the cases for 0 and 1.
Finset.filter_true_of_mem- Filtering a finite set by a predicate that holds for all of its elements leaves the set unchanged.
Function.iterate_succ- The (n + 1)-th iterate of a function f is the composition f^[n] ∘ f.
Function.iterate_zero- The 0-th iterate of a function is the identity function.
Function.comp_apply- Applying a composed function (f ∘ g) to an input x equals f (g x).
id- The identity function, returning its argument unchanged.
- The helper equivalences hr, hr2, hS, hq, and hS2 are formal scaffolding required for Lean's simplifier to compute finite set infima and evaluate quantifiers over Fin 2; on paper, the eating rates and phase durations are determined by inspection.
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 probabilistic_serial_fractional_assignment_two_same (pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 0) (h1 : pref 1 0 = 0) (i j : Fin 2) : probabilistic_serial_fractional_assignment 2 pref i j = 1 / 2 := by have e0 : (pref 0).symm 0 = 0 := by rw [Equiv.symm_apply_eq]; exact h0.symm have e1 : (pref 1).symm 0 = 0 := by rw [Equiv.symm_apply_eq]; exact h1.symm have f0 : (pref 0).symm 1 = 1 := by have : (pref 0).symm 1 ≠ 0 := fun h => by have := (pref 0).symm.injective (h.trans e0.symm); simp at this omega have f1 : (pref 1).symm 1 = 1 := by have : (pref 1).symm 1 ≠ 0 := fun h => by have := (pref 1).symm.injective (h.trans e1.symm); simp at this omega have hr : ∀ i x : Fin 2, ((pref i).symm x ≤ (pref i).symm 0 ∧ (pref i).symm x ≤ (pref i).symm 1) ↔ x = 0 := by intro i x; fin_cases i <;> fin_cases x <;> simp [e0, e1, f0, f1] have hr2 : ∀ i x : Fin 2, ((pref i).symm x = 0 ∧ (pref i).symm x ≤ 1) ↔ x = 0 := by intro i x; fin_cases i <;> fin_cases x <;> simp [e0, e1, f0, f1] have hS : (Finset.univ.filter fun x : Fin 2 => (if x = 0 then (Finset.univ : Finset (Fin 2)) else ∅).Nonempty) = {0} := by ext x; fin_cases x <;> simp have p1 : probabilistic_serial_phase 2 pref (fun _ => 1, fun _ _ => 0) = (fun j => if j = 0 then 0 else 1, fun _ j => if j = 0 then 1 / 2 else 0) := by unfold probabilistic_serial_phase ext j <;> fin_cases j <;> simp [Fin.forall_fin_two, hr, hr2, Finset.filter_true_of_mem, hS, e0, e1, f0, f1] have hq : ∀ i x : Fin 2, ((0 < if x = 0 then (0:ℝ) else 1) ∧ (pref i).symm x ≤ (pref i).symm 1) ↔ x = 1 := by intro i x; fin_cases i <;> fin_cases x <;> simp [e0, e1, f0, f1] have hS2 : (Finset.univ.filter fun x : Fin 2 => (if x = 1 then (Finset.univ : Finset (Fin 2)) else ∅).Nonempty) = {1} := by ext x; fin_cases x <;> simp have p2 : probabilistic_serial_phase 2 pref (fun j => if j = 0 then 0 else 1, fun _ j => if j = 0 then 1 / 2 else 0) = (fun _ => 0, fun _ _ => 1 / 2) := by unfold probabilistic_serial_phase ext a <;> fin_cases a <;> simp [Fin.forall_fin_two, hq, hS2, e0, e1, f0, f1] <;> (rename_i y; fin_cases y <;> simp [e0, e1, f0, f1]) unfold probabilistic_serial_fractional_assignment simp only [Function.iterate_succ, Function.iterate_zero, Function.comp_apply, id, p1, p2]