probabilistic_serial_fractional_assignment_two_split_swap
Two agents whose first choices are item 1 (agent 0) and item 0 (agent 1) each get their first choice entirely under probabilistic serial.
Statement
theorem probabilistic_serial_fractional_assignment_two_split_swap (pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 1) (h1 : pref 1 0 = 0) (i j : Fin 2) : probabilistic_serial_fractional_assignment 2 pref i j = if j = i then 0 else 1
- 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 runs for n = 2 phases on two agents and two items. Because the two agents have disjoint top choices—agent 0 top-ranks item 1 and agent 1 top-ranks item 0—each agent consumes their preferred item without competition. In the first phase of duration t = 1, both items are fully consumed, allocating item 1 entirely to agent 0 and item 0 entirely to agent 1. The second phase is trivial since all capacities are already zero, leaving each agent fully assigned to their first choice.
Agent 0 ranks item 1 at rank 0, and agent 1 ranks item 0 at rank 0.
Applying the definition of the inverse permutation (via Equiv.symm_apply_eq) to the hypotheses h0 and h1 shows that each agent's first choice maps to rank 0 under their inverse preference permutation.
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 0 = 0 := by rw [Equiv.symm_apply_eq]; exact h1.symm
Agent 0 ranks item 0 at rank 1, and agent 1 ranks item 1 at rank 1.
Because the preference rankings are permutations of the two-element set Fin 2 and rank 0 is already occupied by the first choice, injectivity ensures that the second item cannot have rank 0. In Fin 2, any value different from 0 must be 1, so the rank of each agent's second choice is uniquely determined.
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 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
An item x is agent i's top choice if and only if x ≠ i, and pairwise preference comparisons between items 0 and 1 are determined for each agent.
Exhaustive case analysis across both agents and both items, simplified using the complete ranking tables established above, confirms that an item is agent i's weakly most-preferred choice if and only if x ≠ i (that is, agent 0 top-ranks item 1 and agent 1 top-ranks item 0). Similarly, agent i prefers item 0 to item 1 precisely when i = 1, and prefers item 1 to item 0 precisely when i = 0.
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 = 1 := 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 = 0 := by intro i; fin_cases i <;> simp [e0, e1, f0, f1]
During the first phase of the probabilistic serial mechanism, all item capacities are exhausted, and agent i receives 1 unit of item 1 - i and 0 units of item i.
Unfolding the definition of a probabilistic serial phase, each item begins with capacity 1. Since agent 0 prefers item 1 and agent 1 prefers item 0, each item has exactly one consumer. Both items are consumed at unit rate until exhaustion at time t = 1. Consequently, both remaining item capacities become 0, and each agent i is allocated exactly 1 unit of their top choice 1 - i.
uses
Fin.forall_fin_two,Finset.filter_ne',Finset.filter_ne,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 0 else 1) := by unfold probabilistic_serial_phase ext a <;> fin_cases a <;> simp [Fin.forall_fin_two, hr, hr0, hr1, Finset.filter_ne', Finset.filter_ne, Finset.filter_eq', Finset.filter_eq] <;> (try (rename_i y; fin_cases y)) <;> try simp [e0, e1, f0, f1]
The second phase of the probabilistic serial mechanism leaves the allocation and capacities unchanged.
Because all item capacities are already 0 at the end of phase 1, no agent can consume any item. The active set of items is empty, the elapsed time is t = 0, and the assignment and capacity state remain unchanged.
have p2 : probabilistic_serial_phase 2 pref (fun _ => 0, fun i j => if j = i then 0 else 1) = (fun _ => 0, fun i j => if j = i then 0 else 1) := by unfold probabilistic_serial_phase simp
The final probabilistic serial fractional assignment gives agent i 0 units of item i and 1 unit of item 1 - i.
By definition, the fractional assignment after 2 phases is the second iterate of the phase transition function applied to the initial state (1, 0). Expanding the two iterates and substituting the values from phase 1 and phase 2 yields the final assignment matrix, which is 0 when j = i and 1 otherwise.
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 predicate at 0 and at 1.
Finset.filter_ne'- Filtering a finite set for elements not equal to b (as a ≠ b) removes b from the set.
Finset.filter_ne- Filtering a finite set for elements not equal to b (as b ≠ a) removes b from the set.
Finset.filter_eq'- Filtering a finite set for elements equal to b (as a = b) yields {b} if b is in the set, and ∅ otherwise.
Finset.filter_eq- Filtering a finite set for elements equal to b (via Eq b) yields {b} if b is in the set, and ∅ otherwise.
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 f is the identity function id.
Function.comp_apply- Function composition applied to an argument satisfies (f ∘ g) x = f (g x).
id- The identity function mapping any value to itself.
- The evaluation of the first phase (lines 19–23) relies on finite case analysis and rewriting of finite set filters, which Lean's simplifier automates to determine the eating sets, agent counts, and the minimum time duration t = 1.
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_swap (pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 1) (h1 : pref 1 0 = 0) (i j : Fin 2) : probabilistic_serial_fractional_assignment 2 pref i j = if j = i then 0 else 1 := by have e0 : (pref 0).symm 1 = 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 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 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 ≠ 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 = 1 := 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 = 0 := 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 0 else 1) := by unfold probabilistic_serial_phase ext a <;> fin_cases a <;> simp [Fin.forall_fin_two, hr, hr0, hr1, Finset.filter_ne', Finset.filter_ne, 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 0 else 1) = (fun _ => 0, fun i j => if j = i then 0 else 1) := 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]