fixed_dictator_social_cost_le_of_singletons
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
- 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
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).
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.
uses
Bool.noConfusionclassical 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
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).
uses
Fin.sum_univ_two,add_nonneg,dist_nonneghave 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]
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).
uses
dist_nonnegset 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 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.
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
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.
uses
Finset.mem_erase.2,Ne.symm,dist_triangle,dist_commhave 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
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.
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)
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).
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
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).
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
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).
uses
Finset.single_le_sum,Finset.mem_erase.2,Ne.symm,Finset.mem_univhave 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
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).
uses
Fintype.card_pos_iff.2,Finset.sum_nonneghave 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
- The algebraic combination of the agent bounds, the pair bound c_i + c_j ≤ SC(o), and the nonnegativity conditions to reach the final factor (2n - 1) is closed in one step by the nonlinear arithmetic tactic `nlinarith`.
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.
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]