probabilistic_serial_fractional_assignment_two_split
Two agents whose first choices are item 0 (agent 0) and item 1 (agent 1) each get their first choice entirely under probabilistic serial.
Statement
theorem probabilistic_serial_fractional_assignment_two_split (pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 0) (h1 : pref 1 0 = 1) (i j : Fin 2) : probabilistic_serial_fractional_assignment 2 pref i j = if j = i then 1 else 0
- Source
- lemma for probabilistic_serial_line_distortion_le_two_agents (OP-1158): the probabilistic serial assignment for two agents
- 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…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- 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…
The proof, explained
The proof proceeds by explicitly computing the two successive phases of the probabilistic serial mechanism on two items. Because agents 0 and 1 have distinct top choices (items 0 and 1, respectively), each agent's preference order over the two items is uniquely determined, and during the first phase both agents consume their respective favorite items without mutual competition. By time t = 1, both items are fully exhausted, giving each agent their first choice entirely, while the second phase simply preserves this already-depleted state.
Item 0 has rank 0 for agent 0, and item 1 has rank 0 for agent 1.
The hypotheses h0 and h1 state that the preference permutation pref 0 maps rank 0 to item 0, and pref 1 maps rank 0 to item 1. Inverting these permutations using Equiv.symm_apply_eq shows that (pref 0)⁻¹(0) = 0 and (pref 1)⁻¹(1) = 0.
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 1 = 0 := by rw [Equiv.symm_apply_eq]; exact h1.symm
Item 1 has rank 1 for agent 0, and item 0 has rank 1 for agent 1.
Because the preference permutations are bijections on the two-element set Fin 2 = {0, 1}, injectivity ensures that (pref 0)⁻¹(1) cannot be 0 (which is already the rank of item 0), so it must be 1. Symmetrically, (pref 1)⁻¹(0) cannot be 0 (the rank of item 1), so it must be 1.
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 0 = 1 := by have : (pref 1).symm 0 ≠ 0 := fun h => by have := (pref 1).symm.injective (h.trans e1.symm); simp at this omega
Each agent i strictly prefers item i to the other item, so item x is weakly preferred to all items by agent i if and only if x = i.
Exhaustive case analysis on all elements of Fin 2, combined with the rank values computed previously, confirms that agent 0 strictly prefers item 0 to item 1, while agent 1 strictly prefers item 1 to item 0. Hence, an item x is weakly preferred to both items by agent i if and only if x = i.
have hr : ∀ i x : Fin 2, ((pref i).symm x ≤ (pref i).symm 0 ∧ (pref i).symm x ≤ (pref i).symm 1) ↔ x = i := by intro i x; fin_cases i <;> fin_cases x <;> simp [e0, e1, f0, f1] have hr0 : ∀ i : Fin 2, (pref i).symm 0 ≤ (pref i).symm 1 ↔ i = 0 := by intro i; fin_cases i <;> simp [e0, e1, f0, f1] have hr1 : ∀ i : Fin 2, (pref i).symm 1 ≤ (pref i).symm 0 ↔ i = 1 := by intro i; fin_cases i <;> simp [e0, e1, f0, f1]
The first phase consumes both items completely and allocates fraction 1 of item i to agent i.
Unfolding the definition of probabilistic_serial_phase on the initial state (where each item has remaining capacity 1 and no agent has received any share), each agent i eats only their most-preferred available item, which is item i. Each item is therefore eaten by exactly one agent at rate 1. The transition time until an item is exhausted is t = min(1/1, 1/1) = 1. After time 1, remaining capacities become 0, and agent i has accumulated share 1 of item i and 0 of the other item. Lean verifies this componentwise across Fin 2 using Fin.forall_fin_two and simplifying the active eater sets with Finset.filter_eq' and Finset.filter_eq.
uses
Fin.forall_fin_two,Finset.filter_eq',Finset.filter_eqhave p1 : probabilistic_serial_phase 2 pref (fun _ => 1, fun _ _ => 0) = (fun _ => 0, fun i j => if j = i then 1 else 0) := by unfold probabilistic_serial_phase ext a <;> fin_cases a <;> simp [Fin.forall_fin_two, hr, hr0, hr1, Finset.filter_eq', Finset.filter_eq] <;> (try (rename_i y; fin_cases y)) <;> try simp [e0, e1, f0, f1]
The second phase leaves the fully consumed capacities and the allocations unchanged.
Unfolding probabilistic_serial_phase, since all remaining capacities are already 0, no items can be eaten. The set of items being consumed is empty, the elapsed time is t = 0, and the state remains identical.
have p2 : probabilistic_serial_phase 2 pref (fun _ => 0, fun i j => if j = i then 1 else 0) = (fun _ => 0, fun i j => if j = i then 1 else 0) := by unfold probabilistic_serial_phase simp
The probabilistic serial fractional assignment gives each agent i exactly fraction 1 of item i and 0 of the other item.
By definition, the assignment is the allocation component after two iterations of probabilistic_serial_phase. Rewriting the two-fold iterate using Function.iterate_succ, Function.iterate_zero, Function.comp_apply, and id, the first phase yields the diagonal assignment matrix (1 if j = i else 0), and the second phase preserves it.
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- Applying the inverse of an equivalence e to x equals y if and only if x = e y.
Fin.forall_fin_two- A universal statement over Fin 2 is equivalent to the conjunction of the statement at 0 and at 1.
Finset.filter_eq'- Filtering a finite set for elements equal to b yields the singleton {b} if b belongs to the set, and the empty set otherwise.
Finset.filter_eq- Filtering a finite set for elements equal to b yields the singleton {b} if b belongs to the set, and the empty set otherwise.
Function.iterate_succ- The (n + 1)-th iterate of a function f equals the composition of the n-th iterate with f.
Function.iterate_zero- The 0-th iterate of any function is the identity function id.
Function.comp_apply- The application of a composite function (f ∘ g) x equals f (g x).
id- The identity function, which maps every element to itself.
- The probabilistic serial mechanism is formally defined by running n phases (here n = 2), even though all items are already exhausted at the end of the first phase; the second phase acts as a dummy step that leaves the allocation unchanged.
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_split (pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 0) (h1 : pref 1 0 = 1) (i j : Fin 2) : probabilistic_serial_fractional_assignment 2 pref i j = if j = i then 1 else 0 := by have e0 : (pref 0).symm 0 = 0 := by rw [Equiv.symm_apply_eq]; exact h0.symm have e1 : (pref 1).symm 1 = 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 0 = 1 := by have : (pref 1).symm 0 ≠ 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 = i := by intro i x; fin_cases i <;> fin_cases x <;> simp [e0, e1, f0, f1] have hr0 : ∀ i : Fin 2, (pref i).symm 0 ≤ (pref i).symm 1 ↔ i = 0 := by intro i; fin_cases i <;> simp [e0, e1, f0, f1] have hr1 : ∀ i : Fin 2, (pref i).symm 1 ≤ (pref i).symm 0 ↔ i = 1 := by intro i; fin_cases i <;> simp [e0, e1, f0, f1] have p1 : probabilistic_serial_phase 2 pref (fun _ => 1, fun _ _ => 0) = (fun _ => 0, fun i j => if j = i then 1 else 0) := by unfold probabilistic_serial_phase ext a <;> fin_cases a <;> simp [Fin.forall_fin_two, hr, hr0, hr1, Finset.filter_eq', Finset.filter_eq] <;> (try (rename_i y; fin_cases y)) <;> try simp [e0, e1, f0, f1] have p2 : probabilistic_serial_phase 2 pref (fun _ => 0, fun i j => if j = i then 1 else 0) = (fun _ => 0, fun i j => if j = i then 1 else 0) := by unfold probabilistic_serial_phase simp unfold probabilistic_serial_fractional_assignment simp only [Function.iterate_succ, Function.iterate_zero, Function.comp_apply, id, p1, p2]