AFTD Auto-Formalizing Theoretical Domains

fixed_dictator_max_cost_le_of_doubleton

theoremverifiedformalization

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.

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

    lines 4–22

    uses Fin.sum_univ_two, dist_triangle, dist_comm, dist_nonneg

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

    lines 31–37

    uses Fin.sum_univ_two, if_pos

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

    lines 38–52

    uses eq_or_ne, Finset.mem_erase.mpr

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

    lines 53–62

    uses dist_triangle, dist_comm

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

    lines 63–66

    uses Finset.le_sup', Finset.mem_univ

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

    lines 67–72

    uses fixed_dictator_max_cost_le_of_doubleton_aux_triangle

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

    lines 73–74

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

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