AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_equispaced_distortion_le_two_agents

theoremverifiedoriginal

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

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.

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

    line 8

    uses probabilistic_serial_line_distortion_le_two_agents

      have h_bound := probabilistic_serial_line_distortion_le_two_agents a (fun (j : Fin 2) => (j : ℝ)) pref h
  2. 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.

    lines 9–13

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

    lines 14–19

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

    lines 20–21

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

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