probabilistic_serial_equispaced_distortion_two_agents_attained
For n = 2 with equispaced items at 0 and 1, agents at 0 and 1/2 with ties broken toward the smaller-index item attain the harmonic distortion bound of 2 exactly.
Statement
theorem probabilistic_serial_equispaced_distortion_two_agents_attained : ∃ pref : Fin 2 → Equiv.Perm (Fin 2), (∀ (i k k' : Fin 2), k < k' → |((if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) - ((pref i k : Fin 2) : ℝ))| < |((if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) - ((pref i k' : Fin 2) : ℝ))| ∨ (|((if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) - ((pref i k : Fin 2) : ℝ))| = |((if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) - ((pref i k' : Fin 2) : ℝ))| ∧ pref i k < pref i k')) ∧ probabilistic_serial_line_cost (fun (i : Fin 2) => if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) (fun (j : Fin 2) => (j : ℝ)) pref = (1 + (harmonic (2 / 2) : ℝ) + (harmonic ((2 - 1) / 2) : ℝ)) * line_min_matching_cost (fun (i : Fin 2) => if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) (fun (j : Fin 2) => (j : ℝ))
- Related work
- OP-1441
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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)}|.
- line_min_matching_cost_leOPT is at most the cost of any perfect matching.
- 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_fractional_assignment_two_sameSanity check: when both of two agents rank item 0 first, probabilistic serial gives each agent half of each item.
Read back from the Lean
There exists a preference profile pref : Fin 2 → Equiv.Perm (Fin 2) such that:
1. For all agents $i \in \text{Fin } 2$ and ranks $k, k' \in \text{Fin } 2$ with $k < k'$, the item ranked at position $k$, namely $\text{pref}(i)(k)$, is preferred to the item ranked at position $k'$, namely $\text{pref}(i)(k')$, according to Euclidean distance to the agent's location $a(i)$ with ties broken by smaller item index. That is, either:
- $|a(i) - \text{pref}(i)(k)| < |a(i) - \text{pref}(i)(k')|$, or
- $|a(i) - \text{pref}(i)(k)| = |a(i) - \text{pref}(i)(k')|$ and $\text{pref}(i)(k) < \text{pref}(i)(k')$,
where the agent location is $a(i) = \text{if } i.val < 2 - 1 \text{ then } (i : \mathbb{R}) \text{ else } 2 - 3/2$ (so $a(0) = 0$ and $a(1) = 0.5$), and items are embedded in $\mathbb{R}$ via their index.
2. The probabilistic serial line cost for agent locations $a$ and item locations $b$ (where $b(j) = (j : \mathbb{R})$) under pref is equal to
$$\left(1 + \text{harmonic}(2 / 2) + \text{harmonic}((2 - 1) / 2)\right) \cdot \text{line\_min\_matching\_cost}(a, b),$$
where division inside harmonic is natural number division (so $2/2 = 1$ and $(2-1)/2 = 0$, giving $1 + \text{harmonic}(1) + \text{harmonic}(0) = 2$).
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 shows that for two items at positions 0 and 1, placing two agents at 0 and 1/2 attains the harmonic distortion bound of 2 exactly under the probabilistic serial mechanism. Under tie-breaking toward the smaller index, both agents strictly prefer item 0 to item 1, so probabilistic serial equally splits each item between the two agents, resulting in an expected social cost of 1. By contrast, the optimal offline matching assigns agent 0 to item 0 and agent 1 to item 1 for a cost of 1/2, making the ratio exactly 1 / (1/2) = 2.
It suffices to show that the identity preference profile satisfies metric consistency with tie-breaking and attains the harmonic distortion equality.
We provide the witness where each agent has preference order given by the identity permutation (ranking item 0 ahead of item 1). The goal splits into confirming that this preference profile respects distance and tie-breaking, and verifying the cost equation.
use fun _ => 1 constructor
The identity preference profile correctly represents the metric distances and tie-breaking for both agents.
For two items, the condition k < k' forces k = 0 and k' = 1. For agent 0 located at 0, item 0 is strictly closer than item 1 since |0 - 0| = 0 < 1 = |0 - 1|. For agent 1 located at 1/2, item 0 and item 1 are equidistant (|1/2 - 0| = |1/2 - 1| = 1/2), and the tie-breaking rule selects the smaller-index item 0 since 0 < 1.
uses
Equiv.Perm.coe_one,id· intro i k k' h have : k = 0 ∧ k' = 1 := by fin_cases k <;> fin_cases k' <;> try omega rcases this with ⟨rfl, rfl⟩ fin_cases i · left simp only [Equiv.Perm.coe_one, id] norm_num · right simp only [Equiv.Perm.coe_one, id] norm_num
The harmonic distortion factor 1 + H_{2/2} + H_{(2-1)/2} equals 2.
Under natural number division, 2 / 2 = 1 and (2 - 1) / 2 = 0. The 0-th harmonic number is 0 by harmonic_zero, and the 1st harmonic number is 1 by harmonic_succ. Adding 1 + 1 + 0 gives 2.
uses
harmonic_zero,harmonic_succ· have h_harm_0 : harmonic 0 = 0 := harmonic_zero have h_harm_1 : harmonic 1 = 1 := by change harmonic (0 + 1) = 1 rw [harmonic_succ, harmonic_zero] simp have h_coef : (1 + (harmonic (2 / 2) : ℝ) + (harmonic ((2 - 1) / 2) : ℝ)) = 2 := by have h1 : 2 / 2 = 1 := rfl have h0 : (2 - 1) / 2 = 0 := rfl rw [h1, h0, h_harm_0, h_harm_1] push_cast ring
The probabilistic serial line cost under this preference profile is 1.
Because both agents have item 0 as their top choice, the probabilistic serial mechanism allocates a share of 1/2 of each item to each agent. Summing the fractional assignment times the Euclidean distance across all pairs of agents and items gives (1/2)(0) + (1/2)(1) + (1/2)(1/2) + (1/2)(1/2) = 1.
uses
Fin.sum_univ_two,probabilistic_serial_fractional_assignment_two_samehave h_ps : probabilistic_serial_line_cost (fun (i : Fin 2) => if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) (fun (j : Fin 2) => (j : ℝ)) (fun _ => 1) = 1 := by unfold probabilistic_serial_line_cost simp only [Fin.sum_univ_two] simp only [probabilistic_serial_fractional_assignment_two_same (fun _ => 1) rfl rfl] norm_num
The minimum matching cost is 1/2.
We prove the minimum matching cost equals 1/2 by showing both inequalities: the upper bound is verified by testing the identity matching, which incurs cost |0 - 0| + |1/2 - 1| = 1/2; the lower bound follows because the symmetric group on two elements consists only of the identity and the swap (0 1), with the swap having cost |0 - 1| + |1/2 - 0| = 3/2 ≥ 1/2.
uses
le_antisymm,line_min_matching_cost_le,Fin.sum_univ_two,Equiv.Perm.coe_one,id,Finset.le_inf',Equiv.swap_apply_left,Equiv.swap_apply_righthave h_opt : line_min_matching_cost (fun (i : Fin 2) => if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) (fun (j : Fin 2) => (j : ℝ)) = 1 / 2 := by apply le_antisymm · have h := line_min_matching_cost_le (fun (i : Fin 2) => if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) (fun (j : Fin 2) => (j : ℝ)) 1 simp only [Fin.sum_univ_two, Equiv.Perm.coe_one, id] at h norm_num at h ⊢ exact h · unfold line_min_matching_cost apply Finset.le_inf' intro σ _ have hp : ∀ π : Equiv.Perm (Fin 2), π = 1 ∨ π = Equiv.swap 0 1 := by decide rcases hp σ with rfl | rfl · simp only [Fin.sum_univ_two, Equiv.Perm.coe_one, id] norm_num · simp only [Fin.sum_univ_two, Equiv.swap_apply_left, Equiv.swap_apply_right] norm_num
The probabilistic serial line cost equals the harmonic coefficient times the minimum matching cost.
Substituting the calculated values—a harmonic coefficient of 2, a probabilistic serial cost of 1, and an optimal matching cost of 1/2—the identity 1 = 2 * (1/2) holds by elementary arithmetic.
rw [h_coef, h_ps, h_opt] norm_num
Equiv.Perm.coe_one- coercing the identity permutation to a function yields the identity function
id- the identity function, which maps every element to itself
harmonic_zero- the 0-th harmonic number is 0
harmonic_succ- the (n + 1)-th harmonic number equals the n-th harmonic number plus 1 / (n + 1)
Fin.sum_univ_two- a sum over the two elements of Fin 2 equals the value at 0 plus the value at 1
probabilistic_serial_fractional_assignment_two_same- when both agents in a two-agent instance rank item 0 first, the probabilistic serial mechanism allocates each agent an equal fraction of 1/2 of each item
le_antisymm- if a ≤ b and b ≤ a, then a = b
line_min_matching_cost_le- the minimum matching cost is bounded above by the cost of any specific matching permutation
Finset.le_inf'- a lower bound on all values in a nonempty finite set is a lower bound on its infimum
Equiv.swap_apply_left- the transposition of a and b maps a to b
Equiv.swap_apply_right- the transposition of a and b maps b to a
- In the theorem statement, the expressions `2 / 2` and `(2 - 1) / 2` in the harmonic index are computed using natural number division, evaluating to 1 and 0 respectively.
- The conditional `if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2` positions agent 0 at 0 and agent 1 at 1/2.
- The fact that the symmetric group on two elements contains only the identity and transposition is checked by the `decide` decision procedure via finite enumeration.
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.
/-- Sharpness of OP-1441 for n = 2: the harmonic distortion bound is attained by agents at 0 and 1/2. -/theorem probabilistic_serial_equispaced_distortion_two_agents_attained : ∃ pref : Fin 2 → Equiv.Perm (Fin 2), (∀ (i k k' : Fin 2), k < k' → |((if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) - ((pref i k : Fin 2) : ℝ))| < |((if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) - ((pref i k' : Fin 2) : ℝ))| ∨ (|((if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) - ((pref i k : Fin 2) : ℝ))| = |((if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) - ((pref i k' : Fin 2) : ℝ))| ∧ pref i k < pref i k')) ∧ probabilistic_serial_line_cost (fun (i : Fin 2) => if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) (fun (j : Fin 2) => (j : ℝ)) pref = (1 + (harmonic (2 / 2) : ℝ) + (harmonic ((2 - 1) / 2) : ℝ)) * line_min_matching_cost (fun (i : Fin 2) => if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) (fun (j : Fin 2) => (j : ℝ)) := by use fun _ => 1 constructor · intro i k k' h have : k = 0 ∧ k' = 1 := by fin_cases k <;> fin_cases k' <;> try omega rcases this with ⟨rfl, rfl⟩ fin_cases i · left simp only [Equiv.Perm.coe_one, id] norm_num · right simp only [Equiv.Perm.coe_one, id] norm_num · have h_harm_0 : harmonic 0 = 0 := harmonic_zero have h_harm_1 : harmonic 1 = 1 := by change harmonic (0 + 1) = 1 rw [harmonic_succ, harmonic_zero] simp have h_coef : (1 + (harmonic (2 / 2) : ℝ) + (harmonic ((2 - 1) / 2) : ℝ)) = 2 := by have h1 : 2 / 2 = 1 := rfl have h0 : (2 - 1) / 2 = 0 := rfl rw [h1, h0, h_harm_0, h_harm_1] push_cast ring have h_ps : probabilistic_serial_line_cost (fun (i : Fin 2) => if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) (fun (j : Fin 2) => (j : ℝ)) (fun _ => 1) = 1 := by unfold probabilistic_serial_line_cost simp only [Fin.sum_univ_two] simp only [probabilistic_serial_fractional_assignment_two_same (fun _ => 1) rfl rfl] norm_num have h_opt : line_min_matching_cost (fun (i : Fin 2) => if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) (fun (j : Fin 2) => (j : ℝ)) = 1 / 2 := by apply le_antisymm · have h := line_min_matching_cost_le (fun (i : Fin 2) => if i.val < 2 - 1 then (i : ℝ) else (2 : ℝ) - 3 / 2) (fun (j : Fin 2) => (j : ℝ)) 1 simp only [Fin.sum_univ_two, Equiv.Perm.coe_one, id] at h norm_num at h ⊢ exact h · unfold line_min_matching_cost apply Finset.le_inf' intro σ _ have hp : ∀ π : Equiv.Perm (Fin 2), π = 1 ∨ π = Equiv.swap 0 1 := by decide rcases hp σ with rfl | rfl · simp only [Fin.sum_univ_two, Equiv.Perm.coe_one, id] norm_num · simp only [Fin.sum_univ_two, Equiv.swap_apply_left, Equiv.swap_apply_right] norm_num rw [h_coef, h_ps, h_opt] norm_num