fixed_dictator_max_cost_le_of_doubleton
In the two-facility location problem on a general metric space with candidate set C and a finite nonempty set of agents, if an agent i approves both facilities (p i 0 = true and p i 1 = true), w 0 is a closest candidate in C to x i, and w 1 is a closest candidate in C \ {w 0} to x i, then for every feasible two-facility solution o from C, the max cost of w is at most 3 times the max cost of o.
Statement
theorem fixed_dictator_max_cost_le_of_doubleton {ι X : Type*} [Fintype ι] [Nonempty ι] [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_max_cost x p w ≤ 3 * two_facility_max_cost x p o
- Formalizes
- scout/2610-18006-truthful-two-facility-location-with-candidate-locations-in.md:1349
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- two_facility_max_costGiven a finite and nonempty set of agents ι, a metric space X, agent positions x, approval preferences p, and facility locations c, the…
- two_facility_costcost_i(c) = sum over j in {F_1, F_2} of p_ij * d(x_i, c_j).
- IsClosestCandidatec ∈ C and d(y, c) ≤ d(y, c') for every c' ∈ C.
- IsTwoFacilityFeasiblec = (c_1, c_2) is feasible iff c_1, c_2 ∈ C and c_1 ≠ c_2.
- Used by 1
- fixed_dictator_max_cost_leOn general metric spaces, in the two-facility location problem with candidate locations C and a finite nonempty set of n ≥ 2 agents with…
Read back from the Lean
Let ι be a finite, nonempty type, and let X be a metric space with decidable equality.
Given:
- a finite set of candidates C : Finset X,
- a location profile x : ι → X,
- an approval/preference matrix p : ι → Fin 2 → Bool,
- a facility placement w : Fin 2 → X,
- an agent i : ι,
- hypotheses hi0 : p i 0 = true and hi1 : p i 1 = true,
- the hypothesis hw0 that w 0 is a closest candidate in C to x i (i.e., w 0 ∈ C and for all c' ∈ C, dist (x i) (w 0) ≤ dist (x i) c'),
- the hypothesis hw1 that w 1 is a closest candidate in C.erase (w 0) to x i (i.e., w 1 ∈ C, w 1 ≠ w 0, and for all c' ∈ C \ {w 0}, dist (x i) (w 1) ≤ dist (x i) c'),
- an alternative facility placement o : Fin 2 → X,
- the hypothesis ho that o is two-facility feasible in C (i.e., o 0 ∈ C, o 1 ∈ C, and o 0 ≠ o 1),
the theorem asserts that the maximum two-facility cost of w across all agents in ι is at most 3 times the maximum two-facility cost of o across all agents in ι.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes that if an agent i approves both facilities and the facilities w are chosen as the two closest distinct candidates in C to x i, then the maximum cost of w is at most 3 times that of any feasible configuration o. It first proves an auxiliary triangle inequality bounding any agent's cost under w by their cost under o plus the sum of distances between corresponding facilities. Because agent i approves both facilities, agent i's cost under w is at most that under o, which bounds the facility distance sum by twice agent i's cost under o. Combining these bounds shows that every agent's cost under w is at most 3 times the maximum cost under o, and taking the supremum yields the result.
For any agent a and configurations c and c', agent a's cost under c is at most the cost under c' plus dist(c 0, c' 0) + dist(c 1, c' 1)
Unfolding two_facility_cost and decomposing the sum over Fin 2, the cost is the sum of terms for facility 0 and facility 1. For each facility j ∈ {0, 1}, we check whether agent a approves facility j: if so, dist(x a, c j) ≤ dist(x a, c' j) + dist(c j, c' j) by the triangle inequality dist(x a, c j) ≤ dist(x a, c' j) + dist(c' j, c j) and symmetry; if not, the term is 0 ≤ 0 + dist(c j, c' j) by nonnegativity of distance. Adding these two component inequalities yields the auxiliary triangle inequality for the total two-facility cost.
uses
Fin.sum_univ_two,dist_triangle,dist_comm,dist_nonnegunfold 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 : 0 ≤ dist (c 0) (c' 0) := dist_nonneg 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 : 0 ≤ dist (c 1) (c' 1) := dist_nonneg 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)
Since agent i approves both facilities (p i 0 = true and p i 1 = true), the indicator conditions in the definition of two_facility_cost evaluate to true for both facilities 0 and 1. Expanding the sum over Fin 2 thus simplifies the cost directly to the sum of distances to the two facilities.
uses
Fin.sum_univ_two,if_posclassical 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]
Agent i's cost under w is at most agent i's cost under o
Since o is feasible, o 0 and o 1 are distinct candidates in C. We split into cases on whether o 0 = w 0. If o 0 = w 0, then o 1 ≠ w 0, so o 1 is in C with w 0 erased; by choice of w 1 as closest candidate in C \ {w 0}, dist(x i, w 1) ≤ dist(x i, o 1), and dist(x i, w 0) ≤ dist(x i, o 0) because w 0 is closest in C. If o 0 ≠ w 0, then o 0 is in C \ {w 0}, giving dist(x i, w 1) ≤ dist(x i, o 0), while dist(x i, w 0) ≤ dist(x i, o 1) since o 1 ∈ C. In both cases, summing the two inequalities shows agent i's cost under w is at most that under o.
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
dist(w 0, o 0) + dist(w 1, o 1) is at most twice agent i's cost under o
By the triangle inequality and symmetry of distance, 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). Adding these gives dist(w 0, o 0) + dist(w 1, o 1) ≤ cost_i(w) + cost_i(o). Since cost_i(w) ≤ cost_i(o), this sum is bounded by 2 * cost_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, the cost under o is at most the maximum cost under o
By definition, two_facility_max_cost is the supremum of two_facility_cost over the universe of all agents, so each agent's cost is bounded above by this supremum.
uses
Finset.le_sup',Finset.mem_univhave h_le_max : ∀ a, two_facility_cost x p a o ≤ two_facility_max_cost x p o := by intro a unfold two_facility_max_cost exact Finset.le_sup' (fun j => two_facility_cost x p j o) (Finset.mem_univ a)
For every agent a, the cost under w is at most 3 times the maximum cost under o
By the auxiliary triangle inequality lemma, agent a's cost under w is at most agent a's cost under o plus dist(w 0, o 0) + dist(w 1, o 1). Bounding the distance sum by 2 * cost_i(o), we get cost_a(w) ≤ cost_a(o) + 2 * cost_i(o). Since both cost_a(o) and cost_i(o) are bounded by two_facility_max_cost of o, the sum is at most 3 * two_facility_max_cost of o.
uses
fixed_dictator_max_cost_le_of_doubleton_aux_trianglehave hper : ∀ a, two_facility_cost x p a w ≤ 3 * two_facility_max_cost x p o := by intro a have htri := fixed_dictator_max_cost_le_of_doubleton_aux_triangle x p a w o have h_ao := h_le_max a have h_io := h_le_max i linarith
The maximum cost under w is at most 3 times the maximum cost under o
Unfolding two_facility_max_cost as the supremum over all agents, since every agent's cost under w is at most 3 * two_facility_max_cost of o, the supremum over all agents is likewise bounded by 3 * two_facility_max_cost of o.
uses
Finset.sup'_le,Finset.univ_nonemptyunfold two_facility_max_cost exact Finset.sup'_le Finset.univ_nonempty (fun a => two_facility_cost x p a w) (fun a _ => hper a)
Fin.sum_univ_two- The sum of a function over Fin 2 is the sum of its values at 0 and 1
dist_triangle- The triangle inequality: dist x z ≤ dist x y + dist y z
dist_comm- Symmetry of distance: dist x y = dist y x
dist_nonneg- Distance is always nonnegative: 0 ≤ dist x y
if_pos- If a condition c holds, then (if c then t else e) = t
eq_or_ne- Any two elements are either equal or not equal: x = y ∨ x ≠ y
Finset.mem_erase.mpr- An element belongs to a finset with an element erased iff it is distinct from that element and belongs to the original finset
Finset.le_sup'- Any element's image under f is bounded above by the supremum of f over the finset
Finset.mem_univ- Every element of a finite type belongs to Finset.univ
fixed_dictator_max_cost_le_of_doubleton_aux_triangle- For any agent a and configurations c, c', cost(a, c) ≤ cost(a, c') + dist(c 0, c' 0) + dist(c 1, c' 1)
Finset.sup'_le- If every element in a nonempty finset has image ≤ a, then the supremum over the finset is ≤ a
Finset.univ_nonempty- In a nonempty finite type, Finset.univ is nonempty
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_max_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 : 0 ≤ dist (c 0) (c' 0) := dist_nonneg 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 : 0 ≤ dist (c 1) (c' 1) := dist_nonneg linarith linarith/-- Case 1 of Theorem 4.14: if some agent approves both facilities, Fixed-Dictator achieves max cost at most 3 times optimal. -/theorem fixed_dictator_max_cost_le_of_doubleton {ι X : Type*} [Fintype ι] [Nonempty ι] [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_max_cost x p w ≤ 3 * two_facility_max_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 h_le_max : ∀ a, two_facility_cost x p a o ≤ two_facility_max_cost x p o := by intro a unfold two_facility_max_cost exact Finset.le_sup' (fun j => two_facility_cost x p j o) (Finset.mem_univ a) have hper : ∀ a, two_facility_cost x p a w ≤ 3 * two_facility_max_cost x p o := by intro a have htri := fixed_dictator_max_cost_le_of_doubleton_aux_triangle x p a w o have h_ao := h_le_max a have h_io := h_le_max i linarith unfold two_facility_max_cost exact Finset.sup'_le Finset.univ_nonempty (fun a => two_facility_cost x p a w) (fun a _ => hper a)