AFTD Auto-Formalizing Theoretical Domains

fixed_dictator_social_cost_le_of_singletons

theoremverified

Case 2 of Theorem 4.5: with no agent approving both facilities, if F_1 is at a closest candidate w_1 of an agent i approving F_1 and F_2 at a closest available candidate w_2 (≠ w_1) of an agent j approving F_2, then SC(w) ≤ (2n-1) SC(o) for every feasible o.

Statement

theorem fixed_dictator_social_cost_le_of_singletons {ι X : Type*} [Fintype ι] [MetricSpace X] [DecidableEq X]
    (C : Finset X) (x : ι → X) (p : ι → Fin 2 → Bool)
    (hnd : ∀ a, ¬ (p a 0 = true ∧ p a 1 = true)) (w : Fin 2 → X) (i j : ι)
    (hi : p i 0 = true) (hj : p j 1 = true)
    (hw0 : IsClosestCandidate C (x i) (w 0)) (hw1 : IsClosestCandidate (C.erase (w 0)) (x j) (w 1))
    (o : Fin 2 → X) (ho : IsTwoFacilityFeasible C o) :
    two_facility_social_cost x p w ≤ (2 * (Fintype.card ι : ℝ) - 1) * two_facility_social_cost x p o
Source
Case 2 of the proof of Theorem 4.5 of arXiv:2610.18006 (Truthful two-facility location with candidate locations in metric spaces); serves fixed_dictator_social_cost_le
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1
  • fixed_dictator_social_cost_leOn a general metric space, for n ≥ 2 agents with known non-empty approval preferences over two facilities and any candidate set C, every…

The proof, explained

The proof bounds the social cost of the chosen candidates w against an arbitrary feasible location profile o by analyzing the displacement of each facility. Because agent i approves only facility 0 and agent j approves only facility 1, the chosen locations w(0) and w(1) are placed near optimal candidates, bounding their displacements from o(0) and o(1) by E = 2(c_i + c_j), where c_i and c_j are the optimal costs of agents i and j. By the triangle inequality, each of the other n - 1 agents incurs an additional cost of at most E, while agent i incurs no extra cost at all. Summing these bounds and using c_i + c_j ≤ SC(o) yields SC(w) ≤ SC(o) + 2(n - 1)(c_i + c_j) ≤ (2n - 1) SC(o).

  1. The candidates o(0) and o(1) are distinct elements of C, agents i and j approve only their respective facilities, and i ≠ j.

    From the feasibility hypothesis ho, o(0), o(1) ∈ C with o(0) ≠ o(1). The condition hnd that no agent approves both facilities implies that agent i (who approves facility 0) does not approve facility 1 (p i 1 = false), and agent j (who approves facility 1) does not approve facility 0 (p j 0 = false). If i = j, agent i would approve both 0 and 1, which is impossible; hence i ≠ j.

    lines 8–19

    uses Bool.noConfusion

      classical
      obtain ⟨ho0, ho1, ho01⟩ := ho
      have hi1 : p i 1 = false := by
        cases h : p i 1
        · rfl
        · exact absurd ⟨hi, h⟩ (hnd i)
      have hj0 : p j 0 = false := by
        cases h : p j 0
        · rfl
        · exact absurd ⟨h, hj⟩ (hnd j)
      have hij : i ≠ j := by
        rintro rfl; rw [hi] at hj0; exact Bool.noConfusion hj0
  2. An agent's cost is the sum of the distances to the facilities they approve, and is always nonnegative.

    Unfolding two_facility_cost expresses the cost over Fin 2 as the sum of distances to approved facilities using Fin.sum_univ_two. Since metric distances are nonnegative (dist_nonneg), their sum is also nonnegative (add_nonneg).

    lines 20–25

    uses Fin.sum_univ_two, add_nonneg, dist_nonneg

      have cost_eq : ∀ a (c : Fin 2 → X), two_facility_cost x p a c =
          (if p a 0 then dist (x a) (c 0) else 0) + (if p a 1 then dist (x a) (c 1) else 0) := by
        intro a c; simp [two_facility_cost, Fin.sum_univ_two]
      have cost_nonneg : ∀ a (c : Fin 2 → X), 0 ≤ two_facility_cost x p a c := by
        intro a c; rw [cost_eq]
        apply add_nonneg <;> split_ifs <;> simp [dist_nonneg]
  3. Agents i and j have optimal costs c_i = dist(x i, o 0) and c_j = dist(x j, o 1), the chosen facility w(0) is at distance at most c_i from agent i, and we define E = 2(c_i + c_j) ≥ 0.

    Because agent i approves only facility 0 and agent j approves only facility 1, their costs under o simplify to c_i = dist(x i, o 0) and c_j = dist(x j, o 1). Because w(0) is a closest candidate in C to x i and o(0) ∈ C, dist(x i, w 0) ≤ c_i. We define the displacement scale E = 2(c_i + c_j), which is nonnegative because distances are nonnegative (dist_nonneg).

    lines 26–33

    uses dist_nonneg

      set ci := dist (x i) (o 0) with hci
      set cj := dist (x j) (o 1) with hcj
      have hci' : two_facility_cost x p i o = ci := by rw [cost_eq]; simp [hi, hi1, hci]
      have hcj' : two_facility_cost x p j o = cj := by rw [cost_eq]; simp [hj, hj0, hcj]
      have hi_w0 : dist (x i) (w 0) ≤ ci := hw0.2 _ ho0
      set E := 2 * (ci + cj) with hE
      have hci0 : 0 ≤ ci := dist_nonneg
      have hcj0 : 0 ≤ cj := dist_nonneg
  4. The displacement of facility 0 satisfies dist(o 0, w 0) ≤ E.

    By the triangle inequality (dist_triangle) and symmetry of distance (dist_comm), dist(o 0, w 0) ≤ dist(x i, o 0) + dist(x i, w 0) ≤ c_i + c_i = 2 c_i ≤ E.

    lines 34–38

    uses dist_triangle, dist_comm

      -- the two displacement bounds
      have hD0 : dist (o 0) (w 0) ≤ E := by
        have := dist_triangle (o 0) (x i) (w 0)
        rw [dist_comm (o 0) (x i)] at this
        linarith
  5. The displacement of facility 1 satisfies dist(o 1, w 1) ≤ E.

    We split into cases on whether w(0) = o(1). If w(0) = o(1), then o(0) ≠ w(0), so o(0) remains available in C.erase (w 0) (Finset.mem_erase.2). By the choice of w(1), dist(x j, w 1) ≤ dist(x j, o 0). The triangle inequality on (w 0, x i, o 0) gives dist(o 1, o 0) ≤ 2 c_i, and triangle inequalities on (x j, o 1, o 0) and (o 1, x j, w 1) then bound dist(o 1, w 1) by c_j + (c_j + 2 c_i) = E. Otherwise, w(0) ≠ o(1), so o(1) ∈ C.erase (w 0) (Finset.mem_erase.2, Ne.symm), giving dist(x j, w 1) ≤ c_j, and the triangle inequality bounds dist(o 1, w 1) by 2 c_j ≤ E.

    lines 39–56

    uses Finset.mem_erase.2, Ne.symm, dist_triangle, dist_comm

      have hD1 : dist (o 1) (w 1) ≤ E := by
        by_cases hwo : w 0 = o 1
        · have ho0e : o 0 ∈ C.erase (w 0) := Finset.mem_erase.2 ⟨by rw [hwo]; exact ho01, ho0⟩
          have h1 : dist (x j) (w 1) ≤ dist (x j) (o 0) := hw1.2 _ ho0e
          have h2 := dist_triangle (x j) (o 1) (o 0)
          have h3 : dist (o 1) (o 0) ≤ 2 * ci := by
            rw [← hwo]
            have := dist_triangle (w 0) (x i) (o 0)
            rw [dist_comm (w 0) (x i)] at this
            linarith
          have h4 := dist_triangle (o 1) (x j) (w 1)
          rw [dist_comm (o 1) (x j)] at h4
          linarith
        · have ho1e : o 1 ∈ C.erase (w 0) := Finset.mem_erase.2 ⟨Ne.symm hwo, ho1⟩
          have h1 : dist (x j) (w 1) ≤ cj := hw1.2 _ ho1e
          have h4 := dist_triangle (o 1) (x j) (w 1)
          rw [dist_comm (o 1) (x j)] at h4
          linarith
  6. For every agent a, two_facility_cost x p a w ≤ two_facility_cost x p a o + E.

    By hypothesis hnd, agent a cannot approve both facilities. If a approves neither, both costs are 0 and 0 ≤ E. If a approves only facility 1, the triangle inequality (dist_triangle) gives dist(x a, w 1) ≤ dist(x a, o 1) + dist(o 1, w 1) ≤ dist(x a, o 1) + E. Symmetrically, if a approves only facility 0, dist(x a, w 0) ≤ dist(x a, o 0) + E.

    lines 57–70

    uses dist_triangle

      -- per agent
      have hper : ∀ a, two_facility_cost x p a w ≤ two_facility_cost x p a o + E := by
        intro a
        rw [cost_eq, cost_eq]
        have hE0 : 0 ≤ E := by positivity
        cases h0 : p a 0 <;> cases h1 : p a 1
        · simp; exact hE0
        · simp
          have := dist_triangle (x a) (o 1) (w 1)
          linarith
        · simp
          have := dist_triangle (x a) (o 0) (w 0)
          linarith
        · exact absurd ⟨h0, h1⟩ (hnd a)
  7. Agent i incurs no more cost under w than under o: two_facility_cost x p i w ≤ two_facility_cost x p i o.

    Agent i approves only facility 0, so their cost under w is dist(x i, w 0), which is at most c_i = two_facility_cost x p i o by the choice of w(0).

    lines 71–72

      have hself : two_facility_cost x p i w ≤ two_facility_cost x p i o := by
        rw [cost_eq, hci']; simp [hi, hi1]; exact hi_w0
  8. The sum of costs under w over all agents except i is bounded by their sum under o plus (n - 1) E, where n = |ι|.

    We isolate agent i from the social cost sum using Finset.add_sum_erase and Finset.mem_univ. Summing the per-agent bound over all a ≠ i with Finset.sum_le_sum and distributing the sum with Finset.sum_add_distrib yields the sum of costs under o plus the constant E summed over ι.erase i. The cardinality of ι.erase i is n - 1 (Finset.sum_const, Finset.card_erase_of_mem, Finset.card_univ, nsmul_eq_mul, Fintype.card_pos_iff.2, Nat.cast_sub).

    lines 73–83

    uses Finset.add_sum_erase, Finset.mem_univ, Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_const, Finset.card_erase_of_mem, Finset.card_univ, nsmul_eq_mul, Fintype.card_pos_iff.2, Nat.cast_sub

      -- sum
      unfold two_facility_social_cost
      rw [← Finset.add_sum_erase _ _ (Finset.mem_univ i), ← Finset.add_sum_erase _ (fun a => two_facility_cost x p a o) (Finset.mem_univ i)]
      have hsum : ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a w ≤
          ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o + ((Fintype.card ι : ℝ) - 1) * E := by
        have := Finset.sum_le_sum (fun a (_ : a ∈ Finset.univ.erase i) => hper a)
        rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_erase_of_mem (Finset.mem_univ i),
          Finset.card_univ, nsmul_eq_mul] at this
        have hn1 : 1 ≤ Fintype.card ι := Fintype.card_pos_iff.2 ⟨i⟩
        rw [Nat.cast_sub hn1] at this
        simpa using this
  9. The sum of dictator costs satisfies c_i + c_j ≤ two_facility_cost x p i o + ∑ a ≠ i, two_facility_cost x p a o.

    Since i ≠ j, agent j belongs to ι.erase i (Finset.mem_erase.2, Ne.symm, Finset.mem_univ). Because costs are nonnegative, agent j's cost c_j is bounded by the sum of costs over ι.erase i via Finset.single_le_sum. Adding agent i's cost c_i gives c_i + c_j ≤ SC(o).

    lines 84–88

    uses Finset.single_le_sum, Finset.mem_erase.2, Ne.symm, Finset.mem_univ

      have hpair : ci + cj ≤ two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o := by
        rw [hci', ← hcj']
        have : two_facility_cost x p j o ≤ ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o :=
          Finset.single_le_sum (fun a _ => cost_nonneg a o) (Finset.mem_erase.2 ⟨Ne.symm hij, Finset.mem_univ j⟩)
        linarith
  10. The social cost bound SC(w) ≤ (2n - 1) SC(o) holds.

    Agent i witnesses that n ≥ 1 (Fintype.card_pos_iff.2), and the sum of optimal costs over the remaining agents is nonnegative (Finset.sum_nonneg). Combining the bounds for agent i and the remaining agents with c_i + c_j ≤ SC(o), nonlinear arithmetic deduces SC(w) ≤ SC(o) + 2(n - 1) SC(o) = (2n - 1) SC(o).

    lines 89–92

    uses Fintype.card_pos_iff.2, Finset.sum_nonneg

      have hn1 : (1 : ℝ) ≤ Fintype.card ι := by exact_mod_cast Fintype.card_pos_iff.2 ⟨i⟩
      have hrest : 0 ≤ ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o :=
        Finset.sum_nonneg (fun a _ => cost_nonneg a o)
      nlinarith [hsum, hpair, hself, hn1, hci0, hcj0]
Bool.noConfusion
equality between distinct boolean constructors (true = false) is contradictory
Fin.sum_univ_two
the sum of a function over Fin 2 is f(0) + f(1)
add_nonneg
the sum of two nonnegative elements is nonnegative
dist_nonneg
the metric distance between any two points is nonnegative
dist_triangle
the triangle inequality dist x z ≤ dist x y + dist y z
dist_comm
symmetry of metric distance, dist x y = dist y x
Finset.mem_erase.2
if a ≠ b and a ∈ s, then a ∈ s.erase b (the right-to-left direction of membership in an erased finset)
Ne.symm
inequality is symmetric: if a ≠ b then b ≠ a
Finset.add_sum_erase
for any element a ∈ s, f(a) + ∑ x ∈ s.erase a, f(x) = ∑ x ∈ s, f(x)
Finset.mem_univ
every element of a finite type belongs to its universal finset
Finset.sum_le_sum
if f(x) ≤ g(x) for all x ∈ s, then ∑ x ∈ s, f(x) ≤ ∑ x ∈ s, g(x)
Finset.sum_add_distrib
the sum of f(x) + g(x) distributes over addition of sums
Finset.sum_const
summing a constant value b over a finset s equals |s| • b
Finset.card_erase_of_mem
erasing an element from a finset decreases its cardinality by 1
Finset.card_univ
the cardinality of the universal finset equals Fintype.card of the underlying type
nsmul_eq_mul
natural number scalar multiplication n • a equals the cast product ↑n * a
Fintype.card_pos_iff.2
if a finite type is nonempty, its cardinality is at least 1
Nat.cast_sub
the cast of a subtraction of natural numbers m ≤ n equals ↑n - ↑m
Finset.single_le_sum
a single nonnegative term f(a) is bounded by the sum of nonnegative terms over the set containing a
Finset.sum_nonneg
a sum of nonnegative terms over a finset is nonnegative

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

theorem fixed_dictator_social_cost_le_of_singletons {ι X : Type*} [Fintype ι] [MetricSpace X] [DecidableEq X]    (C : Finset X) (x : ι → X) (p : ι → Fin 2 → Bool)    (hnd : ∀ a, ¬ (p a 0 = true ∧ p a 1 = true)) (w : Fin 2 → X) (i j : ι)    (hi : p i 0 = true) (hj : p j 1 = true)    (hw0 : IsClosestCandidate C (x i) (w 0)) (hw1 : IsClosestCandidate (C.erase (w 0)) (x j) (w 1))    (o : Fin 2 → X) (ho : IsTwoFacilityFeasible C o) :    two_facility_social_cost x p w ≤ (2 * (Fintype.card ι : ℝ) - 1) * two_facility_social_cost x p o := by  classical  obtain ⟨ho0, ho1, ho01⟩ := ho  have hi1 : p i 1 = false := by    cases h : p i 1    · rfl    · exact absurd ⟨hi, h⟩ (hnd i)  have hj0 : p j 0 = false := by    cases h : p j 0    · rfl    · exact absurd ⟨h, hj⟩ (hnd j)  have hij : i ≠ j := by    rintro rfl; rw [hi] at hj0; exact Bool.noConfusion hj0  have cost_eq : ∀ a (c : Fin 2 → X), two_facility_cost x p a c =      (if p a 0 then dist (x a) (c 0) else 0) + (if p a 1 then dist (x a) (c 1) else 0) := by    intro a c; simp [two_facility_cost, Fin.sum_univ_two]  have cost_nonneg : ∀ a (c : Fin 2 → X), 0 ≤ two_facility_cost x p a c := by    intro a c; rw [cost_eq]    apply add_nonneg <;> split_ifs <;> simp [dist_nonneg]  set ci := dist (x i) (o 0) with hci  set cj := dist (x j) (o 1) with hcj  have hci' : two_facility_cost x p i o = ci := by rw [cost_eq]; simp [hi, hi1, hci]  have hcj' : two_facility_cost x p j o = cj := by rw [cost_eq]; simp [hj, hj0, hcj]  have hi_w0 : dist (x i) (w 0) ≤ ci := hw0.2 _ ho0  set E := 2 * (ci + cj) with hE  have hci0 : 0 ≤ ci := dist_nonneg  have hcj0 : 0 ≤ cj := dist_nonneg  -- the two displacement bounds  have hD0 : dist (o 0) (w 0) ≤ E := by    have := dist_triangle (o 0) (x i) (w 0)    rw [dist_comm (o 0) (x i)] at this    linarith  have hD1 : dist (o 1) (w 1) ≤ E := by    by_cases hwo : w 0 = o 1    · have ho0e : o 0 ∈ C.erase (w 0) := Finset.mem_erase.2 ⟨by rw [hwo]; exact ho01, ho0⟩      have h1 : dist (x j) (w 1) ≤ dist (x j) (o 0) := hw1.2 _ ho0e      have h2 := dist_triangle (x j) (o 1) (o 0)      have h3 : dist (o 1) (o 0) ≤ 2 * ci := by        rw [← hwo]        have := dist_triangle (w 0) (x i) (o 0)        rw [dist_comm (w 0) (x i)] at this        linarith      have h4 := dist_triangle (o 1) (x j) (w 1)      rw [dist_comm (o 1) (x j)] at h4      linarith    · have ho1e : o 1 ∈ C.erase (w 0) := Finset.mem_erase.2 ⟨Ne.symm hwo, ho1⟩      have h1 : dist (x j) (w 1) ≤ cj := hw1.2 _ ho1e      have h4 := dist_triangle (o 1) (x j) (w 1)      rw [dist_comm (o 1) (x j)] at h4      linarith  -- per agent  have hper : ∀ a, two_facility_cost x p a w ≤ two_facility_cost x p a o + E := by    intro a    rw [cost_eq, cost_eq]    have hE0 : 0 ≤ E := by positivity    cases h0 : p a 0 <;> cases h1 : p a 1    · simp; exact hE0    · simp      have := dist_triangle (x a) (o 1) (w 1)      linarith    · simp      have := dist_triangle (x a) (o 0) (w 0)      linarith    · exact absurd ⟨h0, h1⟩ (hnd a)  have hself : two_facility_cost x p i w ≤ two_facility_cost x p i o := by    rw [cost_eq, hci']; simp [hi, hi1]; exact hi_w0  -- sum  unfold two_facility_social_cost  rw [← Finset.add_sum_erase _ _ (Finset.mem_univ i), ← Finset.add_sum_erase _ (fun a => two_facility_cost x p a o) (Finset.mem_univ i)]  have hsum : ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a w ≤      ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o + ((Fintype.card ι : ℝ) - 1) * E := by    have := Finset.sum_le_sum (fun a (_ : a ∈ Finset.univ.erase i) => hper a)    rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_erase_of_mem (Finset.mem_univ i),      Finset.card_univ, nsmul_eq_mul] at this    have hn1 : 1 ≤ Fintype.card ι := Fintype.card_pos_iff.2 ⟨i⟩    rw [Nat.cast_sub hn1] at this    simpa using this  have hpair : ci + cj ≤ two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o := by    rw [hci', ← hcj']    have : two_facility_cost x p j o ≤ ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o :=      Finset.single_le_sum (fun a _ => cost_nonneg a o) (Finset.mem_erase.2 ⟨Ne.symm hij, Finset.mem_univ j⟩)    linarith  have hn1 : (1 : ℝ) ≤ Fintype.card ι := by exact_mod_cast Fintype.card_pos_iff.2 ⟨i⟩  have hrest : 0 ≤ ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o :=    Finset.sum_nonneg (fun a _ => cost_nonneg a o)  nlinarith [hsum, hpair, hself, hn1, hci0, hcj0]
See it in the graphDiscuss this resultChallenge it