fixed_dictator_max_cost_le_of_one_approved
In the two-facility location problem on a general metric space with candidate set C and a finite nonempty set of agents, if no agent approves facility 1 - k (∀ a, p a (1 - k) = false), agent i approves facility k (p i k = true), w k is a closest candidate in C to x i, and w (1 - k) is a closest candidate in C \ {w k} 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_one_approved {ι X : Type*} [Fintype ι] [Nonempty ι] [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_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:1441
- 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.
Let $C$ be a finite subset of $X$, $x : ι \to X$ assign each agent in $ι$ a location in $X$, and $p : ι \to \text{Fin } 2 \to \text{Bool}$ indicate whether each agent approves each of two facilities.
Let $w : \text{Fin } 2 \to X$ be a pair of facility locations, $k \in \text{Fin } 2$, and assume:
1. For every agent $a \in ι$, $p(a, 1 - k) = \text{false}$ (no agent approves facility $1 - k$).
2. There exists an agent $i \in ι$ such that $p(i, k) = \text{true}$ (agent $i$ approves facility $k$).
3. $w(k)$ is a closest candidate in $C$ to $x(i)$ (IsClosestCandidate C (x i) (w k)).
4. $w(1 - k)$ is a closest candidate in $C \setminus \{w(k)\}$ to $x(i)$ (IsClosestCandidate (C.erase (w k)) (x i) (w (1 - k))).
5. $o : \text{Fin } 2 \to X$ is a feasible two-facility placement from $C$ (IsTwoFacilityFeasible C o, meaning $o(0), o(1) \in C$ with $o(0) \ne o(1)$).
Then the maximum two-facility cost of $w$ across all agents is at most $3$ times the maximum two-facility cost of $o$ across all agents (two_facility_max_cost x p w ≤ 3 * 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
When only one facility k is approved by any agent in the system, each agent's cost simplifies to their distance to facility k if approved, and 0 otherwise. The Fixed-Dictator mechanism selects w k as a closest candidate in C to dictator agent i, which guarantees by the triangle inequality that dist (w k) (o k) ≤ 2 * dist (x i) (o k) ≤ 2 * OPT for any feasible solution o. For any agent a who approves facility k, the triangle inequality then bounds dist (x a) (w k) ≤ dist (x a) (o k) + dist (w k) (o k) ≤ OPT + 2 * OPT = 3 * OPT, establishing the 3-approximation ratio.
Retain the second-facility hypothesis and enable classical logic.
Line 9 touches the hypothesis hwk' to acknowledge it, and line 10 opens classical reasoning for case analysis and decidability.
have _ := hwk' classicalFor any agent a and configuration c, the agent's cost is dist (x a) (c k) if a approves facility k, and 0 otherwise.
By definition, an agent's cost is the sum over both facilities j ∈ {0, 1} of the distance when approved and 0 otherwise. Since no agent approves facility 1 - k (hk), the term for j = 1 - k is zero. Using Finset.sum_eq_single, the sum collapses to just the term for facility k.
uses
Finset.sum_eq_single,Finset.mem_univhave 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 hjk have : j = 1 - k := by omega rw [this, hk a] simp · intro h exact absurd (Finset.mem_univ k) h
The optimal placement o k belongs to the candidate set C.
Feasibility of o means both o 0 ∈ C and o 1 ∈ C. Since k is in Fin 2, splitting on k = 0 or k = 1 shows o k ∈ C in both cases.
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
The dictator agent i incurs cost dist (x i) (o k) under the optimal solution o.
Since agent i approves facility k (hi), evaluating the cost formula established earlier gives exactly dist (x i) (o k).
uses
if_poshave hci_o : two_facility_cost x p i o = dist (x i) (o k) := by rw [hcost i o, if_pos hi]
The distance between the dictator's choice w k and the optimal location o k is at most 2 * dist (x i) (o k).
By the triangle inequality, dist (w k) (o k) ≤ dist (w k) (x i) + dist (x i) (o k). Since w k is a closest candidate in C to x i (hwk) and o k ∈ C, dist (x i) (w k) ≤ dist (x i) (o k). Symmetry of distance (dist_comm) and linear arithmetic yield dist (w k) (o k) ≤ 2 * dist (x i) (o k).
uses
dist_triangle,dist_commhave hD : dist (w k) (o k) ≤ 2 * dist (x i) (o k) := 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 linarith
Every agent's cost under o is bounded by the maximum cost of o.
By definition, the maximum cost is the supremum over all agents of their individual costs. The lemma Finset.le_sup' confirms that any single agent's cost is at most 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)
The dictator's distance to the optimal facility, dist (x i) (o k), is at most the maximum cost of o.
Agent i's cost under o is dist (x i) (o k), which is bounded by the maximum cost over all agents under o.
have hio : dist (x i) (o k) ≤ two_facility_max_cost x p o := by rw [← hci_o] exact h_le_max i
For every agent a, the individual cost under w is at most 3 times the maximum cost of o.
If agent a does not approve facility k, their cost under w is 0, which is at most 3 times the non-negative optimal cost. If agent a approves facility k, their cost is dist (x a) (w k). By the triangle inequality, dist (x a) (w k) ≤ dist (x a) (o k) + dist (w k) (o k). Here dist (x a) (o k) is bounded by the optimal max cost, while dist (w k) (o k) ≤ 2 * dist (x i) (o k) ≤ 2 * (optimal max cost). Adding these gives at most 3 times the optimal max cost.
uses
if_pos,dist_triangle,dist_comm,dist_nonneghave hper : ∀ a, two_facility_cost x p a w ≤ 3 * two_facility_max_cost x p o := by intro a rw [hcost a w] split_ifs with h · have hao := h_le_max a rw [hcost a o, if_pos h] at hao have htri := dist_triangle (x a) (o k) (w k) rw [dist_comm (o k) (w k)] at htri linarith · have hnonneg : 0 ≤ dist (x i) (o k) := dist_nonneg linarith
The maximum cost under w is at most 3 times the maximum cost under o.
The maximum cost under w is the supremum of all agents' individual costs. Since every individual cost is bounded by 3 * (maximum cost under o), Finset.sup'_le concludes that the supremum also satisfies this bound.
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)
Finset.sum_eq_single- A finite sum ∑ x ∈ s, f x equals f a if every term other than a is zero and a ∈ s.
Finset.mem_univ- Every element of a finite type belongs to its universal Finset univ.
if_pos- An if-then-else expression (if c then t else e) reduces to t when the condition c holds.
dist_triangle- In a metric space, dist x z ≤ dist x y + dist y z.
dist_comm- In a metric space, dist x y = dist y x.
Finset.le_sup'- For any element b in a finset s, f b is at most the supremum s.sup' ⋯ f.
dist_nonneg- In a metric space, distance is non-negative: 0 ≤ dist x y.
Finset.sup'_le- If every value f b for b ∈ s is at most a bound a, then s.sup' H f ≤ a.
Finset.univ_nonempty- The universal finset Finset.univ of a nonempty finite type is nonempty.
- The hypothesis `hwk'`, which specifies the candidate chosen for the second facility w (1 - k), is not needed in the computation because no agent approves facility 1 - k. Line 9 introduces `have _ := hwk'` simply to reference the hypothesis.
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 3 of Theorem 4.14: when only one facility is approved, Fixed-Dictator achieves max cost at most 3 times optimal. -/theorem fixed_dictator_max_cost_le_of_one_approved {ι X : Type*} [Fintype ι] [Nonempty ι] [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_max_cost x p w ≤ 3 * two_facility_max_cost x p o := by have _ := hwk' 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 hjk have : j = 1 - k := by omega rw [this, 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 hD : dist (w k) (o k) ≤ 2 * dist (x i) (o k) := 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 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 hio : dist (x i) (o k) ≤ two_facility_max_cost x p o := by rw [← hci_o] exact h_le_max i have hper : ∀ a, two_facility_cost x p a w ≤ 3 * two_facility_max_cost x p o := by intro a rw [hcost a w] split_ifs with h · have hao := h_le_max a rw [hcost a o, if_pos h] at hao have htri := dist_triangle (x a) (o k) (w k) rw [dist_comm (o k) (w k)] at htri linarith · have hnonneg : 0 ≤ dist (x i) (o k) := dist_nonneg 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)