AFTD Auto-Formalizing Theoretical Domains

fixed_dictator_social_cost_le_of_doubleton

theoremverified

Case 1 of Theorem 4.5: if the facilities are at the two closest candidate locations w_1, w_2 of an agent i approving both, then SC(w) ≤ (2n-1) SC(o) for every feasible o.

Statement

theorem fixed_dictator_social_cost_le_of_doubleton {ι X : Type*} [Fintype ι] [MetricSpace X] [DecidableEq X]
    (C : Finset X) (x : ι → X) (p : ι → Fin 2 → Bool)
    (w : Fin 2 → X) (i : ι) (hi0 : p i 0 = true) (hi1 : p i 1 = true)
    (hw0 : IsClosestCandidate C (x i) (w 0)) (hw1 : IsClosestCandidate (C.erase (w 0)) (x i) (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 1 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

To bound the social cost of the two facilities chosen by dictator i, the proof first shows that agent i's cost under w is at most their cost under any feasible outcome o. By the triangle inequality, the sum of displacements between the facilities in w and o is at most twice the dictator's cost under o. Every other agent's cost under w exceeds their cost under o by at most this total displacement. Summing over all n agents and bounding the dictator's cost by the optimal social cost yields SC(w) ≤ SC(o) + 2(n - 1) SC(o) = (2n - 1) SC(o).

  1. For any agent a and pairs of facilities c, c', two_facility_cost x p a c ≤ two_facility_cost x p a c' + dist (c 0) (c' 0) + dist (c 1) (c' 1).

    Unfolding two_facility_cost expresses the cost to agent a as the sum over j ∈ {0, 1} of dist(x a, c j) if p a j is true, and 0 otherwise. For each facility j, if p a j is true, the triangle inequality dist_triangle and symmetry dist_comm give dist(x a, c j) ≤ dist(x a, c' j) + dist(c j, c' j). If p a j is false, the contribution 0 ≤ 0 + dist(c j, c' j) holds because distances are non-negative by dist_nonneg. Summing these inequalities over j ∈ {0, 1} with Fin.sum_univ_two and linear arithmetic yields the bound.

    lines 1–24

    uses Fin.sum_univ_two, dist_triangle, dist_comm, dist_nonneg

    lemma fixed_dictator_social_cost_le_of_doubleton_aux_triangle
        {ι X : Type*} [MetricSpace X] (x : ι → X) (p : ι → Fin 2 → Bool)
        (a : ι) (c c' : Fin 2 → X) :
        two_facility_cost x p a c ≤ two_facility_cost x p a c' + dist (c 0) (c' 0) + dist (c 1) (c' 1) := by
      unfold two_facility_cost
      rw [Fin.sum_univ_two, Fin.sum_univ_two]
      have h0 : (if p a 0 = true then dist (x a) (c 0) else 0)
          ≤ (if p a 0 = true then dist (x a) (c' 0) else 0) + dist (c 0) (c' 0) := by
        split_ifs with h
        · have := dist_triangle (x a) (c' 0) (c 0)
          rw [dist_comm (c' 0) (c 0)] at this
          linarith
        · have := dist_nonneg (x := c 0) (y := c' 0)
          linarith
      have h1 : (if p a 1 = true then dist (x a) (c 1) else 0)
          ≤ (if p a 1 = true then dist (x a) (c' 1) else 0) + dist (c 1) (c' 1) := by
        split_ifs with h
        · have := dist_triangle (x a) (c' 1) (c 1)
          rw [dist_comm (c' 1) (c 1)] at this
          linarith
        · have := dist_nonneg (x := c 1) (y := c' 1)
          linarith
      linarith
    
  2. Agent i's cost under w is dist(x i, w 0) + dist(x i, w 1), and under o is dist(x i, o 0) + dist(x i, o 1).

    Unfolding two_facility_cost for agent i and expanding the two-element sum via Fin.sum_univ_two, both conditional terms simplify to their positive branches using if_pos because agent i approves both facilities (hi0 : p i 0 = true and hi1 : p i 1 = true). This evaluates the cost of dictator i to the sum of distances to both facilities for both w (hcw) and o (hco).

    lines 25–37

    uses Fin.sum_univ_two, if_pos

    theorem fixed_dictator_social_cost_le_of_doubleton {ι X : Type*} [Fintype ι] [MetricSpace X] [DecidableEq X]
        (C : Finset X) (x : ι → X) (p : ι → Fin 2 → Bool)
        (w : Fin 2 → X) (i : ι) (hi0 : p i 0 = true) (hi1 : p i 1 = true)
        (hw0 : IsClosestCandidate C (x i) (w 0)) (hw1 : IsClosestCandidate (C.erase (w 0)) (x i) (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
      have hcw : two_facility_cost x p i w = dist (x i) (w 0) + dist (x i) (w 1) := by
        unfold two_facility_cost
        rw [Fin.sum_univ_two, if_pos hi0, if_pos hi1]
      have hco : two_facility_cost x p i o = dist (x i) (o 0) + dist (x i) (o 1) := by
        unfold two_facility_cost
        rw [Fin.sum_univ_two, if_pos hi0, if_pos hi1]
  3. The dictator's cost under w is at most their cost under any feasible outcome o: two_facility_cost x p i w ≤ two_facility_cost x p i o.

    Since o is feasible, its facilities are distinct (o 0 ≠ o 1) and lie in C. We perform a case split using eq_or_ne on whether o 0 = w 0. If o 0 = w 0, then o 1 ≠ w 0, so o 1 ∈ C.erase (w 0) by Finset.mem_erase.mpr; since w 1 is closest in C.erase (w 0) by hw1, dist(x i, w 1) ≤ dist(x i, o 1), while dist(x i, w 0) ≤ dist(x i, o 0) by hw0. If o 0 ≠ w 0, then o 0 ∈ C.erase (w 0), so dist(x i, w 1) ≤ dist(x i, o 0) by hw1, and dist(x i, w 0) ≤ dist(x i, o 1) by hw0. Adding the inequalities in either case gives dist(x i, w 0) + dist(x i, w 1) ≤ dist(x i, o 0) + dist(x i, o 1).

    lines 38–52

    uses eq_or_ne, Finset.mem_erase.mpr

      have hA : two_facility_cost x p i w ≤ two_facility_cost x p i o := by
        have ho0 : o 0 ∈ C := ho.1
        have ho1 : o 1 ∈ C := ho.2.1
        have hone : o 0 ≠ o 1 := ho.2.2
        rw [hcw, hco]
        rcases eq_or_ne (o 0) (w 0) with h | h
        · have hone' : o 1 ≠ w 0 := by intro hh; exact hone (h.trans hh.symm)
          have hlt : dist (x i) (w 1) ≤ dist (x i) (o 1) :=
            hw1.2 (o 1) (Finset.mem_erase.mpr ⟨hone', ho1⟩)
          have h2 : dist (x i) (w 0) ≤ dist (x i) (o 0) := hw0.2 (o 0) ho0
          linarith
        · have hlt : dist (x i) (w 1) ≤ dist (x i) (o 0) :=
            hw1.2 (o 0) (Finset.mem_erase.mpr ⟨h, ho0⟩)
          have h2 : dist (x i) (w 0) ≤ dist (x i) (o 1) := hw0.2 (o 1) ho1
          linarith
  4. The total displacement between w and o is bounded by twice the dictator's cost: dist(w 0, o 0) + dist(w 1, o 1) ≤ 2 * two_facility_cost x p i o.

    Applying the triangle inequality dist_triangle and symmetry dist_comm via agent i's location gives dist(w 0, o 0) ≤ dist(x i, w 0) + dist(x i, o 0) and dist(w 1, o 1) ≤ dist(x i, w 1) + dist(x i, o 1). Summing these gives two_facility_cost x p i w + two_facility_cost x p i o. Since the dictator's cost under w is at most that under o by hA, linear arithmetic bounds the sum by 2 * two_facility_cost x p i o.

    lines 53–62

    uses dist_triangle, dist_comm

      have hD : dist (w 0) (o 0) + dist (w 1) (o 1) ≤ 2 * two_facility_cost x p i o := by
        have htri0 : dist (w 0) (o 0) ≤ dist (x i) (w 0) + dist (x i) (o 0) := by
          have := dist_triangle (w 0) (x i) (o 0)
          rwa [dist_comm (w 0) (x i)] at this
        have htri1 : dist (w 1) (o 1) ≤ dist (x i) (w 1) + dist (x i) (o 1) := by
          have := dist_triangle (w 1) (x i) (o 1)
          rwa [dist_comm (w 1) (x i)] at this
        rw [hcw, hco] at hA
        rw [hco]
        linarith
  5. For every agent a, two_facility_cost x p a w ≤ two_facility_cost x p a o + (dist(w 0, o 0) + dist(w 1, o 1)), and two_facility_cost x p i o ≤ two_facility_social_cost x p o.

    The per-agent cost bound hper follows directly from the auxiliary triangle lemma fixed_dictator_social_cost_le_of_doubleton_aux_triangle applied to w and o. The lower bound on optimal social cost hsc follows by unfolding two_facility_social_cost and applying Finset.single_le_sum, since all agent costs are non-negative by two_facility_cost_nonneg and i ∈ Finset.univ by Finset.mem_univ.

    lines 63–70

    uses fixed_dictator_social_cost_le_of_doubleton_aux_triangle, two_facility_cost_nonneg, Finset.single_le_sum, Finset.mem_univ

      have hper : ∀ a, two_facility_cost x p a w ≤
          two_facility_cost x p a o + (dist (w 0) (o 0) + dist (w 1) (o 1)) := by
        intro a
        have := fixed_dictator_social_cost_le_of_doubleton_aux_triangle x p a w o
        linarith
      have hsc : two_facility_cost x p i o ≤ two_facility_social_cost x p o := by
        rw [two_facility_social_cost]
        exact Finset.single_le_sum (fun a _ => two_facility_cost_nonneg x p a o) (Finset.mem_univ i)
  6. The social cost under w is bounded by two_facility_social_cost x p o + |ι \ {i}| * (dist(w 0, o 0) + dist(w 1, o 1)).

    Using Finset.add_sum_erase and Finset.mem_univ, the social costs under w and o are split into the dictator's term at i plus the sum over the remaining agents a ∈ Finset.univ.erase i (hsplit_w, hsplit_o). We bound the dictator term using hA and each remaining agent term using hper via add_le_add and Finset.sum_le_sum. Rewriting the sum of constant displacement with Finset.sum_add_distrib, Finset.sum_const, and nsmul_eq_mul yields the bound.

    lines 71–94

    uses Finset.add_sum_erase, Finset.mem_univ, add_le_add, Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul

      have hsplit_w : two_facility_social_cost x p w =
          two_facility_cost x p i w + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a w := by
        rw [two_facility_social_cost]
        exact (Finset.add_sum_erase Finset.univ (fun a => two_facility_cost x p a w) (Finset.mem_univ i)).symm
      have hsplit_o : two_facility_social_cost x p o =
          two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o := by
        rw [two_facility_social_cost]
        exact (Finset.add_sum_erase Finset.univ (fun a => two_facility_cost x p a o) (Finset.mem_univ i)).symm
      have hbound : two_facility_social_cost x p w ≤
          two_facility_social_cost x p o
            + ((Finset.univ.erase i).card : ℝ) * (dist (w 0) (o 0) + dist (w 1) (o 1)) := by
        rw [hsplit_w, hsplit_o]
        have h1 : two_facility_cost x p i w + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a w
            ≤ two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i,
                (two_facility_cost x p a o + (dist (w 0) (o 0) + dist (w 1) (o 1))) := by
          apply add_le_add hA
          exact Finset.sum_le_sum (fun a _ => hper a)
        have h2 : two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i,
                (two_facility_cost x p a o + (dist (w 0) (o 0) + dist (w 1) (o 1)))
            = (two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o)
                + ((Finset.univ.erase i).card : ℝ) * (dist (w 0) (o 0) + dist (w 1) (o 1)) := by
          rw [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul]
          ring
        linarith [h1, h2]
  7. two_facility_social_cost x p w ≤ (2 * |ι| - 1) * two_facility_social_cost x p o.

    Since agent i exists, Fintype.card_pos_iff.mpr ensures 1 ≤ |ι|. By Finset.card_erase_of_mem, Finset.card_univ, and Nat.cast_sub, the number of other agents is |Finset.univ.erase i| = |ι| - 1 ≥ 0. Multiplying the displacement bound hD by |ι| - 1 ≥ 0 via mul_le_mul_of_nonneg_left bounds the displacement term by (|ι| - 1) * (2 * two_facility_cost x p i o). Applying hsc bounds this further by (|ι| - 1) * (2 * two_facility_social_cost x p o). Finally, combining with the base optimal social cost gives (1 + 2(|ι| - 1)) * SC(o) = (2|ι| - 1) * SC(o) by ring arithmetic and linarith.

    lines 95–113

    uses Fintype.card_pos_iff.mpr, Finset.card_erase_of_mem, Finset.card_univ, Nat.cast_sub, mul_le_mul_of_nonneg_left

      have hn : 1 ≤ Fintype.card ι := Fintype.card_pos_iff.mpr ⟨i⟩
      have hcard : ((Finset.univ.erase i).card : ℝ) = (Fintype.card ι : ℝ) - 1 := by
        rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Nat.cast_sub hn]
        norm_num
      have hnonneg : (0:ℝ) ≤ (Fintype.card ι : ℝ) - 1 := by
        have : (1:ℝ) ≤ (Fintype.card ι : ℝ) := by exact_mod_cast hn
        linarith
      have hstep1 : ((Finset.univ.erase i).card : ℝ) * (dist (w 0) (o 0) + dist (w 1) (o 1))
          ≤ ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_cost x p i o) := by
        rw [hcard]
        exact mul_le_mul_of_nonneg_left hD hnonneg
      have hstep2 : ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_cost x p i o)
          ≤ ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_social_cost x p o) := by
        apply mul_le_mul_of_nonneg_left _ hnonneg
        linarith [hsc]
      have hfinal : two_facility_social_cost x p o
          + ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_social_cost x p o)
          = (2 * (Fintype.card ι : ℝ) - 1) * two_facility_social_cost x p o := by ring
      linarith [hbound, hstep1, hstep2, hfinal]
Fin.sum_univ_two
The sum of a function over Fin 2 equals the value at 0 plus the value at 1.
dist_triangle
In a metric space, the distance from x to z is at most the distance from x to y plus the distance from y to z.
dist_comm
In a metric space, distance is symmetric: dist(x, y) = dist(y, x).
dist_nonneg
The distance between any two points in a metric space is non-negative: 0 ≤ dist(x, y).
if_pos
If a proposition c is true, the conditional expression if c then t else e evaluates to t.
eq_or_ne
For any two elements x and y, either x = y or x ≠ y.
Finset.mem_erase.mpr
An element a belongs to s with b erased if and only if a ≠ b and a ∈ s.
fixed_dictator_social_cost_le_of_doubleton_aux_triangle
For any agent a and pairs of facilities c and c', cost(a, c) ≤ cost(a, c') + dist(c 0, c' 0) + dist(c 1, c' 1).
Finset.single_le_sum
A single term in a finite sum of non-negative elements is bounded above by the total sum.
two_facility_cost_nonneg
An agent's two-facility cost is always non-negative.
Finset.mem_univ
Every element of a finite type belongs to the universal set Finset.univ.
Finset.add_sum_erase
The sum over a finite set s can be decomposed into the term at a ∈ s plus the sum over s with a erased.
add_le_add
If a ≤ b and c ≤ d, then a + c ≤ b + d.
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)) over a finite set equals the sum of f(x) plus the sum of g(x).
Finset.sum_const
The sum of a constant value b over a finite set s equals |s| • b.
nsmul_eq_mul
Natural number scalar multiplication n • a equals (n : ℝ) * a.
Fintype.card_pos_iff.mpr
A finite type with at least one element has strictly positive cardinality.
Finset.card_erase_of_mem
Erasing an element a ∈ s from a finite set s decreases its cardinality by 1.
Finset.card_univ
The cardinality of the universal set of a finite type equals the cardinality of the type.
Nat.cast_sub
For natural numbers with m ≤ n, the cast of n - m to real numbers equals (n : ℝ) - (m : ℝ).
mul_le_mul_of_nonneg_left
Multiplying an inequality b ≤ c on the left by a non-negative scalar 0 ≤ a yields a * b ≤ a * c.

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

lemma fixed_dictator_social_cost_le_of_doubleton_aux_triangle    {ι X : Type*} [MetricSpace X] (x : ι → X) (p : ι → Fin 2 → Bool)    (a : ι) (c c' : Fin 2 → X) :    two_facility_cost x p a c ≤ two_facility_cost x p a c' + dist (c 0) (c' 0) + dist (c 1) (c' 1) := by  unfold two_facility_cost  rw [Fin.sum_univ_two, Fin.sum_univ_two]  have h0 : (if p a 0 = true then dist (x a) (c 0) else 0)      ≤ (if p a 0 = true then dist (x a) (c' 0) else 0) + dist (c 0) (c' 0) := by    split_ifs with h    · have := dist_triangle (x a) (c' 0) (c 0)      rw [dist_comm (c' 0) (c 0)] at this      linarith    · have := dist_nonneg (x := c 0) (y := c' 0)      linarith  have h1 : (if p a 1 = true then dist (x a) (c 1) else 0)      ≤ (if p a 1 = true then dist (x a) (c' 1) else 0) + dist (c 1) (c' 1) := by    split_ifs with h    · have := dist_triangle (x a) (c' 1) (c 1)      rw [dist_comm (c' 1) (c 1)] at this      linarith    · have := dist_nonneg (x := c 1) (y := c' 1)      linarith  linariththeorem fixed_dictator_social_cost_le_of_doubleton {ι X : Type*} [Fintype ι] [MetricSpace X] [DecidableEq X]    (C : Finset X) (x : ι → X) (p : ι → Fin 2 → Bool)    (w : Fin 2 → X) (i : ι) (hi0 : p i 0 = true) (hi1 : p i 1 = true)    (hw0 : IsClosestCandidate C (x i) (w 0)) (hw1 : IsClosestCandidate (C.erase (w 0)) (x i) (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  have hcw : two_facility_cost x p i w = dist (x i) (w 0) + dist (x i) (w 1) := by    unfold two_facility_cost    rw [Fin.sum_univ_two, if_pos hi0, if_pos hi1]  have hco : two_facility_cost x p i o = dist (x i) (o 0) + dist (x i) (o 1) := by    unfold two_facility_cost    rw [Fin.sum_univ_two, if_pos hi0, if_pos hi1]  have hA : two_facility_cost x p i w ≤ two_facility_cost x p i o := by    have ho0 : o 0 ∈ C := ho.1    have ho1 : o 1 ∈ C := ho.2.1    have hone : o 0 ≠ o 1 := ho.2.2    rw [hcw, hco]    rcases eq_or_ne (o 0) (w 0) with h | h    · have hone' : o 1 ≠ w 0 := by intro hh; exact hone (h.trans hh.symm)      have hlt : dist (x i) (w 1) ≤ dist (x i) (o 1) :=        hw1.2 (o 1) (Finset.mem_erase.mpr ⟨hone', ho1⟩)      have h2 : dist (x i) (w 0) ≤ dist (x i) (o 0) := hw0.2 (o 0) ho0      linarith    · have hlt : dist (x i) (w 1) ≤ dist (x i) (o 0) :=        hw1.2 (o 0) (Finset.mem_erase.mpr ⟨h, ho0⟩)      have h2 : dist (x i) (w 0) ≤ dist (x i) (o 1) := hw0.2 (o 1) ho1      linarith  have hD : dist (w 0) (o 0) + dist (w 1) (o 1) ≤ 2 * two_facility_cost x p i o := by    have htri0 : dist (w 0) (o 0) ≤ dist (x i) (w 0) + dist (x i) (o 0) := by      have := dist_triangle (w 0) (x i) (o 0)      rwa [dist_comm (w 0) (x i)] at this    have htri1 : dist (w 1) (o 1) ≤ dist (x i) (w 1) + dist (x i) (o 1) := by      have := dist_triangle (w 1) (x i) (o 1)      rwa [dist_comm (w 1) (x i)] at this    rw [hcw, hco] at hA    rw [hco]    linarith  have hper : ∀ a, two_facility_cost x p a w ≤      two_facility_cost x p a o + (dist (w 0) (o 0) + dist (w 1) (o 1)) := by    intro a    have := fixed_dictator_social_cost_le_of_doubleton_aux_triangle x p a w o    linarith  have hsc : two_facility_cost x p i o ≤ two_facility_social_cost x p o := by    rw [two_facility_social_cost]    exact Finset.single_le_sum (fun a _ => two_facility_cost_nonneg x p a o) (Finset.mem_univ i)  have hsplit_w : two_facility_social_cost x p w =      two_facility_cost x p i w + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a w := by    rw [two_facility_social_cost]    exact (Finset.add_sum_erase Finset.univ (fun a => two_facility_cost x p a w) (Finset.mem_univ i)).symm  have hsplit_o : two_facility_social_cost x p o =      two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o := by    rw [two_facility_social_cost]    exact (Finset.add_sum_erase Finset.univ (fun a => two_facility_cost x p a o) (Finset.mem_univ i)).symm  have hbound : two_facility_social_cost x p w ≤      two_facility_social_cost x p o        + ((Finset.univ.erase i).card : ℝ) * (dist (w 0) (o 0) + dist (w 1) (o 1)) := by    rw [hsplit_w, hsplit_o]    have h1 : two_facility_cost x p i w + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a w        ≤ two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i,            (two_facility_cost x p a o + (dist (w 0) (o 0) + dist (w 1) (o 1))) := by      apply add_le_add hA      exact Finset.sum_le_sum (fun a _ => hper a)    have h2 : two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i,            (two_facility_cost x p a o + (dist (w 0) (o 0) + dist (w 1) (o 1)))        = (two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o)            + ((Finset.univ.erase i).card : ℝ) * (dist (w 0) (o 0) + dist (w 1) (o 1)) := by      rw [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul]      ring    linarith [h1, h2]  have hn : 1 ≤ Fintype.card ι := Fintype.card_pos_iff.mpr ⟨i⟩  have hcard : ((Finset.univ.erase i).card : ℝ) = (Fintype.card ι : ℝ) - 1 := by    rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Nat.cast_sub hn]    norm_num  have hnonneg : (0:ℝ) ≤ (Fintype.card ι : ℝ) - 1 := by    have : (1:ℝ) ≤ (Fintype.card ι : ℝ) := by exact_mod_cast hn    linarith  have hstep1 : ((Finset.univ.erase i).card : ℝ) * (dist (w 0) (o 0) + dist (w 1) (o 1))      ≤ ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_cost x p i o) := by    rw [hcard]    exact mul_le_mul_of_nonneg_left hD hnonneg  have hstep2 : ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_cost x p i o)      ≤ ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_social_cost x p o) := by    apply mul_le_mul_of_nonneg_left _ hnonneg    linarith [hsc]  have hfinal : two_facility_social_cost x p o      + ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_social_cost x p o)      = (2 * (Fintype.card ι : ℝ) - 1) * two_facility_social_cost x p o := by ring  linarith [hbound, hstep1, hstep2, hfinal]
See it in the graphDiscuss this resultChallenge it