probabilistic_serial_line_distortion_le_three_agents
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
- probabilistic_serial_line_three_agents_le_of_first_choices_01Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 0 first and item 1 second. For three agents…
- probabilistic_serial_line_three_agents_le_of_first_choices_02Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 0 first and item 2 second. For three agents…
- probabilistic_serial_line_three_agents_le_of_first_choices_10Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 1 first and item 0 second. For three agents…
- probabilistic_serial_line_three_agents_le_of_first_choices_12Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 1 first and item 2 second. For three agents…
- probabilistic_serial_line_three_agents_le_of_first_choices_20Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 2 first and item 0 second. For three agents…
- probabilistic_serial_line_three_agents_le_of_first_choices_21Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 2 first and item 1 second. For three agents…
- line_min_matching_costOPT: the minimum, over all permutations sigma of the n items, of the matching cost sum_i |a_i - b_{sigma(i)}|.
- probabilistic_serial_line_costThe cost of the probabilistic serial assignment X for agents at a and items at b on the real line: PS = sum over agents i and items j of…
- is_line_distance_preference_profileThere are n agents and n items, both indexed by {0, ..., n-1}; agent i sits at the real position a_i and item j at b_j. Each agent's…
- Used by 1
- probabilistic_serial_equispaced_distortion_le_three_agentsFor three agents at real locations and three equispaced items at 0, 1, and 2, the probabilistic serial cost under any distance preference…
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 σ₀.
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 σ₀.
uses
Finset.exists_mem_eq_inf',Finset.univ_nonemptyobtain ⟨σ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]
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).
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
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)}|.
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_21rcases 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 σ.
- The core geometric and case-specific inequalities are established in six helper lemmas (probabilistic_serial_line_three_agents_le_of_first_choices_*); this proof serves as the top-level case analysis dispatching to them.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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