AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_fractional_assignment_two_split_swap

theoremverified

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

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

    lines 3–4

    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 0 = 0 := by rw [Equiv.symm_apply_eq]; exact h1.symm
  2. 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.

    lines 5–12

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

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

    lines 19–23

    uses Fin.forall_fin_two, Finset.filter_ne', Finset.filter_ne, 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 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]
  5. 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.

    lines 24–27

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

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

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