AFTD Auto-Formalizing Theoretical Domains

fixed_dictator_max_cost_le_of_singletons

theoremverifiedformalization

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
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.

  1. 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.

    lines 9–18

      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)
  2. 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.

    lines 19–21

    uses Fin.sum_univ_two

      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]
  3. 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.

    lines 22–33

    uses two_facility_max_cost_nonneg, two_facility_cost_le_max_cost

      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
  4. 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).

    lines 34–41

    uses dist_nonneg, dist_triangle, dist_comm

      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
  5. 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.

    lines 42–59

    uses Finset.mem_erase.2, dist_triangle, dist_comm, Ne.symm

      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
  6. 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.

    lines 60–75

    uses dist_triangle, Bool.false_eq_true, zero_add, add_zero

      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)
  7. 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.

    lines 76–77

    uses Finset.sup'_le, Finset.univ_nonempty

      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)
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.

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

/-- 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)
See it in the graphDiscuss this resultChallenge it