probabilistic_serial_line_distortion_le_two_agents
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
- 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…
- 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)}|.
- 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…
- line_min_matching_cost_leOPT is at most the cost of any perfect matching.
- probabilistic_serial_fractional_assignment_two_sameSanity check: when both of two agents rank item 0 first, probabilistic serial gives each agent half of each item.
- probabilistic_serial_fractional_assignment_two_same_oneTwo agents who both rank item 1 first each get half of each item under probabilistic serial.
- probabilistic_serial_fractional_assignment_two_splitTwo agents whose first choices are item 0 (agent 0) and item 1 (agent 1) each get their first choice entirely under probabilistic serial.
- probabilistic_serial_fractional_assignment_two_split_swapTwo agents whose first choices are item 1 (agent 0) and item 0 (agent 1) each get their first choice entirely under probabilistic serial.
- 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…
- Used by 1
- probabilistic_serial_equispaced_distortion_le_two_agentsFor two agents at real locations and two equispaced items at 0 and 1, the probabilistic serial cost under any distance preference profile…
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.
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.
uses
abs_sub_le,abs_sub_commhave 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
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.
uses
abs_nonneghave 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)
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₀|.
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_righthave 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
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).
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
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.
uses
Fin.sum_univ_twounfold probabilistic_serial_line_cost simp only [Fin.sum_univ_two]
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.
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_onercases 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.
- The eight-way case analysis across the two possible optimal matchings and four agent preference profiles is carried out in a single compound tactic block (lines 32–62), where each branch is closed by the linear arithmetic solver `linarith`.
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_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