fixed_dictator_max_cost_le
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
- 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_max_cost_nonnegFor a finite nonempty set of agents, the max cost of any two-facility solution is nonnegative.
- fixed_dictator_max_cost_le_of_singletonsIn the two-facility location problem on a metric space with a finite nonempty set of agents, if no agent approves both facilities, agent i…
- IsFixedDictatorOutputw is an outcome of Fixed-Dictator (Mechanism 2 of arXiv:2610.18006) for some fixed agents and some tie-breaking, the three cases being: a…
- IsTwoFacilityFeasiblec = (c_1, c_2) is feasible iff c_1, c_2 ∈ C and c_1 ≠ c_2.
- fixed_dictator_max_cost_le_of_one_approvedIn the two-facility location problem on a general metric space with candidate set C and a finite nonempty set of agents, if no agent…
- IsClosestCandidatec ∈ C and d(y, c) ≤ d(y, c') for every c' ∈ C.
- fixed_dictator_max_cost_le_of_doubletonIn 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…
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.
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.
uses
two_facility_max_cost_nonneghave 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'⟩
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.
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
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.
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 hoWhen 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.
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.
- In two of the three cases (when an agent approves both facilities or when all agents approve only one facility), the helper lemmas establish a tighter approximation ratio of 3. Linear arithmetic relaxes this bound to 5 using the non-negativity of the optimal cost.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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