AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_fractional_assignment_two_same_one

theoremverified

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

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

    lines 3–12

    uses Equiv.symm_apply_eq

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

    lines 13–22

    uses Fin.forall_fin_two, Finset.filter_true_of_mem

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

    lines 23–33

    uses Fin.forall_fin_two

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

    lines 34–35

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

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