probabilistic_serial_equispaced_distortion_le_two_agents
For two agents at real locations and two equispaced items at 0 and 1, the probabilistic serial cost under any distance preference profile is at most [1 + H_1 + H_0] = 2 times the minimum matching cost OPT.
Statement
theorem probabilistic_serial_equispaced_distortion_le_two_agents (a : Fin 2 → ℝ) (pref : Fin 2 → Equiv.Perm (Fin 2)) (h : is_line_distance_preference_profile a (fun (j : Fin 2) => (j : ℝ)) pref) : probabilistic_serial_line_cost a (fun (j : Fin 2) => (j : ℝ)) pref ≤ (1 + (harmonic (2 / 2) : ℝ) + (harmonic ((2 - 1) / 2) : ℝ)) * line_min_matching_cost a (fun (j : Fin 2) => (j : ℝ))
- Related work
- OP-1441
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- probabilistic_serial_line_distortion_le_two_agentsCase 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…
- 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…
Read back from the Lean
For any two agents with positions a : Fin 2 → ℝ on the real line and preference profiles pref : Fin 2 → Equiv.Perm (Fin 2) over two equispaced items located at positions 0 and 1 (given by j ↦ (j : ℝ) for j : Fin 2), if pref reflects line-distance preferences (meaning each agent weakly prefers closer items to farther items), then the social cost under the Probabilistic Serial mechanism is at most (1 + harmonic 1 + harmonic 0) times (which equals 2 times) the minimum matching social cost.
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 establishes the harmonic distortion bound for two agents and equispaced items at 0 and 1 by reducing it to the known upper bound of 2 for two agents on a line. It first invokes probabilistic_serial_line_distortion_le_two_agents to bound the probabilistic serial cost by 2 times the minimum matching cost. It then computes the harmonic numbers H_0 = 0 and H_1 = 1 via natural number division, showing that the coefficient 1 + H_{2/2} + H_{(2-1)/2} is exactly 2.
The probabilistic serial cost for two agents at item positions 0 and 1 is at most twice the minimum matching cost.
We apply probabilistic_serial_line_distortion_le_two_agents to the agent locations a and item locations j ↦ (j : ℝ), which establishes that the probabilistic serial line cost is bounded by 2 times the optimal matching cost.
uses
probabilistic_serial_line_distortion_le_two_agentshave h_bound := probabilistic_serial_line_distortion_le_two_agents a (fun (j : Fin 2) => (j : ℝ)) pref h
The harmonic numbers H_0 and H_1 equal 0 and 1, respectively.
The base case H_0 = 0 is given directly by harmonic_zero. For H_1, rewriting 1 as 0 + 1 and applying the recurrence harmonic_succ together with harmonic_zero reduces H_1 to 0 + 1⁻¹ = 1.
uses
harmonic_zero,harmonic_succhave 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
The harmonic coefficient 1 + H_{2/2} + H_{(2-1)/2} evaluates to 2.
By natural number division, 2 / 2 = 1 and (2 - 1) / 2 = 0. Substituting these indices and the values H_1 = 1 and H_0 = 0 into the sum gives 1 + 1 + 0, which evaluates to 2 by ring arithmetic.
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 cost is at most (1 + H_{2/2} + H_{(2-1)/2}) times the minimum matching cost.
Rewriting the coefficient in the target inequality with 2 transforms the goal into the bound established in the first step, which completes the proof.
rw [h_coef] exact h_bound
probabilistic_serial_line_distortion_le_two_agents- For any two agents and two item positions on the real line, the probabilistic serial cost is at most 2 times the minimum matching cost.
harmonic_zero- The 0th harmonic number is 0.
harmonic_succ- For any natural number n, the (n + 1)-th harmonic number equals the n-th harmonic number plus 1 / (n + 1).
- In the harmonic coefficient expression, the operations 2 / 2 and (2 - 1) / 2 represent natural number division (truncating division on ℕ), so (2 - 1) / 2 evaluates to 1 / 2 = 0.
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.
/-- Case n = 2 of OP-1441: the harmonic distortion upper bound holds for two agents and equispaced items. -/theorem probabilistic_serial_equispaced_distortion_le_two_agents (a : Fin 2 → ℝ) (pref : Fin 2 → Equiv.Perm (Fin 2)) (h : is_line_distance_preference_profile a (fun (j : Fin 2) => (j : ℝ)) pref) : probabilistic_serial_line_cost a (fun (j : Fin 2) => (j : ℝ)) pref ≤ (1 + (harmonic (2 / 2) : ℝ) + (harmonic ((2 - 1) / 2) : ℝ)) * line_min_matching_cost a (fun (j : Fin 2) => (j : ℝ)) := by have h_bound := probabilistic_serial_line_distortion_le_two_agents a (fun (j : Fin 2) => (j : ℝ)) pref h 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 rw [h_coef] exact h_bound