AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_fractional_assignment_two_split

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

  1. 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.

    lines 3–4

    uses Equiv.symm_apply_eq

      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
  2. 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.

    lines 5–12

      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
  3. 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.

    lines 13–18

      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]
  4. 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.

    lines 19–23

    uses Fin.forall_fin_two, Finset.filter_eq', Finset.filter_eq

      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]
  5. 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.

    lines 24–27

      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
  6. 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.

    lines 28–29

    uses Function.iterate_succ, Function.iterate_zero, Function.comp_apply, id

      unfold 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.

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

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]
See it in the graphDiscuss this resultChallenge it