fixed_dictator_social_cost_le_of_doubleton
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
- two_facility_costcost_i(c) = sum over j in {F_1, F_2} of p_ij * d(x_i, c_j).
- two_facility_social_costSC(c) = sum over agents i of cost_i(c).
- IsTwoFacilityFeasiblec = (c_1, c_2) is feasible iff c_1, c_2 ∈ C and c_1 ≠ c_2.
- IsClosestCandidatec ∈ C and d(y, c) ≤ d(y, c') for every c' ∈ C.
- two_facility_cost_nonnegSanity: every individual cost is nonnegative.
- 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).
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.
uses
Fin.sum_univ_two,dist_triangle,dist_comm,dist_nonneglemma 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
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).
uses
Fin.sum_univ_two,if_postheorem 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]
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).
uses
eq_or_ne,Finset.mem_erase.mprhave 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
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.
uses
dist_triangle,dist_commhave 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
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.
uses
fixed_dictator_social_cost_le_of_doubleton_aux_triangle,two_facility_cost_nonneg,Finset.single_le_sum,Finset.mem_univhave 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)
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.
uses
Finset.add_sum_erase,Finset.mem_univ,add_le_add,Finset.sum_le_sum,Finset.sum_add_distrib,Finset.sum_const,nsmul_eq_mulhave 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]
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.
uses
Fintype.card_pos_iff.mpr,Finset.card_erase_of_mem,Finset.card_univ,Nat.cast_sub,mul_le_mul_of_nonneg_lefthave 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.
- Classical logic is used (line 31) because determining whether candidate locations coincide (eq_or_ne) requires decidability of equality.
- Converting set cardinalities from ℕ to ℝ and manipulating n - 1 requires explicit positivity and casting lemmas (Fintype.card_pos_iff.mpr, Nat.cast_sub).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]