AFTD Auto-Formalizing Theoretical Domains

fixed_dictator_social_cost_le_of_one_approved

theoremverified

Case 3 of Theorem 4.5: when only F_k is approved and it is placed at a closest candidate of an approving agent i (the other facility at her second-closest), SC(w) ≤ (2n-1) SC(o) for every feasible o.

Statement

theorem fixed_dictator_social_cost_le_of_one_approved {ι X : Type*} [Fintype ι] [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_social_cost x p w ≤ (2 * (Fintype.card ι : ℝ) - 1) * two_facility_social_cost x p o
Source
Case 3 of the proof of Theorem 4.5 of arXiv:2610.18006 (Truthful two-facility location with candidate locations in metric spaces); serves fixed_dictator_social_cost_le
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1
  • fixed_dictator_social_cost_leOn a general metric space, for n ≥ 2 agents with known non-empty approval preferences over two facilities and any candidate set C, every…

The proof, explained

When no agent approves facility 1 - k, every agent's cost depends solely on the placement of facility k. Placing facility k at a closest candidate for an approving dictator i guarantees that her cost under w is at most her cost under any feasible placement o. The triangle inequality bounds the distance d(w_k, o_k) ≤ 2 cost(i, o) and bounds the cost increase for any other agent by d(w_k, o_k). Summing these bounds over the dictator and the remaining n - 1 agents yields SC(w) ≤ SC(o) + 2(n - 1) SC(o) = (2n - 1) SC(o).

  1. Every agent's cost under any placement depends solely on facility k

    Since no agent approves facility 1 - k (hypothesis hk), the only possible non-zero term in the two-facility cost sum for any agent a and placement c is the term for facility k. By Finset.sum_eq_single, an agent a's cost simplifies to d(x a, c k) if a approves k, and 0 otherwise.

    lines 8–19

    uses Finset.sum_eq_single, Finset.mem_univ

      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 _
          have hjk : j = 1 - k := by omega
          rw [hjk, hk a]
          simp
        · intro h
          exact absurd (Finset.mem_univ k) h
  2. The dictator agent i incurs at most as much cost under w as under o

    Since o is feasible, both o 0 and o 1 lie in the candidate set C, which implies o k ∈ C. Because the dictator agent i approves facility k, her costs under o and w are d(x i, o k) and d(x i, w k) respectively. Because w k is chosen as a closest candidate in C to x i, d(x i, w k) ≤ d(x i, o k), meaning cost(i, w) ≤ cost(i, o).

    lines 20–32

    uses if_pos

      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 hci_w : two_facility_cost x p i w = dist (x i) (w k) := by
        rw [hcost i w, if_pos hi]
      have hA : two_facility_cost x p i w ≤ two_facility_cost x p i o := by
        rw [hci_w, hci_o]
        exact hwk.2 (o k) hok
  3. The distance between w k and o k is at most twice the dictator's cost under o

    By the triangle inequality, d(w k, o k) ≤ d(w k, x i) + d(x i, o k). Since w k minimizes the distance to x i among all candidates in C and o k ∈ C, d(w k, x i) ≤ d(x i, o k). Therefore d(w k, o k) ≤ 2 d(x i, o k) = 2 cost(i, o).

    lines 33–39

    uses dist_triangle, dist_comm

      have hD : dist (w k) (o k) ≤ 2 * two_facility_cost x p i o := 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
        rw [hci_o]
        linarith
  4. For every agent a, the cost under w is at most the cost under o plus d(w k, o k)

    If agent a approves facility k, her costs are d(x a, w k) and d(x a, o k); the triangle inequality d(x a, w k) ≤ d(x a, o k) + d(o k, w k) gives the desired bound. If agent a does not approve k, both costs are 0, and the inequality holds because metric distances are non-negative.

    lines 40–48

    uses dist_triangle, dist_comm, dist_nonneg

      have hper : ∀ a, two_facility_cost x p a w ≤ two_facility_cost x p a o + dist (w k) (o k) := by
        intro a
        rw [hcost a w, hcost a o]
        split_ifs with h
        · have htri := dist_triangle (x a) (o k) (w k)
          rw [dist_comm (o k) (w k)] at htri
          linarith
        · have hnn := dist_nonneg (x := w k) (y := o k)
          linarith
  5. The dictator's cost under o is at most the total social cost under o

    The social cost SC(o) is the sum of all individual costs cost(a, o). Since individual costs are non-negative (two_facility_cost_nonneg), dictator i's cost is bounded above by the total social cost (Finset.single_le_sum).

    lines 49–51

    uses Finset.single_le_sum, two_facility_cost_nonneg, Finset.mem_univ

      have hsc : two_facility_cost x p i o ≤ two_facility_social_cost x p o := by
        rw [two_facility_social_cost]
        exact Finset.single_le_sum (fun a _ => two_facility_cost_nonneg x p a o) (Finset.mem_univ i)
  6. The social cost SC(w) is bounded by SC(o) + (n - 1) d(w k, o k)

    Decomposing the social costs for w and o by separating agent i from the remaining n - 1 agents, we apply the dictator bound cost(i, w) ≤ cost(i, o) to agent i and the per-agent bound cost(a, w) ≤ cost(a, o) + d(w k, o k) to each remaining agent. Summing these inequalities yields SC(w) ≤ SC(o) + |univ \ {i}| * d(w k, o k).

    lines 52–75

    uses Finset.add_sum_erase, Finset.mem_univ, add_le_add, Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul

      have hsplit_w : two_facility_social_cost x p w =
          two_facility_cost x p i w + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a w := by
        rw [two_facility_social_cost]
        exact (Finset.add_sum_erase Finset.univ (fun a => two_facility_cost x p a w) (Finset.mem_univ i)).symm
      have hsplit_o : two_facility_social_cost x p o =
          two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o := by
        rw [two_facility_social_cost]
        exact (Finset.add_sum_erase Finset.univ (fun a => two_facility_cost x p a o) (Finset.mem_univ i)).symm
      have hbound : two_facility_social_cost x p w ≤
          two_facility_social_cost x p o
            + ((Finset.univ.erase i).card : ℝ) * dist (w k) (o k) := by
        rw [hsplit_w, hsplit_o]
        have h1 : two_facility_cost x p i w + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a w
            ≤ two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i,
                (two_facility_cost x p a o + dist (w k) (o k)) := by
          apply add_le_add hA
          exact Finset.sum_le_sum (fun a _ => hper a)
        have h2 : two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i,
                (two_facility_cost x p a o + dist (w k) (o k))
            = (two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o)
                + ((Finset.univ.erase i).card : ℝ) * dist (w k) (o k) := by
          rw [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul]
          ring
        linarith [h1, h2]
  7. The social cost of w is at most (2n - 1) SC(o)

    Since dictator i exists, the number of agents n = |ι| is at least 1, and the cardinality of ι \ {i} is n - 1 ≥ 0. Substituting d(w k, o k) ≤ 2 cost(i, o) and cost(i, o) ≤ SC(o) gives (n - 1) d(w k, o k) ≤ 2(n - 1) SC(o). Adding SC(o) yields SC(o) + 2(n - 1) SC(o) = (2n - 1) SC(o).

    lines 76–94

    uses Fintype.card_pos_iff.mpr, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ, Nat.cast_sub, mul_le_mul_of_nonneg_left

      have hn : 1 ≤ Fintype.card ι := Fintype.card_pos_iff.mpr ⟨i⟩
      have hcard : ((Finset.univ.erase i).card : ℝ) = (Fintype.card ι : ℝ) - 1 := by
        rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Nat.cast_sub hn]
        norm_num
      have hnonneg : (0:ℝ) ≤ (Fintype.card ι : ℝ) - 1 := by
        have : (1:ℝ) ≤ (Fintype.card ι : ℝ) := by exact_mod_cast hn
        linarith
      have hstep1 : ((Finset.univ.erase i).card : ℝ) * dist (w k) (o k)
          ≤ ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_cost x p i o) := by
        rw [hcard]
        exact mul_le_mul_of_nonneg_left hD hnonneg
      have hstep2 : ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_cost x p i o)
          ≤ ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_social_cost x p o) := by
        apply mul_le_mul_of_nonneg_left _ hnonneg
        linarith [hsc]
      have hfinal : two_facility_social_cost x p o
          + ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_social_cost x p o)
          = (2 * (Fintype.card ι : ℝ) - 1) * two_facility_social_cost x p o := by ring
      linarith [hbound, hstep1, hstep2, hfinal]
Finset.sum_eq_single
If all terms in a finite sum other than at a single element a are zero, the sum equals the term at a.
Finset.mem_univ
Every element of a finite type belongs to its universal finset univ.
if_pos
If a condition holds, the if-then-else expression evaluates to the 'then' branch.
dist_triangle
The triangle inequality in a metric space: d(x, z) ≤ d(x, y) + d(y, z).
dist_comm
Symmetry of the distance function: d(x, y) = d(y, x).
dist_nonneg
Distances in a metric space are non-negative: 0 ≤ d(x, y).
Finset.single_le_sum
An element of a finite sum of non-negative real numbers is bounded above by the sum.
two_facility_cost_nonneg
The two-facility cost of any agent is always non-negative.
Finset.add_sum_erase
A sum over a finite set s equals the value at a plus the sum over s with a removed.
add_le_add
If a ≤ b and c ≤ d, then a + c ≤ b + d.
Finset.sum_le_sum
If f(x) ≤ g(x) pointwise on a finite set, then the sum of f is bounded by the sum of g.
Finset.sum_add_distrib
The sum of two functions over a finite set equals the sum of the individual sums.
Finset.sum_const
Summing a constant b over a finite set s equals |s| • b.
nsmul_eq_mul
Scalar multiplication by a natural number n on real numbers equals multiplication by the cast of n.
Fintype.card_pos_iff.mpr
A finite type is nonempty if and only if its cardinality is at least 1.
Finset.card_erase_of_mem
Removing an element from a finite set decreases its cardinality by 1.
Finset.card_univ
The cardinality of Finset.univ for a finite type equals the cardinality of the type.
Nat.cast_sub
The real cast of a natural number difference n - m (when m ≤ n) equals the difference of their real casts.
mul_le_mul_of_nonneg_left
Multiplying both sides of an inequality b ≤ c by a non-negative real number preserves the inequality.

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_social_cost_le_of_one_approved {ι X : Type*} [Fintype ι] [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_social_cost x p w ≤ (2 * (Fintype.card ι : ℝ) - 1) * two_facility_social_cost x p o := by  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 _      have hjk : j = 1 - k := by omega      rw [hjk, 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 hci_w : two_facility_cost x p i w = dist (x i) (w k) := by    rw [hcost i w, if_pos hi]  have hA : two_facility_cost x p i w ≤ two_facility_cost x p i o := by    rw [hci_w, hci_o]    exact hwk.2 (o k) hok  have hD : dist (w k) (o k) ≤ 2 * two_facility_cost x p i o := 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    rw [hci_o]    linarith  have hper : ∀ a, two_facility_cost x p a w ≤ two_facility_cost x p a o + dist (w k) (o k) := by    intro a    rw [hcost a w, hcost a o]    split_ifs with h    · have htri := dist_triangle (x a) (o k) (w k)      rw [dist_comm (o k) (w k)] at htri      linarith    · have hnn := dist_nonneg (x := w k) (y := o k)      linarith  have hsc : two_facility_cost x p i o ≤ two_facility_social_cost x p o := by    rw [two_facility_social_cost]    exact Finset.single_le_sum (fun a _ => two_facility_cost_nonneg x p a o) (Finset.mem_univ i)  have hsplit_w : two_facility_social_cost x p w =      two_facility_cost x p i w + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a w := by    rw [two_facility_social_cost]    exact (Finset.add_sum_erase Finset.univ (fun a => two_facility_cost x p a w) (Finset.mem_univ i)).symm  have hsplit_o : two_facility_social_cost x p o =      two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o := by    rw [two_facility_social_cost]    exact (Finset.add_sum_erase Finset.univ (fun a => two_facility_cost x p a o) (Finset.mem_univ i)).symm  have hbound : two_facility_social_cost x p w ≤      two_facility_social_cost x p o        + ((Finset.univ.erase i).card : ℝ) * dist (w k) (o k) := by    rw [hsplit_w, hsplit_o]    have h1 : two_facility_cost x p i w + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a w        ≤ two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i,            (two_facility_cost x p a o + dist (w k) (o k)) := by      apply add_le_add hA      exact Finset.sum_le_sum (fun a _ => hper a)    have h2 : two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i,            (two_facility_cost x p a o + dist (w k) (o k))        = (two_facility_cost x p i o + ∑ a ∈ Finset.univ.erase i, two_facility_cost x p a o)            + ((Finset.univ.erase i).card : ℝ) * dist (w k) (o k) := by      rw [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul]      ring    linarith [h1, h2]  have hn : 1 ≤ Fintype.card ι := Fintype.card_pos_iff.mpr ⟨i⟩  have hcard : ((Finset.univ.erase i).card : ℝ) = (Fintype.card ι : ℝ) - 1 := by    rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Nat.cast_sub hn]    norm_num  have hnonneg : (0:ℝ) ≤ (Fintype.card ι : ℝ) - 1 := by    have : (1:ℝ) ≤ (Fintype.card ι : ℝ) := by exact_mod_cast hn    linarith  have hstep1 : ((Finset.univ.erase i).card : ℝ) * dist (w k) (o k)      ≤ ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_cost x p i o) := by    rw [hcard]    exact mul_le_mul_of_nonneg_left hD hnonneg  have hstep2 : ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_cost x p i o)      ≤ ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_social_cost x p o) := by    apply mul_le_mul_of_nonneg_left _ hnonneg    linarith [hsc]  have hfinal : two_facility_social_cost x p o      + ((Fintype.card ι : ℝ) - 1) * (2 * two_facility_social_cost x p o)      = (2 * (Fintype.card ι : ℝ) - 1) * two_facility_social_cost x p o := by ring  linarith [hbound, hstep1, hstep2, hfinal]
See it in the graphDiscuss this resultChallenge it