fixed_dictator_max_cost_le_of_singletons
In the two-facility location problem on a metric space with a finite nonempty set of agents, if no agent approves both facilities, agent i approves facility 0, agent j approves facility 1, facility 0 is placed at a closest candidate of i, and facility 1 at a closest available candidate of j, then the max cost of w is at most 5 times the max cost of any feasible solution o.
Statement
theorem fixed_dictator_max_cost_le_of_singletons {ι X : Type*} [Fintype ι] [Nonempty ι] [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_max_cost x p w ≤ 5 * two_facility_max_cost x p o
- Formalizes
- scout/2610-18006-truthful-two-facility-location-with-candidate-locations-in.md:1390
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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.
- two_facility_max_cost_nonnegFor a finite nonempty set of agents, the max cost of any two-facility solution is nonnegative.
- two_facility_cost_le_max_costFor a finite nonempty set of agents, every agent i incurs individual cost under solution c that is at most the max cost of c.
- 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 nonempty finite type and $X$ a metric space with decidable equality. Let $C$ be a finite subset of $X$, $x : ι \to X$ map each agent to a location in $X$, and $p : ι \to \text{Fin } 2 \to \text{Bool}$ indicate which facility (0 or 1) each agent is served by.
Assume:
1. No agent is served by both facilities: for all $a \in ι$, $\neg (p(a, 0) = \text{true} \wedge p(a, 1) = \text{true})$.
2. There are facilities $w : \text{Fin } 2 \to X$ and agents $i, j \in ι$ such that agent $i$ is served by facility 0 ($p(i, 0) = \text{true}$) and agent $j$ is served by facility 1 ($p(j, 1) = \text{true}$).
3. $w(0)$ is a candidate in $C$ that minimizes the distance to $x(i)$ among all elements of $C$ (IsClosestCandidate C (x i) (w 0)).
4. $w(1)$ is a candidate in $C \setminus \{w(0)\}$ that minimizes the distance to $x(j)$ among all elements of $C \setminus \{w(0)\}$ (IsClosestCandidate (C.erase (w 0)) (x j) (w 1)).
5. $o : \text{Fin } 2 \to X$ is a feasible two-facility placement from $C$ (IsTwoFacilityFeasible C o).
Then the maximum two-facility cost of $w$ across all agents is at most $5$ times the maximum two-facility cost of $o$ across all agents:
$$\text{two\_facility\_max\_cost } x\ p\ w \le 5 \cdot \text{two\_facility\_max\_cost } x\ p\ o.$$
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 shows that Fixed-Dictator achieves a 5-approximation to the optimal max cost M when no agent approves both facilities. Because agent i approves only facility 0 and agent j approves only facility 1, their optimal distances c_i = dist(x i, o 0) and c_j = dist(x j, o 1) are bounded by M. Using the greedy choice of w 0 for i and w 1 for j, the displacement between each placed facility and its optimal counterpart is bounded by E = 2 * (c_i + c_j) ≤ 4 * M, even if w 0 occupies candidate o 1. Since each agent approves at most one facility, the triangle inequality bounds each agent's cost under w by their cost under o plus E, yielding at most M + 4 * M = 5 * M.
The feasible solution o provides two distinct candidates o 0, o 1 ∈ C, and agents i and j each approve exactly one facility (p i 1 = false and p j 0 = false).
Feasibility of o means that o 0 ∈ C, o 1 ∈ C, and o 0 ≠ o 1. Since no agent approves both facilities (hypothesis hnd), agent i (who approves facility 0) cannot approve facility 1, and agent j (who approves facility 1) cannot approve facility 0.
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)
For any agent a and placement c, the cost to a is the sum of the distance to c 0 (if approved) and the distance to c 1 (if approved).
Unfolding two_facility_cost, the cost is a sum over the two facilities in Fin 2. Applying Fin.sum_univ_two expands this into the sum of the conditional distance to c 0 and the conditional distance to c 1.
uses
Fin.sum_univ_twohave 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]
The individual costs c_i = dist(x i, o 0) and c_j = dist(x j, o 1) are both at most the optimal maximum cost M, and dist(x i, w 0) ≤ c_i.
Let M be the maximum cost under o. Because agent i approves only facility 0, its cost under o is simply c_i = dist(x i, o 0), which must be at most M. Similarly, agent j approves only facility 1, so c_j = dist(x j, o 1) ≤ M. Because w 0 is chosen as a closest candidate in C to x i and o 0 ∈ C, we have dist(x i, w 0) ≤ dist(x i, o 0) = c_i.
uses
two_facility_max_cost_nonneg,two_facility_cost_le_max_costset M := two_facility_max_cost x p o with hM have hM_nonneg : 0 ≤ M := two_facility_max_cost_nonneg x p o have h_le_max : ∀ a, two_facility_cost x p a o ≤ M := by intro a exact two_facility_cost_le_max_cost x p a o 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 hci_le_M : ci ≤ M := by rw [← hci']; exact h_le_max i have hcj_le_M : cj ≤ M := by rw [← hcj']; exact h_le_max j have hi_w0 : dist (x i) (w 0) ≤ ci := hw0.2 _ ho0
With E = 2 * (c_i + c_j), the displacement dist(o 0, w 0) between the optimal and chosen positions of facility 0 is at most E.
By the triangle inequality and symmetry of distance, dist(o 0, w 0) ≤ dist(x i, o 0) + dist(x i, w 0) ≤ c_i + c_i = 2 * c_i. Since c_j ≥ 0 by dist_nonneg, this is bounded by E = 2 * (c_i + c_j).
uses
dist_nonneg,dist_triangle,dist_commset 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
The displacement dist(o 1, w 1) between the optimal and chosen positions of facility 1 is at most E.
We split into cases based on whether w 0 = o 1: 1. If w 0 = o 1, facility 0 took candidate o 1, but o 0 remains in C.erase (w 0) because o 0 ≠ o 1. Since w 1 minimizes distance to x j in C.erase (w 0), dist(x j, w 1) ≤ dist(x j, o 0) ≤ dist(x j, o 1) + dist(o 1, o 0). Since o 1 = w 0, the triangle inequality gives dist(o 1, o 0) = dist(w 0, o 0) ≤ dist(x i, w 0) + dist(x i, o 0) ≤ 2 * c_i. Then dist(o 1, w 1) ≤ dist(x j, o 1) + dist(x j, w 1) ≤ c_j + (c_j + 2 * c_i) = E. 2. If w 0 ≠ o 1, then o 1 is still in C.erase (w 0), so dist(x j, w 1) ≤ dist(x j, o 1) = c_j. By the triangle inequality, dist(o 1, w 1) ≤ dist(x j, o 1) + dist(x j, w 1) ≤ 2 * c_j ≤ E.
uses
Finset.mem_erase.2,dist_triangle,dist_comm,Ne.symmhave 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
The displacement bound satisfies E ≤ 4 * M, and every agent a incurs cost at most 5 * M under w.
Since c_i ≤ M and c_j ≤ M, we have E = 2 * (c_i + c_j) ≤ 4 * M. For any agent a, we examine their approvals: - If a approves neither facility, their cost is 0 ≤ 5 * M. - If a approves only facility 1, their cost under w is dist(x a, w 1) ≤ dist(x a, o 1) + dist(o 1, w 1) ≤ cost(a, o) + E ≤ M + 4 * M = 5 * M. - If a approves only facility 0, their cost under w is dist(x a, w 0) ≤ dist(x a, o 0) + dist(o 0, w 0) ≤ cost(a, o) + E ≤ M + 4 * M = 5 * M. - The case where a approves both facilities is ruled out by hypothesis hnd.
uses
dist_triangle,Bool.false_eq_true,zero_add,add_zerohave hE_le : E ≤ 4 * M := by dsimp [E] linarith have hper : ∀ a, two_facility_cost x p a w ≤ 5 * M := by intro a have hao := h_le_max a rw [cost_eq] at hao ⊢ cases h0 : p a 0 <;> cases h1 : p a 1 · simp; linarith · simp only [h0, h1, Bool.false_eq_true, ↓reduceIte, zero_add] at hao ⊢ have := dist_triangle (x a) (o 1) (w 1) linarith · simp only [h0, h1, Bool.false_eq_true, ↓reduceIte, add_zero] at hao ⊢ have := dist_triangle (x a) (o 0) (w 0) linarith · exact absurd ⟨h0, h1⟩ (hnd a)
The maximum cost under w is at most 5 times the maximum cost under o.
By definition, two_facility_max_cost is the supremum of the per-agent costs over all agents in Finset.univ. Applying Finset.sup'_le on this nonempty finite set with the universal bound 5 * M established in the previous step gives the desired inequality.
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 a two-element index set equals the value at 0 plus the value at 1.
two_facility_max_cost_nonneg- The maximum cost across all agents in the two-facility location problem is nonnegative.
two_facility_cost_le_max_cost- The cost of any individual agent under a facility placement is at most the maximum cost across all agents.
dist_nonneg- The distance between any two points in a metric space is nonnegative.
dist_triangle- The distance between x and z is at most the distance from x to y plus the distance from y to z.
dist_comm- Distance in a metric space is symmetric: dist x y = dist y x.
Finset.mem_erase.2- An element a belongs to a finite set with b removed if and only if a ≠ b and a was in the original set.
Ne.symm- The inequality relation is symmetric: if a ≠ b then b ≠ a.
Bool.false_eq_true- The proposition false = true is false.
zero_add- Adding zero on the left leaves an element unchanged: 0 + a = a.
add_zero- Adding zero on the right leaves an element unchanged: a + 0 = a.
Finset.sup'_le- If every value of a function on a nonempty finite set is at most a given upper bound, then the maximum over the set is at most that bound.
Finset.univ_nonempty- The set of all elements of a nonempty finite type is nonempty.
- In the formalization, preferences are booleans rather than sets of approved facilities, so bounding each agent's cost proceeds by boolean case analysis on whether the agent approves facility 0 and facility 1.
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.
/-- Case 2 of Theorem 4.14: when no agent approves both facilities and both facilities are approved, Fixed-Dictator achieves max cost at most 5 times optimal. -/theorem fixed_dictator_max_cost_le_of_singletons {ι X : Type*} [Fintype ι] [Nonempty ι] [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_max_cost x p w ≤ 5 * two_facility_max_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 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] set M := two_facility_max_cost x p o with hM have hM_nonneg : 0 ≤ M := two_facility_max_cost_nonneg x p o have h_le_max : ∀ a, two_facility_cost x p a o ≤ M := by intro a exact two_facility_cost_le_max_cost x p a o 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 hci_le_M : ci ≤ M := by rw [← hci']; exact h_le_max i have hcj_le_M : cj ≤ M := by rw [← hcj']; exact h_le_max j 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 have hE_le : E ≤ 4 * M := by dsimp [E] linarith have hper : ∀ a, two_facility_cost x p a w ≤ 5 * M := by intro a have hao := h_le_max a rw [cost_eq] at hao ⊢ cases h0 : p a 0 <;> cases h1 : p a 1 · simp; linarith · simp only [h0, h1, Bool.false_eq_true, ↓reduceIte, zero_add] at hao ⊢ have := dist_triangle (x a) (o 1) (w 1) linarith · simp only [h0, h1, Bool.false_eq_true, ↓reduceIte, add_zero] at hao ⊢ have := dist_triangle (x a) (o 0) (w 0) linarith · exact absurd ⟨h0, h1⟩ (hnd a) 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)