AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_equispaced_distortion_le_three_agents

theoremverifiedoriginal

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

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.

  1. 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.

    lines 8–9

      have h3 : (1 + (harmonic (3 / 2) : ℝ) + (harmonic ((3 - 1) / 2) : ℝ)) = 3 := by norm_num
      rw [h3]
  2. 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.

    line 10

    uses probabilistic_serial_line_distortion_le_three_agents

      exact 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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it