AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_line_distortion_le_two_agents

theoremverifiedoriginal

Case 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 items by distance (ties broken arbitrarily), the cost of the probabilistic serial assignment, sum_ij X_ij |a_i - b_j|, is at most 2 times the minimum perfect-matching cost.

Statement

theorem probabilistic_serial_line_distortion_le_two_agents (a b : Fin 2 → ℝ)
    (pref : Fin 2 → Equiv.Perm (Fin 2)) (h : is_line_distance_preference_profile a b pref) :
    probabilistic_serial_line_cost a b pref ≤ 2 * line_min_matching_cost a b
Related work
OP-1158, case n = 2; arXiv:2611.05777 bounds probabilistic serial on general metrics, not this line case
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
Used by 1

Read back from the Lean

For any two agent locations $a : \text{Fin } 2 \to \mathbb{R}$, two item locations $b : \text{Fin } 2 \to \mathbb{R}$, and preference profile $\text{pref} : \text{Fin } 2 \to \text{Equiv.Perm}(\text{Fin } 2)$, if $\text{pref}$ is consistent with the line distances between $a$ and $b$ (that is, for every agent $i \in \text{Fin } 2$ and ranks $k < k'$, agent $i$'s distance to their $k$-th ranked item is at most their distance to their $k'$-th ranked item: $|a(i) - b(\text{pref}(i)(k))| \le |a(i) - b(\text{pref}(i)(k'))|$), then the expected/fractional line cost under the Probabilistic Serial mechanism with respect to $a, b, \text{pref}$ is at most 2 times the minimum matching cost between $a$ and $b$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof shows that for two agents and two items on a real line, the Probabilistic Serial (PS) cost is at most twice the optimal matching cost. It first establishes an extended triangle inequality bounding any agent-item distance by the other three distances, and classifies all two-element matchings as either the identity or the transposition. It then performs an exhaustive eight-way case analysis over the choice of optimal matching and the agents' top-choice items, explicitly computing the fractional assignment in each case and concluding via linear arithmetic.

  1. For all real numbers x, y, u, v, the extended triangle inequality |x - v| ≤ |x - u| + |y - u| + |y - v| holds.

    Applying the triangle inequality twice (|x - v| ≤ |x - u| + |u - v| and |u - v| ≤ |u - y| + |y - v|) and using the symmetry |u - y| = |y - u|, linear arithmetic combines the bounds into the four-point inequality.

    lines 4–9

    uses abs_sub_le, abs_sub_comm

      have tri : ∀ x y u v : ℝ, |x - v| ≤ |x - u| + |y - u| + |y - v| := by
        intro x y u v
        have h1 := abs_sub_le x u v
        have h2 := abs_sub_le u y v
        have h3 : |u - y| = |y - u| := abs_sub_comm u y
        linarith
  2. All four cyclic quadrilateral triangle inequalities hold among the agent positions {a₀, a₁} and item positions {b₀, b₁}, and every pairwise distance |aᵢ - bⱼ| is non-negative.

    The extended triangle inequality from the previous step is specialized to the four combinations of agents and items, bounding each distance |aᵢ - bⱼ| by the sum of the remaining three. Furthermore, all four pairwise distances are noted to be non-negative.

    lines 10–17

    uses abs_nonneg

      have t1 := tri (a 0) (a 1) (b 0) (b 1)
      have t2 := tri (a 0) (a 1) (b 1) (b 0)
      have t3 := tri (a 1) (a 0) (b 0) (b 1)
      have t4 := tri (a 1) (a 0) (b 1) (b 0)
      have n1 := abs_nonneg (a 0 - b 0)
      have n2 := abs_nonneg (a 0 - b 1)
      have n3 := abs_nonneg (a 1 - b 0)
      have n4 := abs_nonneg (a 1 - b 1)
  3. Every permutation of two elements is either the identity or the transposition (0 1), an optimal matching permutation σ₀ exists, and the minimum matching cost is bounded above by both matching candidates.

    Exhaustive checking confirms that the symmetric group on two elements has only two members: the identity and the swap (0 1). Since this set is finite and non-empty, a cost-minimizing matching σ₀ exists, so the optimal cost equals the matching cost at σ₀. Evaluating the definition of minimum matching cost at the identity and swap gives OPT ≤ |a₀ - b₀| + |a₁ - b₁| and OPT ≤ |a₀ - b₁| + |a₁ - b₀|.

    lines 18–25

    uses Finset.exists_mem_eq_inf', Finset.univ_nonempty, line_min_matching_cost_le, Fin.sum_univ_two, Equiv.Perm.coe_one, id, Equiv.swap_apply_left, Equiv.swap_apply_right

      have hp : ∀ π : Equiv.Perm (Fin 2), π = 1 ∨ π = Equiv.swap 0 1 := by decide
      obtain ⟨σ0, -, hσ0⟩ := Finset.exists_mem_eq_inf' (Finset.univ_nonempty (α := Equiv.Perm (Fin 2)))
        (fun σ : Equiv.Perm (Fin 2) => ∑ i, |a i - b (σ i)|)
      have hopt : line_min_matching_cost a b = ∑ i, |a i - b (σ0 i)| := hσ0
      have m1 := line_min_matching_cost_le a b 1
      have m2 := line_min_matching_cost_le a b (Equiv.swap 0 1)
      simp only [Fin.sum_univ_two, Equiv.Perm.coe_one, id, Equiv.swap_apply_left,
        Equiv.swap_apply_right] at m1 m2
  4. Each agent prefers their first-choice item over their second-choice item, and each agent's two choices are distinct.

    Specializing the distance-preference profile hypothesis to each agent i ∈ {0, 1} and rank positions 0 < 1 shows |aᵢ - b_{pref(i)(0)}| ≤ |aᵢ - b_{pref(i)(1)}|. Since each preference permutation pref(i) is injective, the first choice pref(i)(0) cannot equal the second choice pref(i)(1).

    lines 26–29

      have h0 := h 0 0 1 (by decide)
      have h1 := h 1 0 1 (by decide)
      have q0 : pref 0 1 ≠ pref 0 0 := fun e => by have := (pref 0).injective e; simp at this
      have q1 : pref 1 1 ≠ pref 1 0 := fun e => by have := (pref 1).injective e; simp at this
  5. The probabilistic serial line cost is expanded as the four-term sum X₀₀|a₀ - b₀| + X₀₁|a₀ - b₁| + X₁₀|a₁ - b₀| + X₁₁|a₁ - b₁|.

    Unfolding the definition of the probabilistic serial cost and expanding the finite sums over Fin 2 expresses the total cost explicitly in terms of the fractional assignment probabilities Xᵢⱼ and pairwise distances.

    lines 30–31

    uses Fin.sum_univ_two

      unfold probabilistic_serial_line_cost
      simp only [Fin.sum_univ_two]
  6. In all cases of optimal matchings and agent preferences, the probabilistic serial cost is at most twice the minimum matching cost.

    A case split is performed on whether the optimal matching σ₀ is the identity or the swap, and on each agent's top choice (item 0 or item 1), producing 8 cases. In each case, injectivity uniquely determines each agent's second choice. When both agents share the same top choice, they split both items equally (Xᵢⱼ = 1/2); when their top choices differ, each receives their preferred item fully (X is an integral matching). In each branch, substituting the assignments and preference inequalities into the cost allows linear arithmetic (`linarith`) to verify that the PS cost is at most 2 * OPT using the triangle and non-negativity inequalities.

    lines 32–62

    uses Fin.sum_univ_two, Equiv.Perm.coe_one, id, Equiv.swap_apply_left, Equiv.swap_apply_right, probabilistic_serial_fractional_assignment_two_same, probabilistic_serial_fractional_assignment_two_split, probabilistic_serial_fractional_assignment_two_split_swap, probabilistic_serial_fractional_assignment_two_same_one

      rcases hp σ0 with rfl | rfl <;>
      simp only [Fin.sum_univ_two, Equiv.Perm.coe_one, id, Equiv.swap_apply_left,
        Equiv.swap_apply_right] at hopt <;>
      rw [hopt] <;>
      rcases (by omega : pref 0 0 = 0 ∨ pref 0 0 = 1) with e0 | e0 <;>
      rcases (by omega : pref 1 0 = 0 ∨ pref 1 0 = 1) with e1 | e1 <;>
      [ (have f0 : pref 0 1 = 1 := by omega
         have f1 : pref 1 1 = 1 := by omega
         simp only [probabilistic_serial_fractional_assignment_two_same pref e0 e1] at *);
        (have f0 : pref 0 1 = 1 := by omega
         have f1 : pref 1 1 = 0 := by omega
         simp only [probabilistic_serial_fractional_assignment_two_split pref e0 e1] at *);
        (have f0 : pref 0 1 = 0 := by omega
         have f1 : pref 1 1 = 1 := by omega
         simp only [probabilistic_serial_fractional_assignment_two_split_swap pref e0 e1] at *);
        (have f0 : pref 0 1 = 0 := by omega
         have f1 : pref 1 1 = 0 := by omega
         simp only [probabilistic_serial_fractional_assignment_two_same_one pref e0 e1] at *);
        (have f0 : pref 0 1 = 1 := by omega
         have f1 : pref 1 1 = 1 := by omega
         simp only [probabilistic_serial_fractional_assignment_two_same pref e0 e1] at *);
        (have f0 : pref 0 1 = 1 := by omega
         have f1 : pref 1 1 = 0 := by omega
         simp only [probabilistic_serial_fractional_assignment_two_split pref e0 e1] at *);
        (have f0 : pref 0 1 = 0 := by omega
         have f1 : pref 1 1 = 1 := by omega
         simp only [probabilistic_serial_fractional_assignment_two_split_swap pref e0 e1] at *);
        (have f0 : pref 0 1 = 0 := by omega
         have f1 : pref 1 1 = 0 := by omega
         simp only [probabilistic_serial_fractional_assignment_two_same_one pref e0 e1] at *)] <;>
      rw [e0, f0] at h0 <;> rw [e1, f1] at h1 <;> norm_num at h0 h1 ⊢ <;> linarith
abs_sub_le
For elements in an ordered additive group, the absolute difference satisfies the triangle inequality |a - c| ≤ |a - b| + |b - c|.
abs_sub_comm
The absolute difference is symmetric: |a - b| = |b - a|.
abs_nonneg
The absolute value of any element is non-negative: 0 ≤ |a|.
Finset.exists_mem_eq_inf'
Any nonempty finite set s contains an element achieving the infimum of a function f over s.
Finset.univ_nonempty
The universal finset of a nonempty finite type is nonempty.
line_min_matching_cost_le
The minimum matching cost is at most the matching cost under any specific permutation σ.
Fin.sum_univ_two
A sum over the two elements of Fin 2 equals f(0) + f(1).
Equiv.Perm.coe_one
The identity permutation coerced to a function is the identity function id.
id
The identity function on any type, mapping every element to itself: id x = x.
Equiv.swap_apply_left
Applying the transposition swapping a and b to a yields b.
Equiv.swap_apply_right
Applying the transposition swapping a and b to b yields a.
probabilistic_serial_fractional_assignment_two_same
When both agents rank item 0 first, the probabilistic serial mechanism assigns fractional share 1/2 to every agent-item pair.
probabilistic_serial_fractional_assignment_two_split
When agent 0 ranks item 0 first and agent 1 ranks item 1 first, the probabilistic serial mechanism assigns each agent their first choice: X₀₀ = X₁₁ = 1 and X₀₁ = X₁₀ = 0.
probabilistic_serial_fractional_assignment_two_split_swap
When agent 0 ranks item 1 first and agent 1 ranks item 0 first, the probabilistic serial mechanism assigns each agent their first choice: X₀₁ = X₁₀ = 1 and X₀₀ = X₁₁ = 0.
probabilistic_serial_fractional_assignment_two_same_one
When both agents rank item 1 first, the probabilistic serial mechanism assigns fractional share 1/2 to every agent-item pair.

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_line_distortion_le_two_agents (a b : Fin 2 → ℝ)    (pref : Fin 2 → Equiv.Perm (Fin 2)) (h : is_line_distance_preference_profile a b pref) :    probabilistic_serial_line_cost a b pref ≤ 2 * line_min_matching_cost a b := by  have tri : ∀ x y u v : ℝ, |x - v| ≤ |x - u| + |y - u| + |y - v| := by    intro x y u v    have h1 := abs_sub_le x u v    have h2 := abs_sub_le u y v    have h3 : |u - y| = |y - u| := abs_sub_comm u y    linarith  have t1 := tri (a 0) (a 1) (b 0) (b 1)  have t2 := tri (a 0) (a 1) (b 1) (b 0)  have t3 := tri (a 1) (a 0) (b 0) (b 1)  have t4 := tri (a 1) (a 0) (b 1) (b 0)  have n1 := abs_nonneg (a 0 - b 0)  have n2 := abs_nonneg (a 0 - b 1)  have n3 := abs_nonneg (a 1 - b 0)  have n4 := abs_nonneg (a 1 - b 1)  have hp : ∀ π : Equiv.Perm (Fin 2), π = 1 ∨ π = Equiv.swap 0 1 := by decide  obtain ⟨σ0, -, hσ0⟩ := Finset.exists_mem_eq_inf' (Finset.univ_nonempty (α := Equiv.Perm (Fin 2)))    (fun σ : Equiv.Perm (Fin 2) => ∑ i, |a i - b (σ i)|)  have hopt : line_min_matching_cost a b = ∑ i, |a i - b (σ0 i)| := hσ0  have m1 := line_min_matching_cost_le a b 1  have m2 := line_min_matching_cost_le a b (Equiv.swap 0 1)  simp only [Fin.sum_univ_two, Equiv.Perm.coe_one, id, Equiv.swap_apply_left,    Equiv.swap_apply_right] at m1 m2  have h0 := h 0 0 1 (by decide)  have h1 := h 1 0 1 (by decide)  have q0 : pref 0 1 ≠ pref 0 0 := fun e => by have := (pref 0).injective e; simp at this  have q1 : pref 1 1 ≠ pref 1 0 := fun e => by have := (pref 1).injective e; simp at this  unfold probabilistic_serial_line_cost  simp only [Fin.sum_univ_two]  rcases hp σ0 with rfl | rfl <;>  simp only [Fin.sum_univ_two, Equiv.Perm.coe_one, id, Equiv.swap_apply_left,    Equiv.swap_apply_right] at hopt <;>  rw [hopt] <;>  rcases (by omega : pref 0 0 = 0 ∨ pref 0 0 = 1) with e0 | e0 <;>  rcases (by omega : pref 1 0 = 0 ∨ pref 1 0 = 1) with e1 | e1 <;>  [ (have f0 : pref 0 1 = 1 := by omega     have f1 : pref 1 1 = 1 := by omega     simp only [probabilistic_serial_fractional_assignment_two_same pref e0 e1] at *);    (have f0 : pref 0 1 = 1 := by omega     have f1 : pref 1 1 = 0 := by omega     simp only [probabilistic_serial_fractional_assignment_two_split pref e0 e1] at *);    (have f0 : pref 0 1 = 0 := by omega     have f1 : pref 1 1 = 1 := by omega     simp only [probabilistic_serial_fractional_assignment_two_split_swap pref e0 e1] at *);    (have f0 : pref 0 1 = 0 := by omega     have f1 : pref 1 1 = 0 := by omega     simp only [probabilistic_serial_fractional_assignment_two_same_one pref e0 e1] at *);    (have f0 : pref 0 1 = 1 := by omega     have f1 : pref 1 1 = 1 := by omega     simp only [probabilistic_serial_fractional_assignment_two_same pref e0 e1] at *);    (have f0 : pref 0 1 = 1 := by omega     have f1 : pref 1 1 = 0 := by omega     simp only [probabilistic_serial_fractional_assignment_two_split pref e0 e1] at *);    (have f0 : pref 0 1 = 0 := by omega     have f1 : pref 1 1 = 1 := by omega     simp only [probabilistic_serial_fractional_assignment_two_split_swap pref e0 e1] at *);    (have f0 : pref 0 1 = 0 := by omega     have f1 : pref 1 1 = 0 := by omega     simp only [probabilistic_serial_fractional_assignment_two_same_one pref e0 e1] at *)] <;>  rw [e0, f0] at h0 <;> rw [e1, f1] at h1 <;> norm_num at h0 h1 ⊢ <;> linarith
See it in the graphDiscuss this resultChallenge it