fixed_dictator_social_cost_le_of_one_approved
Case 3 of Theorem 4.5: when only F_k is approved and it is placed at a closest candidate of an approving agent i (the other facility at her second-closest), SC(w) ≤ (2n-1) SC(o) for every feasible o.
Statement
theorem fixed_dictator_social_cost_le_of_one_approved {ι X : Type*} [Fintype ι] [MetricSpace X] [DecidableEq X] (C : Finset X) (x : ι → X) (p : ι → Fin 2 → Bool) (w : Fin 2 → X) (k : Fin 2) (hk : ∀ a, p a (1 - k) = false) (i : ι) (hi : p i k = true) (hwk : IsClosestCandidate C (x i) (w k)) (hwk' : IsClosestCandidate (C.erase (w k)) (x i) (w (1 - k))) (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 3 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
When no agent approves facility 1 - k, every agent's cost depends solely on the placement of facility k. Placing facility k at a closest candidate for an approving dictator i guarantees that her cost under w is at most her cost under any feasible placement o. The triangle inequality bounds the distance d(w_k, o_k) ≤ 2 cost(i, o) and bounds the cost increase for any other agent by d(w_k, o_k). Summing these bounds over the dictator and the remaining n - 1 agents yields SC(w) ≤ SC(o) + 2(n - 1) SC(o) = (2n - 1) SC(o).
Every agent's cost under any placement depends solely on facility k
Since no agent approves facility 1 - k (hypothesis hk), the only possible non-zero term in the two-facility cost sum for any agent a and placement c is the term for facility k. By Finset.sum_eq_single, an agent a's cost simplifies to d(x a, c k) if a approves k, and 0 otherwise.
uses
Finset.sum_eq_single,Finset.mem_univclassical have hcost : ∀ (a : ι) (c : Fin 2 → X), two_facility_cost x p a c = if p a k = true then dist (x a) (c k) else 0 := by intro a c unfold two_facility_cost rw [Finset.sum_eq_single k] · intro j hj _ have hjk : j = 1 - k := by omega rw [hjk, hk a] simp · intro h exact absurd (Finset.mem_univ k) h
The dictator agent i incurs at most as much cost under w as under o
Since o is feasible, both o 0 and o 1 lie in the candidate set C, which implies o k ∈ C. Because the dictator agent i approves facility k, her costs under o and w are d(x i, o k) and d(x i, w k) respectively. Because w k is chosen as a closest candidate in C to x i, d(x i, w k) ≤ d(x i, o k), meaning cost(i, w) ≤ cost(i, o).
uses
if_poshave ho0 : o 0 ∈ C := ho.1 have ho1 : o 1 ∈ C := ho.2.1 have hok : o k ∈ C := by rcases (show k = 0 ∨ k = 1 by omega) with h | h · rw [h]; exact ho0 · rw [h]; exact ho1 have hci_o : two_facility_cost x p i o = dist (x i) (o k) := by rw [hcost i o, if_pos hi] have hci_w : two_facility_cost x p i w = dist (x i) (w k) := by rw [hcost i w, if_pos hi] have hA : two_facility_cost x p i w ≤ two_facility_cost x p i o := by rw [hci_w, hci_o] exact hwk.2 (o k) hok
The distance between w k and o k is at most twice the dictator's cost under o
By the triangle inequality, d(w k, o k) ≤ d(w k, x i) + d(x i, o k). Since w k minimizes the distance to x i among all candidates in C and o k ∈ C, d(w k, x i) ≤ d(x i, o k). Therefore d(w k, o k) ≤ 2 d(x i, o k) = 2 cost(i, o).
uses
dist_triangle,dist_commhave hD : dist (w k) (o k) ≤ 2 * two_facility_cost x p i o := by have htri : dist (w k) (o k) ≤ dist (w k) (x i) + dist (x i) (o k) := dist_triangle (w k) (x i) (o k) have h1 : dist (w k) (x i) ≤ dist (x i) (o k) := by rw [dist_comm]; exact hwk.2 (o k) hok rw [hci_o] linarith
For every agent a, the cost under w is at most the cost under o plus d(w k, o k)
If agent a approves facility k, her costs are d(x a, w k) and d(x a, o k); the triangle inequality d(x a, w k) ≤ d(x a, o k) + d(o k, w k) gives the desired bound. If agent a does not approve k, both costs are 0, and the inequality holds because metric distances are non-negative.
uses
dist_triangle,dist_comm,dist_nonneghave hper : ∀ a, two_facility_cost x p a w ≤ two_facility_cost x p a o + dist (w k) (o k) := by intro a rw [hcost a w, hcost a o] split_ifs with h · have htri := dist_triangle (x a) (o k) (w k) rw [dist_comm (o k) (w k)] at htri linarith · have hnn := dist_nonneg (x := w k) (y := o k) linarith
The dictator's cost under o is at most the total social cost under o
The social cost SC(o) is the sum of all individual costs cost(a, o). Since individual costs are non-negative (two_facility_cost_nonneg), dictator i's cost is bounded above by the total social cost (Finset.single_le_sum).
uses
Finset.single_le_sum,two_facility_cost_nonneg,Finset.mem_univhave 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 SC(w) is bounded by SC(o) + (n - 1) d(w k, o k)
Decomposing the social costs for w and o by separating agent i from the remaining n - 1 agents, we apply the dictator bound cost(i, w) ≤ cost(i, o) to agent i and the per-agent bound cost(a, w) ≤ cost(a, o) + d(w k, o k) to each remaining agent. Summing these inequalities yields SC(w) ≤ SC(o) + |univ \ {i}| * d(w k, o k).
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 k) (o k) := 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 k) (o k)) := 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 k) (o k)) = (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 k) (o k) := by rw [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul] ring linarith [h1, h2]
The social cost of w is at most (2n - 1) SC(o)
Since dictator i exists, the number of agents n = |ι| is at least 1, and the cardinality of ι \ {i} is n - 1 ≥ 0. Substituting d(w k, o k) ≤ 2 cost(i, o) and cost(i, o) ≤ SC(o) gives (n - 1) d(w k, o k) ≤ 2(n - 1) SC(o). Adding SC(o) yields SC(o) + 2(n - 1) SC(o) = (2n - 1) SC(o).
uses
Fintype.card_pos_iff.mpr,Finset.card_erase_of_mem,Finset.mem_univ,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 k) (o k) ≤ ((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]
Finset.sum_eq_single- If all terms in a finite sum other than at a single element a are zero, the sum equals the term at a.
Finset.mem_univ- Every element of a finite type belongs to its universal finset univ.
if_pos- If a condition holds, the if-then-else expression evaluates to the 'then' branch.
dist_triangle- The triangle inequality in a metric space: d(x, z) ≤ d(x, y) + d(y, z).
dist_comm- Symmetry of the distance function: d(x, y) = d(y, x).
dist_nonneg- Distances in a metric space are non-negative: 0 ≤ d(x, y).
Finset.single_le_sum- An element of a finite sum of non-negative real numbers is bounded above by the sum.
two_facility_cost_nonneg- The two-facility cost of any agent is always non-negative.
Finset.add_sum_erase- A sum over a finite set s equals the value at a plus the sum over s with a removed.
add_le_add- If a ≤ b and c ≤ d, then a + c ≤ b + d.
Finset.sum_le_sum- If f(x) ≤ g(x) pointwise on a finite set, then the sum of f is bounded by the sum of g.
Finset.sum_add_distrib- The sum of two functions over a finite set equals the sum of the individual sums.
Finset.sum_const- Summing a constant b over a finite set s equals |s| • b.
nsmul_eq_mul- Scalar multiplication by a natural number n on real numbers equals multiplication by the cast of n.
Fintype.card_pos_iff.mpr- A finite type is nonempty if and only if its cardinality is at least 1.
Finset.card_erase_of_mem- Removing an element from a finite set decreases its cardinality by 1.
Finset.card_univ- The cardinality of Finset.univ for a finite type equals the cardinality of the type.
Nat.cast_sub- The real cast of a natural number difference n - m (when m ≤ n) equals the difference of their real casts.
mul_le_mul_of_nonneg_left- Multiplying both sides of an inequality b ≤ c by a non-negative real number preserves the inequality.
- The hypothesis hwk' specifies that the second facility w(1 - k) is placed at a second-closest candidate, but this placement is completely unused in the proof because no agent approves facility 1 - k.
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_one_approved {ι X : Type*} [Fintype ι] [MetricSpace X] [DecidableEq X] (C : Finset X) (x : ι → X) (p : ι → Fin 2 → Bool) (w : Fin 2 → X) (k : Fin 2) (hk : ∀ a, p a (1 - k) = false) (i : ι) (hi : p i k = true) (hwk : IsClosestCandidate C (x i) (w k)) (hwk' : IsClosestCandidate (C.erase (w k)) (x i) (w (1 - k))) (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 hcost : ∀ (a : ι) (c : Fin 2 → X), two_facility_cost x p a c = if p a k = true then dist (x a) (c k) else 0 := by intro a c unfold two_facility_cost rw [Finset.sum_eq_single k] · intro j hj _ have hjk : j = 1 - k := by omega rw [hjk, hk a] simp · intro h exact absurd (Finset.mem_univ k) h have ho0 : o 0 ∈ C := ho.1 have ho1 : o 1 ∈ C := ho.2.1 have hok : o k ∈ C := by rcases (show k = 0 ∨ k = 1 by omega) with h | h · rw [h]; exact ho0 · rw [h]; exact ho1 have hci_o : two_facility_cost x p i o = dist (x i) (o k) := by rw [hcost i o, if_pos hi] have hci_w : two_facility_cost x p i w = dist (x i) (w k) := by rw [hcost i w, if_pos hi] have hA : two_facility_cost x p i w ≤ two_facility_cost x p i o := by rw [hci_w, hci_o] exact hwk.2 (o k) hok have hD : dist (w k) (o k) ≤ 2 * two_facility_cost x p i o := by have htri : dist (w k) (o k) ≤ dist (w k) (x i) + dist (x i) (o k) := dist_triangle (w k) (x i) (o k) have h1 : dist (w k) (x i) ≤ dist (x i) (o k) := by rw [dist_comm]; exact hwk.2 (o k) hok rw [hci_o] linarith have hper : ∀ a, two_facility_cost x p a w ≤ two_facility_cost x p a o + dist (w k) (o k) := by intro a rw [hcost a w, hcost a o] split_ifs with h · have htri := dist_triangle (x a) (o k) (w k) rw [dist_comm (o k) (w k)] at htri linarith · have hnn := dist_nonneg (x := w k) (y := o k) 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 k) (o k) := 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 k) (o k)) := 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 k) (o k)) = (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 k) (o k) := 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 k) (o k) ≤ ((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]