probabilistic_serial_equispaced_distortion_le_three_agents
For three agents at real locations and three equispaced items at 0, 1, and 2, the probabilistic serial cost under any distance preference profile is at most [1 + H_1 + H_1] = 3 times the minimum matching cost OPT.
Statement
theorem probabilistic_serial_equispaced_distortion_le_three_agents (a : Fin 3 → ℝ) (pref : Fin 3 → Equiv.Perm (Fin 3)) (h : is_line_distance_preference_profile a (fun (j : Fin 3) => (j : ℝ)) pref) : probabilistic_serial_line_cost a (fun (j : Fin 3) => (j : ℝ)) pref ≤ (1 + (harmonic (3 / 2) : ℝ) + (harmonic ((3 - 1) / 2) : ℝ)) * line_min_matching_cost a (fun (j : Fin 3) => (j : ℝ))
- Related work
- OP-1441
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- probabilistic_serial_line_distortion_le_three_agentsCase 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…
- 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 3 agent positions a : Fin 3 → ℝ and any preference profile pref : Fin 3 → Equiv.Perm (Fin 3), if pref is consistent with distances from the agents to three equispaced facilities located at 0, 1, 2 on the real line (meaning that for every agent i : Fin 3 and every pair of preference ranks k < k', the facility pref i k is weakly closer to a i than pref i k'), then the probabilistic serial line cost of a with respect to the equispaced facilities (at j : ℝ for j : Fin 3) under pref is at most (1 + harmonic (3 / 2) + harmonic ((3 - 1) / 2)) * line_min_matching_cost a (fun j => (j : ℝ)) (which evaluates to 3 times the minimum matching 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 theorem proves the case of three agents and three equispaced items for the harmonic distortion conjecture. Truncating integer division reduces the harmonic upper bound factor 1 + H_{3/2} + H_{(3-1)/2} to 1 + H_1 + H_1 = 3. The claim then follows directly from the previously established general distortion bound of 3 for three agents on a line.
The upper bound coefficient simplifies to 3, so it suffices to show that the probabilistic serial cost is at most 3 times the minimum matching cost.
In natural number arithmetic, the integer divisions yield 3 / 2 = 1 and (3 - 1) / 2 = 1. Since the first harmonic number H₁ = 1, the sum 1 + H₁ + H₁ evaluates to 3. The proof verifies this numerical identity h3 with `norm_num` and rewrites it into the goal, replacing the harmonic factor with 3.
have h3 : (1 + (harmonic (3 / 2) : ℝ) + (harmonic ((3 - 1) / 2) : ℝ)) = 3 := by norm_num rw [h3]
The probabilistic serial cost for three agents and three equispaced items is at most 3 times the minimum matching cost, concluding the proof.
With the coefficient rewritten to 3, the goal matches the theorem `probabilistic_serial_line_distortion_le_three_agents`, which bounds the probabilistic serial distortion on a line by 3 for three agents under distance-based preferences. Specializing item positions to 0, 1, and 2 closes the goal.
uses
probabilistic_serial_line_distortion_le_three_agentsexact probabilistic_serial_line_distortion_le_three_agents a (fun j => (j : ℝ)) pref h
probabilistic_serial_line_distortion_le_three_agents- For any three agents and three items on the real line where preferences are induced by Euclidean distance, the probabilistic serial cost is at most 3 times the minimum matching cost.
- The divisions in the harmonic term indices, `3 / 2` and `(3 - 1) / 2`, represent truncating integer division in ℕ, both evaluating to 1.
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 = 3 of OP-1441: the harmonic distortion upper bound holds for three agents and equispaced items. -/theorem probabilistic_serial_equispaced_distortion_le_three_agents (a : Fin 3 → ℝ) (pref : Fin 3 → Equiv.Perm (Fin 3)) (h : is_line_distance_preference_profile a (fun (j : Fin 3) => (j : ℝ)) pref) : probabilistic_serial_line_cost a (fun (j : Fin 3) => (j : ℝ)) pref ≤ (1 + (harmonic (3 / 2) : ℝ) + (harmonic ((3 - 1) / 2) : ℝ)) * line_min_matching_cost a (fun (j : Fin 3) => (j : ℝ)) := by have h3 : (1 + (harmonic (3 / 2) : ℝ) + (harmonic ((3 - 1) / 2) : ℝ)) = 3 := by norm_num rw [h3] exact probabilistic_serial_line_distortion_le_three_agents a (fun j => (j : ℝ)) pref h