probabilistic_serial_fractional_assignment_two_same_one
Two agents who both rank item 1 first each get half of each item under probabilistic serial.
Statement
theorem probabilistic_serial_fractional_assignment_two_same_one (pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 1) (h1 : pref 1 0 = 1) (i j : Fin 2) :
probabilistic_serial_fractional_assignment 2 pref i j = 1 / 2- 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 probabilistic serial mechanism works in continuous time: agents consume their most preferred available item at unit rate until an item is exhausted, repeating until all items are allocated. Here, both agents have the identical preference order 1 ≻ 0. In the first phase, both agents consume item 1 simultaneously, splitting it equally until it runs out at time 1/2; in the second phase, both agents consume the remaining item 0, splitting it equally until time 1, resulting in each agent receiving 1/2 of each item.
Both agents rank item 1 first (rank 0) and item 0 second (rank 1).
The hypotheses h0 and h1 state that rank 0 corresponds to item 1 for both agents. Applying Equiv.symm_apply_eq inverts this to show that item 1 has rank 0 for both agents (e0, e1). Since preferences are permutations on {0, 1}, injectivity prevents item 0 from also having rank 0, so linear arithmetic on Fin 2 forces item 0 to have rank 1 for both agents (f0, f1).
uses
Equiv.symm_apply_eqhave e0 : (pref 0).symm 1 = 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 0 = 1 := by have : (pref 0).symm 0 ≠ 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
In the first phase, both agents consume item 1 equally until it is exhausted at time 1/2.
With both items initially available at capacity 1, exhausting all cases over Fin 2 confirms that each agent's uniquely preferred item is item 1 (hr), so only item 1 is being consumed (hS). Unfolding the phase definition, both agents eat item 1 at rate 1 each (total rate 2). Item 1 is fully consumed at time t = 1/2, leaving capacity 0 for item 1, capacity 1 for item 0, and giving each agent a 1/2 share of item 1 (p1).
uses
Fin.forall_fin_two,Finset.filter_true_of_memhave hr : ∀ i x : Fin 2, ((pref i).symm x ≤ (pref i).symm 0 ∧ (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 hS : (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 p1 : probabilistic_serial_phase 2 pref (fun _ => 1, fun _ _ => 0) = (fun j => if j = 1 then 0 else 1, fun _ j => if j = 1 then 1 / 2 else 0) := by unfold probabilistic_serial_phase ext j <;> fin_cases j <;> simp [Fin.forall_fin_two, hr, Finset.filter_true_of_mem, hS, e0, e1, f0, f1] <;> (rename_i y; fin_cases y <;> simp [e0, e1, f0, f1])
In the second phase, both agents consume the remaining item 0 equally until it is exhausted at time 1/2.
Because item 1 is depleted, item 0 is the only item with positive capacity remaining. Checking the finite cases confirms that both agents eat item 0 (hq), so the active consumption set is {0} (hS2). Both agents consume item 0 at total rate 2 for duration t = 1/2. At the end of the phase (p2), both items are depleted and each agent gains an additional 1/2 share of item 0, totaling 1/2 of each item.
uses
Fin.forall_fin_twohave hq : ∀ i x : Fin 2, ((0 < if x = 1 then (0:ℝ) else 1) ∧ (pref i).symm x ≤ (pref i).symm 0) ↔ x = 0 := 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 = 0 then (Finset.univ : Finset (Fin 2)) else ∅).Nonempty) = {0} := by ext x; fin_cases x <;> simp have p2 : probabilistic_serial_phase 2 pref (fun j => if j = 1 then 0 else 1, fun _ j => if j = 1 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 final fractional assignment gives each agent half of each item.
For two items, the probabilistic serial assignment is defined as the result of iterating the phase function twice from the initial state of full capacities and zero shares. Unfolding this definition and simplifying the two successive phase applications using p1 and p2 concludes that each agent receives 1/2 of both items.
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 quantification over Fin 2 is equivalent to the conjunction of the conditions at 0 and 1.
Finset.filter_true_of_mem- Filtering a finite set by a predicate satisfied by all its members returns the set itself.
Function.iterate_succ- The (n + 1)-th iterate of a function f is the composition of f^[n] with f.
Function.iterate_zero- The zeroth iterate of a function f is the identity function.
Function.comp_apply- Evaluating a composite function satisfies (f ∘ g) x = f (g x).
id- The identity function returns its argument unchanged.
- In this formalization, an agent's preference permutation maps ranks to items (so rank 0 is the most preferred item). Consequently, the rank of item j is given by the inverse permutation (pref i).symm j, with smaller values indicating higher priority.
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_one (pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 1) (h1 : pref 1 0 = 1) (i j : Fin 2) : probabilistic_serial_fractional_assignment 2 pref i j = 1 / 2 := by have e0 : (pref 0).symm 1 = 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 0 = 1 := by have : (pref 0).symm 0 ≠ 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 = 1 := 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 = 1 then (Finset.univ : Finset (Fin 2)) else ∅).Nonempty) = {1} := by ext x; fin_cases x <;> simp have p1 : probabilistic_serial_phase 2 pref (fun _ => 1, fun _ _ => 0) = (fun j => if j = 1 then 0 else 1, fun _ j => if j = 1 then 1 / 2 else 0) := by unfold probabilistic_serial_phase ext j <;> fin_cases j <;> simp [Fin.forall_fin_two, hr, Finset.filter_true_of_mem, hS, e0, e1, f0, f1] <;> (rename_i y; fin_cases y <;> simp [e0, e1, f0, f1]) have hq : ∀ i x : Fin 2, ((0 < if x = 1 then (0:ℝ) else 1) ∧ (pref i).symm x ≤ (pref i).symm 0) ↔ x = 0 := 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 = 0 then (Finset.univ : Finset (Fin 2)) else ∅).Nonempty) = {0} := by ext x; fin_cases x <;> simp have p2 : probabilistic_serial_phase 2 pref (fun j => if j = 1 then 0 else 1, fun _ j => if j = 1 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]