AFTD Auto-Formalizing Theoretical Domains

fixed_dictator_max_cost_le_of_one_approved

theoremverifiedformalization

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.

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

    lines 9–10

      have _ := hwk'
      classical
  2. For 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.

    lines 11–21

    uses Finset.sum_eq_single, Finset.mem_univ

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

    lines 22–27

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

    lines 28–29

    uses if_pos

      have hci_o : two_facility_cost x p i o = dist (x i) (o k) := by
        rw [hcost i o, if_pos hi]
  5. 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).

    lines 30–35

    uses dist_triangle, dist_comm

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

    lines 36–39

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

    lines 40–42

      have hio : dist (x i) (o k) ≤ two_facility_max_cost x p o := by
        rw [← hci_o]
        exact h_le_max i
  8. 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.

    lines 43–53

    uses if_pos, dist_triangle, dist_comm, dist_nonneg

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

    lines 54–55

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

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