AFTD Auto-Formalizing Theoretical Domains

fixed_dictator_social_cost_le

theoremverifiedformalization

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

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.

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

    line 6

      rcases hw with ⟨i, hi0, hi1, hw0, hw1⟩ | ⟨hnd, i, j, hi, hj, hw0, hw1⟩ | ⟨k, hk, i, hi, hwk, hwk'⟩
  2. 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).

    line 7

    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 ho
  3. The 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).

    line 8

    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 ho
  4. The 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.

    line 9

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

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