AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_line_distortion_le_three_agents

theoremverifiedoriginal

Case n = 3 of OP-1158: for three agents at real positions a_0, a_1, a_2 and three items at real positions b_0, b_1, b_2, 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 3 times the minimum perfect-matching cost.

Statement

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

Read back from the Lean

For any agent locations $a : \text{Fin } 3 \to \mathbb{R}$ and item locations $b : \text{Fin } 3 \to \mathbb{R}$ on the real line, and any preference profile $\text{pref} : \text{Fin } 3 \to \text{Equiv.Perm}(\text{Fin } 3)$, if $\text{pref}$ is distance-consistent with $a$ and $b$ (meaning that for every agent $i : \text{Fin } 3$ and all ranks $k < k'$, the distance $|a(i) - b(\text{pref}(i)(k))| \le |a(i) - b(\text{pref}(i)(k'))|$), then the expected social cost of the assignment generated by the Probabilistic Serial mechanism on $(a, b, \text{pref})$ is at most 3 times the minimum matching cost between $a$ and $b$ (the minimum over all permutations $\sigma \in \text{Equiv.Perm}(\text{Fin } 3)$ of $\sum_{i} |a(i) - b(\sigma(i))|$).

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 theorem is proved by choosing a concrete permutation σ₀ achieving the minimum matching cost and performing a case analysis on the first two choices of agent 0. Because preferences are permutations, agent 0's top two choices are distinct, leaving six possible pairs in {0, 1, 2}. For each pair, the distortion bound is discharged by a dedicated lemma establishing that the probabilistic serial line cost is at most 3 times the matching cost under σ₀.

  1. There exists an optimal matching permutation σ₀ attaining the minimum matching cost, reducing the goal to showing that the probabilistic serial cost is at most 3 ∑ᵢ |aᵢ - b_{σ₀(i)}|.

    Since the set of permutations of three items is finite and non-empty (Finset.univ_nonempty), the infimum defining the minimum matching cost is achieved by some permutation σ₀ (by Finset.exists_mem_eq_inf'). Rewriting the definition of line_min_matching_cost with this permutation reduces the goal to bounding the cost against σ₀.

    lines 4–7

    uses Finset.exists_mem_eq_inf', Finset.univ_nonempty

      obtain ⟨σ0, -, hσ0⟩ := Finset.exists_mem_eq_inf' (Finset.univ_nonempty (α := Equiv.Perm (Fin 3)))
        (fun σ : Equiv.Perm (Fin 3) => ∑ i, |a i - b (σ i)|)
      have hopt : line_min_matching_cost a b = ∑ i, |a i - b (σ0 i)| := hσ0
      rw [hopt]
  2. Agent 0's top two preferred items are distinct, leaving six possible ordered pairs in {0, 1, 2}.

    Because agent 0's preference ranking is a permutation (in particular, injective), the top choice pref(0)(0) and the second choice pref(0)(1) cannot coincide. Exhaustive case evaluation on Fin 3 shows that any two distinct elements must be one of the pairs (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), or (2, 1).

    lines 8–10

      have hne : pref 0 0 ≠ pref 0 1 := (pref 0).injective.ne (by decide)
      have key : ∀ x y : Fin 3, x ≠ y → (x = 0 ∧ y = 1) ∨ (x = 0 ∧ y = 2) ∨ (x = 1 ∧ y = 0) ∨
          (x = 1 ∧ y = 2) ∨ (x = 2 ∧ y = 0) ∨ (x = 2 ∧ y = 1) := by decide
  3. In each of the six preference orderings for agent 0, the probabilistic serial cost is at most 3 times the cost of the optimal matching σ₀.

    We perform a case analysis on the six possible pairs of first and second choices for agent 0. Each case is discharged by a corresponding specialized lemma (probabilistic_serial_line_three_agents_le_of_first_choices_01 through _21), each showing that the probabilistic serial cost is bounded by 3 ∑ᵢ |aᵢ - b_{σ₀(i)}|.

    lines 11–17

    uses probabilistic_serial_line_three_agents_le_of_first_choices_01, probabilistic_serial_line_three_agents_le_of_first_choices_02, probabilistic_serial_line_three_agents_le_of_first_choices_10, probabilistic_serial_line_three_agents_le_of_first_choices_12, probabilistic_serial_line_three_agents_le_of_first_choices_20, probabilistic_serial_line_three_agents_le_of_first_choices_21

      rcases key _ _ hne with ⟨hx, hy⟩ | ⟨hx, hy⟩ | ⟨hx, hy⟩ | ⟨hx, hy⟩ | ⟨hx, hy⟩ | ⟨hx, hy⟩
      · exact probabilistic_serial_line_three_agents_le_of_first_choices_01 a b pref h hx hy σ0
      · exact probabilistic_serial_line_three_agents_le_of_first_choices_02 a b pref h hx hy σ0
      · exact probabilistic_serial_line_three_agents_le_of_first_choices_10 a b pref h hx hy σ0
      · exact probabilistic_serial_line_three_agents_le_of_first_choices_12 a b pref h hx hy σ0
      · exact probabilistic_serial_line_three_agents_le_of_first_choices_20 a b pref h hx hy σ0
      · exact probabilistic_serial_line_three_agents_le_of_first_choices_21 a b pref h hx hy σ0
Finset.exists_mem_eq_inf'
In a non-empty finite set with a linear order, the infimum of a function is attained at some element of the set.
Finset.univ_nonempty
The universal finset of an inhabited finite type is non-empty.
probabilistic_serial_line_three_agents_le_of_first_choices_01
For three agents and items on the real line, if agent 0 ranks item 0 first and item 1 second, the probabilistic serial assignment cost is at most 3 times the matching cost under any permutation σ.
probabilistic_serial_line_three_agents_le_of_first_choices_02
For three agents and items on the real line, if agent 0 ranks item 0 first and item 2 second, the probabilistic serial assignment cost is at most 3 times the matching cost under any permutation σ.
probabilistic_serial_line_three_agents_le_of_first_choices_10
For three agents and items on the real line, if agent 0 ranks item 1 first and item 0 second, the probabilistic serial assignment cost is at most 3 times the matching cost under any permutation σ.
probabilistic_serial_line_three_agents_le_of_first_choices_12
For three agents and items on the real line, if agent 0 ranks item 1 first and item 2 second, the probabilistic serial assignment cost is at most 3 times the matching cost under any permutation σ.
probabilistic_serial_line_three_agents_le_of_first_choices_20
For three agents and items on the real line, if agent 0 ranks item 2 first and item 0 second, the probabilistic serial assignment cost is at most 3 times the matching cost under any permutation σ.
probabilistic_serial_line_three_agents_le_of_first_choices_21
For three agents and items on the real line, if agent 0 ranks item 2 first and item 1 second, the probabilistic serial assignment cost is at most 3 times the matching cost under any permutation σ.

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_three_agents (a b : Fin 3 → ℝ)    (pref : Fin 3 → Equiv.Perm (Fin 3)) (h : is_line_distance_preference_profile a b pref) :    probabilistic_serial_line_cost a b pref ≤ 3 * line_min_matching_cost a b := by  obtain ⟨σ0, -, hσ0⟩ := Finset.exists_mem_eq_inf' (Finset.univ_nonempty (α := Equiv.Perm (Fin 3)))    (fun σ : Equiv.Perm (Fin 3) => ∑ i, |a i - b (σ i)|)  have hopt : line_min_matching_cost a b = ∑ i, |a i - b (σ0 i)| := hσ0  rw [hopt]  have hne : pref 0 0 ≠ pref 0 1 := (pref 0).injective.ne (by decide)  have key : ∀ x y : Fin 3, x ≠ y → (x = 0 ∧ y = 1) ∨ (x = 0 ∧ y = 2) ∨ (x = 1 ∧ y = 0) ∨      (x = 1 ∧ y = 2) ∨ (x = 2 ∧ y = 0) ∨ (x = 2 ∧ y = 1) := by decide  rcases key _ _ hne with ⟨hx, hy⟩ | ⟨hx, hy⟩ | ⟨hx, hy⟩ | ⟨hx, hy⟩ | ⟨hx, hy⟩ | ⟨hx, hy⟩  · exact probabilistic_serial_line_three_agents_le_of_first_choices_01 a b pref h hx hy σ0  · exact probabilistic_serial_line_three_agents_le_of_first_choices_02 a b pref h hx hy σ0  · exact probabilistic_serial_line_three_agents_le_of_first_choices_10 a b pref h hx hy σ0  · exact probabilistic_serial_line_three_agents_le_of_first_choices_12 a b pref h hx hy σ0  · exact probabilistic_serial_line_three_agents_le_of_first_choices_20 a b pref h hx hy σ0  · exact probabilistic_serial_line_three_agents_le_of_first_choices_21 a b pref h hx hy σ0
See it in the graphDiscuss this resultChallenge it