AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_fractional_assignment_two_same

theoremverified

Sanity check: when both of two agents rank item 0 first, probabilistic serial gives each agent half of each item.

Statement

theorem probabilistic_serial_fractional_assignment_two_same
    (pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 0) (h1 : pref 1 0 = 0) (i j : Fin 2) :
    probabilistic_serial_fractional_assignment 2 pref i j = 1 / 2
Source
sanity lemma for probabilistic_serial_fractional_assignment (OP-1158)
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…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 3

The proof, explained

The probabilistic serial mechanism proceeds in phases where agents consume their most preferred available item at unit rate until an item is depleted. When two agents both rank item 0 first and item 1 second, both consume item 0 in the first phase, exhausting it at time t = 1/2 and each receiving half of it. In the second phase, only item 1 remains available, so both agents consume item 1 until time t = 1/2, each receiving half of it as well. The proof verifies these two phases by explicitly computing the phase transition function twice, concluding that each agent receives exactly half of each item.

  1. Both agents rank item 0 first (rank 0) and item 1 second (rank 1).

    The hypotheses h0 and h1 state that each agent's preference permutation maps rank 0 to item 0. Inverting this via Equiv.symm_apply_eq shows that item 0 has rank 0 for both agents (e0, e1). Since the preference permutations act bijectively on {0, 1}, injectivity forces item 1 to have non-zero rank, which by linear integer arithmetic (omega) means item 1 has rank 1 for both agents (f0, f1).

    lines 4–13

    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 0 = 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 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
  2. In Phase 1, both agents strictly prefer item 0, so the active item set is {0}.

    When both items 0 and 1 are available, an item is weakly preferred to all available items if and only if it is item 0 (hr and hr2). Consequently, both agents choose to consume item 0, making S = {0} the set of items with positive eating rate (hS). These characterisations are proved by finite case exhaustion (fin_cases) on the agents and items.

    lines 14–20

      have hr : ∀ i x : Fin 2, ((pref i).symm x ≤ (pref i).symm 0 ∧ (pref i).symm x ≤ (pref i).symm 1) ↔ x = 0 := by
        intro i x; fin_cases i <;> fin_cases x <;> simp [e0, e1, f0, f1]
      have hr2 : ∀ i x : Fin 2, ((pref i).symm x = 0 ∧ (pref i).symm x ≤ 1) ↔ x = 0 := 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 = 0 then (Finset.univ : Finset (Fin 2)) else ∅).Nonempty) = {0} := by
        ext x; fin_cases x <;> simp
  3. Phase 1 consumes item 0 to depletion in time 1/2, giving each agent half of item 0.

    Unfolding probabilistic_serial_phase, both agents consume item 0 at unit speed, giving a total consumption rate of 2 for item 0 and 0 for item 1. The bottleneck duration is t = 1/2 (the initial capacity 1 divided by rate 2). After time t, item 0 is fully depleted, item 1 still has capacity 1, and each agent has accumulated a fraction 1/2 of item 0 and 0 of item 1 (p1). This is verified on all components using the characterisations hr, hr2, and hS, together with Fin.forall_fin_two and Finset.filter_true_of_mem.

    lines 21–24

    uses Fin.forall_fin_two, Finset.filter_true_of_mem

      have p1 : probabilistic_serial_phase 2 pref (fun _ => 1, fun _ _ => 0) =
          (fun j => if j = 0 then 0 else 1, fun _ j => if j = 0 then 1 / 2 else 0) := by
        unfold probabilistic_serial_phase
        ext j <;> fin_cases j <;> simp [Fin.forall_fin_two, hr, hr2, Finset.filter_true_of_mem, hS, e0, e1, f0, f1]
  4. In Phase 2, with item 0 depleted, both agents prefer the only remaining item 1, so the active item set is {1}.

    With item 0 at capacity 0, only item 1 has positive remaining capacity. For each agent, an item is available and weakly preferred to item 1 if and only if it is item 1 (hq). Hence both agents eat item 1, so the set of actively consumed items is S = {1} (hS2), proved by finite case exhaustion over Fin 2.

    lines 25–29

      have hq : ∀ i x : Fin 2, ((0 < if x = 0 then (0:ℝ) else 1) ∧ (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 hS2 : (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
  5. Phase 2 consumes item 1 to depletion in time 1/2, giving each agent an additional half of item 1.

    Unfolding probabilistic_serial_phase, both agents consume item 1 at total rate 2, so the phase duration is t = 1/2. At the conclusion of this second phase, both items have 0 capacity remaining, and each agent's cumulative fraction is 1/2 of item 0 and 1/2 of item 1 (p2). The goal is closed by evaluating each component with simp using hq, hS2, and Fin.forall_fin_two across all cases.

    lines 30–35

    uses Fin.forall_fin_two

      have p2 : probabilistic_serial_phase 2 pref
          (fun j => if j = 0 then 0 else 1, fun _ j => if j = 0 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])
  6. The probabilistic serial fractional assignment gives every agent half of each item.

    By definition, probabilistic_serial_fractional_assignment for n = 2 runs probabilistic_serial_phase twice starting from initial capacities 1 and assignment 0, and returns the accumulated assignment. Expanding the two iterations using Function.iterate_succ, Function.iterate_zero, Function.comp_apply, and id, and substituting the phase outcomes p1 and p2, evaluates the fractional assignment to 1/2 for all agents i and items j.

    lines 36–37

    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 quantifier over the two-element type Fin 2 is equivalent to the conjunction of the cases for 0 and 1.
Finset.filter_true_of_mem
Filtering a finite set by a predicate that holds for all of its elements leaves the set unchanged.
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 is the identity function.
Function.comp_apply
Applying a composed function (f ∘ g) to an input x equals f (g x).
id
The identity function, returning 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    (pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 0) (h1 : pref 1 0 = 0) (i j : Fin 2) :    probabilistic_serial_fractional_assignment 2 pref i j = 1 / 2 := by  have e0 : (pref 0).symm 0 = 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 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 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 = 0 := by    intro i x; fin_cases i <;> fin_cases x <;> simp [e0, e1, f0, f1]  have hr2 : ∀ i x : Fin 2, ((pref i).symm x = 0 ∧ (pref i).symm x ≤ 1) ↔ x = 0 := 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 = 0 then (Finset.univ : Finset (Fin 2)) else ∅).Nonempty) = {0} := by    ext x; fin_cases x <;> simp  have p1 : probabilistic_serial_phase 2 pref (fun _ => 1, fun _ _ => 0) =      (fun j => if j = 0 then 0 else 1, fun _ j => if j = 0 then 1 / 2 else 0) := by    unfold probabilistic_serial_phase    ext j <;> fin_cases j <;> simp [Fin.forall_fin_two, hr, hr2, Finset.filter_true_of_mem, hS, e0, e1, f0, f1]  have hq : ∀ i x : Fin 2, ((0 < if x = 0 then (0:ℝ) else 1) ∧ (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 hS2 : (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 p2 : probabilistic_serial_phase 2 pref      (fun j => if j = 0 then 0 else 1, fun _ j => if j = 0 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