AFTD Auto-Formalizing Theoretical Domains

fixed_dictator_max_cost_le

theoremverifiedformalization

On general metric spaces, in the two-facility location problem with candidate locations C and a finite nonempty set of n ≥ 2 agents with non-empty approval preferences p, every output w of the Fixed-Dictator mechanism satisfies two_facility_max_cost x p w ≤ 5 * two_facility_max_cost x p o for every feasible two-facility solution o; that is, the approximation ratio with respect to the max cost is at most 5.

Statement

theorem fixed_dictator_max_cost_le {ι X : Type*} [Fintype ι] [Nonempty ι] [MetricSpace X] [DecidableEq X]
    (C : Finset X) (x : ι → X) (p : ι → Fin 2 → Bool) (hp : ∀ i, p i 0 = true ∨ p i 1 = true)
    (hn : 2 ≤ Fintype.card ι) (w : Fin 2 → X) (hw : IsFixedDictatorOutput C x p w)
    (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:1341
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8

Read back from the Lean

Let $\iota$ be a finite, nonempty type with at least 2 elements ($|\iota| \ge 2$), and let $X$ be a metric space with decidable equality. Let $C \subseteq X$ be a finite set of candidates. Let $x : \iota \to X$ assign a location to each agent, and let $p : \iota \to \text{Fin } 2 \to \text{Bool}$ assign to each agent their demand/approval for each of two facilities (0 and 1), such that every agent demands at least one facility ($\forall i, p(i, 0) = \text{true} \lor p(i, 1) = \text{true}$). Let $w : \text{Fin } 2 \to X$ be an output of the fixed dictator mechanism with respect to $C, x, p$ (IsFixedDictatorOutput C x p w). Let $o : \text{Fin } 2 \to X$ be any feasible two-facility placement from $C$ (IsTwoFacilityFeasible C o, meaning $o(0) \in C$, $o(1) \in C$, and $o(0) \ne o(1)$). Then the maximum two-facility cost of $w$ is at most 5 times the maximum two-facility cost of $o$: $$\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 proceeds by case analysis on the definition of the Fixed-Dictator mechanism (IsFixedDictatorOutput), which specifies three configurations depending on the agents' approvals: an agent approves both facilities, no agent approves both facilities, or only one facility is approved overall. In each configuration, a dedicated helper lemma bounds the maximum cost of the mechanism's output by either 3 or 5 times the optimal cost. Because the optimal cost is non-negative, the bound of 5 holds in all three cases.

  1. The optimal max cost is non-negative, and the proof reduces to three cases depending on the approval structure of the mechanism.

    We first establish that the benchmark cost two_facility_max_cost x p o is non-negative via two_facility_max_cost_nonneg. We then perform a case analysis on hw (IsFixedDictatorOutput), which partitions into three cases: (1) some agent approves both facilities; (2) no agent approves both facilities and two distinct agents dictate each facility; or (3) all agents approve only a single facility.

    lines 7–8

    uses two_facility_max_cost_nonneg

      have hpos : 0 ≤ two_facility_max_cost x p o := two_facility_max_cost_nonneg x p o
      rcases hw with ⟨i, hi0, hi1, hw0, hw1⟩ | ⟨hnd, i, j, hi, hj, hw0, hw1⟩ | ⟨k, hk, i, hi, hwk, hwk'⟩
  2. When an agent approves both facilities, the approximation ratio is at most 5.

    By fixed_dictator_max_cost_le_of_doubleton, the maximum cost of w is at most 3 times the benchmark cost. Since the benchmark cost is non-negative (hpos), linear arithmetic (linarith) weakens the factor 3 bound to 5.

    lines 9–10

    uses fixed_dictator_max_cost_le_of_doubleton

      · have h3 := fixed_dictator_max_cost_le_of_doubleton C x p w i hi0 hi1 hw0 hw1 o ho
        linarith
  3. When no agent approves both facilities, the approximation ratio is at most 5.

    This case is handled directly by fixed_dictator_max_cost_le_of_singletons, which bounds the cost of w by 5 times the benchmark cost.

    line 11

    uses fixed_dictator_max_cost_le_of_singletons

      · exact fixed_dictator_max_cost_le_of_singletons C x p hnd w i j hi hj hw0 hw1 o ho
  4. When all agents approve only a single facility, the approximation ratio is at most 5.

    By fixed_dictator_max_cost_le_of_one_approved, the maximum cost of w is at most 3 times the benchmark cost. Since the benchmark cost is non-negative (hpos), linear arithmetic (linarith) weakens the factor 3 bound to 5.

    lines 12–13

    uses fixed_dictator_max_cost_le_of_one_approved

      · have h3 := fixed_dictator_max_cost_le_of_one_approved C x p w k hk i hi hwk hwk' o ho
        linarith
two_facility_max_cost_nonneg
The maximum cost across all agents for any two-facility placement is non-negative.
fixed_dictator_max_cost_le_of_doubleton
When some agent approves both facilities and dictates both candidate locations, the Fixed-Dictator output has max cost at most 3 times that of any feasible solution.
fixed_dictator_max_cost_le_of_singletons
When no agent approves both facilities and two distinct agents dictate the two facilities, the Fixed-Dictator output has max cost at most 5 times that of any feasible solution.
fixed_dictator_max_cost_le_of_one_approved
When all agents approve only one facility and one agent dictates both candidate locations, the Fixed-Dictator output has max cost at most 3 times that of any feasible solution.

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 4.14 of arXiv:2610.18006: Fixed-Dictator achieves approximation ratio at most 5 for the max cost on general metric spaces. -/theorem fixed_dictator_max_cost_le {ι X : Type*} [Fintype ι] [Nonempty ι] [MetricSpace X] [DecidableEq X]    (C : Finset X) (x : ι → X) (p : ι → Fin 2 → Bool) (hp : ∀ i, p i 0 = true ∨ p i 1 = true)    (hn : 2 ≤ Fintype.card ι) (w : Fin 2 → X) (hw : IsFixedDictatorOutput C x p w)    (o : Fin 2 → X) (ho : IsTwoFacilityFeasible C o) :    two_facility_max_cost x p w ≤ 5 * two_facility_max_cost x p o := by  have hpos : 0 ≤ two_facility_max_cost x p o := two_facility_max_cost_nonneg x p o  rcases hw with ⟨i, hi0, hi1, hw0, hw1⟩ | ⟨hnd, i, j, hi, hj, hw0, hw1⟩ | ⟨k, hk, i, hi, hwk, hwk'⟩  · have h3 := fixed_dictator_max_cost_le_of_doubleton C x p w i hi0 hi1 hw0 hw1 o ho    linarith  · exact fixed_dictator_max_cost_le_of_singletons C x p hnd w i j hi hj hw0 hw1 o ho  · have h3 := fixed_dictator_max_cost_le_of_one_approved C x p w k hk i hi hwk hwk' o ho    linarith
See it in the graphDiscuss this resultChallenge it