fixed_dictator_social_cost_le
On a general metric space, for n ≥ 2 agents with known non-empty approval preferences over two facilities and any candidate set C, every outcome w of Fixed-Dictator satisfies SC(w) ≤ (2n - 1) SC(o) for every feasible solution o; that is, its approximation ratio for the social cost is at most 2n - 1.
Statement
theorem fixed_dictator_social_cost_le {ι X : Type*} [Fintype ι] [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_social_cost x p w ≤ (2 * (Fintype.card ι : ℝ) - 1) * two_facility_social_cost x p o
- Formalizes
- arXiv:2610.18006 (Truthful two-facility location with candidate locations in metric spaces), Theorem 4.5. Lean differs: holds for every choice of the fixed agents and every tie-breaking (IsFixedDictatorOutput), and is stated against every feasible o rather than as a ratio
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- fixed_dictator_social_cost_le_of_doubletonCase 1 of Theorem 4.5: if the facilities are at the two closest candidate locations w_1, w_2 of an agent i approving both, then SC(w) ≤…
- fixed_dictator_social_cost_le_of_singletonsCase 2 of Theorem 4.5: with no agent approving both facilities, if F_1 is at a closest candidate w_1 of an agent i approving F_1 and F_2…
- fixed_dictator_social_cost_le_of_one_approvedCase 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…
- two_facility_social_costSC(c) = sum over agents i of cost_i(c).
- IsTwoFacilityFeasiblec = (c_1, c_2) is feasible iff c_1, c_2 ∈ C and c_1 ≠ c_2.
- IsClosestCandidatec ∈ C and d(y, c) ≤ d(y, c') for every c' ∈ C.
The proof, explained
The proof proceeds by case analysis on the definition of a Fixed-Dictator outcome (IsFixedDictatorOutput). Depending on the approval profile, there are three mutually exhaustive configurations: an agent approves both facilities, every agent approves at most one facility with both facilities approved, or only one facility is approved overall. In each configuration, the approximation bound SC(w) ≤ (2n - 1) SC(o) is dispatched directly by an existing helper theorem dedicated to that case.
It suffices to verify the social cost bound in each of the three defining cases of the Fixed-Dictator mechanism.
By definition of IsFixedDictatorOutput, any outcome w of the Fixed-Dictator mechanism arises in one of three ways: (1) some agent approves both facilities; (2) no agent approves both facilities, but each facility is approved by some agent; or (3) every agent approves only one particular facility. We perform a case split on these three disjuncts.
rcases hw with ⟨i, hi0, hi1, hw0, hw1⟩ | ⟨hnd, i, j, hi, hj, hw0, hw1⟩ | ⟨k, hk, i, hi, hwk, hwk'⟩
The bound holds when some agent approves both facilities.
In this case, an agent i approves both facilities, and w assigns the facilities to the two closest candidates to x(i) in C. The helper theorem fixed_dictator_social_cost_le_of_doubleton directly establishes that SC(w) ≤ (2n - 1) SC(o).
uses
fixed_dictator_social_cost_le_of_doubleton· exact fixed_dictator_social_cost_le_of_doubleton C x p w i hi0 hi1 hw0 hw1 o hoThe bound holds when agents approve at most one facility and both facilities have approvals.
In this case, no agent approves both facilities, but some agent i approves facility 0 and some agent j approves facility 1, with w_0 closest to x(i) and w_1 closest to x(j) in C \ {w_0}. Applying fixed_dictator_social_cost_le_of_singletons yields the bound SC(w) ≤ (2n - 1) SC(o).
uses
fixed_dictator_social_cost_le_of_singletons· exact fixed_dictator_social_cost_le_of_singletons C x p hnd w i j hi hj hw0 hw1 o hoThe bound holds when only one facility is approved across all agents.
In the remaining case, all agents approve only facility k and reject facility 1 - k, while an agent i approving facility k chooses w_k and w_{1-k} as their two closest candidates. The theorem fixed_dictator_social_cost_le_of_one_approved immediately completes the proof.
uses
fixed_dictator_social_cost_le_of_one_approved· exact fixed_dictator_social_cost_le_of_one_approved C x p w k hk i hi hwk hwk' o ho
fixed_dictator_social_cost_le_of_doubleton- For any feasible two-facility placement o, if an agent approves both facilities and w assigns the facilities to that agent's two closest candidates in C, then SC(w) ≤ (2n - 1) SC(o).
fixed_dictator_social_cost_le_of_singletons- For any feasible two-facility placement o, if no agent approves both facilities, but one agent approves facility 0 and another approves facility 1, and w assigns each facility to that agent's closest candidate in C (with the second chosen from C \ {w 0}), then SC(w) ≤ (2n - 1) SC(o).
fixed_dictator_social_cost_le_of_one_approved- For any feasible two-facility placement o, if all agents approve only facility k and disapprove facility 1 - k, and an agent approving k dictates w_k and w_{1-k} as their two closest candidates in C, then SC(w) ≤ (2n - 1) SC(o).
- The hypotheses hp (every agent approves at least one facility) and hn (there are at least two agents) appear in the theorem statement, but none of the three specialized lemmas require them.
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 fixed_dictator_social_cost_le {ι X : Type*} [Fintype ι] [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_social_cost x p w ≤ (2 * (Fintype.card ι : ℝ) - 1) * two_facility_social_cost x p o := by rcases hw with ⟨i, hi0, hi1, hw0, hw1⟩ | ⟨hnd, i, j, hi, hj, hw0, hw1⟩ | ⟨k, hk, i, hi, hwk, hwk'⟩ · exact fixed_dictator_social_cost_le_of_doubleton C x p w i hi0 hi1 hw0 hw1 o ho · exact fixed_dictator_social_cost_le_of_singletons C x p hnd w i j hi hj hw0 hw1 o ho · exact fixed_dictator_social_cost_le_of_one_approved C x p w k hk i hi hwk hwk' o ho