AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_equispaced_distortion_two_agents_attained

theoremverifiedoriginal

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

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.

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

    lines 17–18

      use fun _ => 1
      constructor
  2. 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.

    lines 19–29

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

    lines 30–40

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

    lines 41–47

    uses Fin.sum_univ_two, probabilistic_serial_fractional_assignment_two_same

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

    lines 48–66

    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_right

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

    lines 67–68

        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

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

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