AFTD Auto-Formalizing Theoretical Domains

is_two_facility_feasible_of_is_fixed_dictator_output

theoremverified

Sanity: every Fixed-Dictator output is a feasible solution (two distinct candidate locations).

Statement

theorem is_two_facility_feasible_of_is_fixed_dictator_output {ι X : Type*} [MetricSpace X] [DecidableEq X]
    (C : Finset X) (x : ι → X) (p : ι → Fin 2 → Bool) (w : Fin 2 → X)
    (hw : IsFixedDictatorOutput C x p w) : IsTwoFacilityFeasible C w
Source
sanity lemma for IsFixedDictatorOutput (arXiv:2610.18006 (Truthful two-facility location with candidate locations in metric spaces))
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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.
  • IsClosestCandidatec ∈ C and d(y, c) ≤ d(y, c') for every c' ∈ C.

The proof, explained

A Fixed-Dictator output selects two facility locations from candidate set C by first choosing a closest candidate to some voter, and then choosing a closest candidate from the candidate set with the first facility removed. In all three cases of the mechanism's definition, the second facility is explicitly drawn from the candidate set minus the first facility, guaranteeing that both locations belong to C and are distinct. Case analysis on the mechanism's branches and the index of the approved facility completes the verification.

  1. The goal reduces to checking feasibility across the three cases of a Fixed-Dictator output.

    We rewrite the definition of two-facility feasibility, which requires w 0 ∈ C, w 1 ∈ C, and w 0 ≠ w 1. Unfolding the definition of a Fixed-Dictator output reveals three cases: a single voter dictates both facilities, two separate voters dictate the two facilities, or only one facility k ∈ {0, 1} receives approvals while the other is chosen from the remaining candidates.

    lines 4–6

      rw [IsTwoFacilityFeasible]
      simp only [IsFixedDictatorOutput] at hw
      rcases hw with ⟨i, _, _, h0, h1⟩ | ⟨_, i, j, _, _, h0, h1⟩ | ⟨k, _, i, _, h0, h1⟩
  2. When a single voter dictates both facilities, the output is feasible.

    By definition of closest candidate and set erasure, w 0 is chosen from C, and w 1 is chosen from C with w 0 removed. Thus w 0 ∈ C, w 1 ∈ C, and w 1 ≠ w 0, which implies w 0 ≠ w 1.

    lines 7–10

    uses Finset.mem_erase

      · simp only [IsClosestCandidate, Finset.mem_erase] at h0 h1
        obtain ⟨hm0, _⟩ := h0
        obtain ⟨⟨hne, hm1⟩, _⟩ := h1
        exact ⟨hm0, hm1, fun h => hne h.symm⟩
  3. When different voters dictate the two facilities, the output is feasible.

    Similarly, voter i selects w 0 ∈ C and voter j selects w 1 from C with w 0 removed. This directly gives w 0 ∈ C, w 1 ∈ C, and w 1 ≠ w 0, hence w 0 ≠ w 1.

    lines 11–14

    uses Finset.mem_erase

      · simp only [IsClosestCandidate, Finset.mem_erase] at h0 h1
        obtain ⟨hm0, _⟩ := h0
        obtain ⟨⟨hne, hm1⟩, _⟩ := h1
        exact ⟨hm0, hm1, fun h => hne h.symm⟩
  4. When approvals exist for only one facility k, the two chosen locations belong to C and are distinct.

    Unfolding candidate closeness and set erasure shows that w k ∈ C while w (1 - k) is chosen from C with w k removed, ensuring w (1 - k) ∈ C and w (1 - k) ≠ w k. We then split into cases depending on whether k is 0 or 1.

    lines 15–18

    uses Finset.mem_erase

      · simp only [IsClosestCandidate, Finset.mem_erase] at h0 h1
        obtain ⟨hmk, _⟩ := h0
        obtain ⟨⟨hnek, hm1k⟩, _⟩ := h1
        fin_cases k
  5. In the subcase k = 0, the output is feasible.

    Simplifying the indices with k = 0 yields w 0 ∈ C and w (1 - 0) = w 1 ∈ C with w 1 ≠ w 0, so w 0 ≠ w 1.

    lines 19–20

    uses Fin.zero_eta

        · simp only [Fin.isValue, Fin.zero_eta] at *
          exact ⟨hmk, hm1k, fun h => hnek h.symm⟩
  6. In the subcase k = 1, the output is feasible.

    Simplifying the indices with k = 1 yields w 1 ∈ C and w (1 - 1) = w 0 ∈ C with w 0 ≠ w 1.

    lines 21–22

    uses Fin.mk_one

        · simp only [Fin.isValue, Fin.mk_one] at *
          exact ⟨hm1k, hmk, hnek⟩
Finset.mem_erase
An element a is in s.erase b if and only if a ≠ b and a ∈ s.
Fin.zero_eta
The Fin 2 element represented as ⟨0, _⟩ is definitionally equal to 0.
Fin.mk_one
The Fin 2 element represented as ⟨1, _⟩ is definitionally equal to 1.

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 is_two_facility_feasible_of_is_fixed_dictator_output {ι X : Type*} [MetricSpace X] [DecidableEq X]    (C : Finset X) (x : ι → X) (p : ι → Fin 2 → Bool) (w : Fin 2 → X)    (hw : IsFixedDictatorOutput C x p w) : IsTwoFacilityFeasible C w := by  rw [IsTwoFacilityFeasible]  simp only [IsFixedDictatorOutput] at hw  rcases hw with ⟨i, _, _, h0, h1⟩ | ⟨_, i, j, _, _, h0, h1⟩ | ⟨k, _, i, _, h0, h1⟩  · simp only [IsClosestCandidate, Finset.mem_erase] at h0 h1    obtain ⟨hm0, _⟩ := h0    obtain ⟨⟨hne, hm1⟩, _⟩ := h1    exact ⟨hm0, hm1, fun h => hne h.symm⟩  · simp only [IsClosestCandidate, Finset.mem_erase] at h0 h1    obtain ⟨hm0, _⟩ := h0    obtain ⟨⟨hne, hm1⟩, _⟩ := h1    exact ⟨hm0, hm1, fun h => hne h.symm⟩  · simp only [IsClosestCandidate, Finset.mem_erase] at h0 h1    obtain ⟨hmk, _⟩ := h0    obtain ⟨⟨hnek, hm1k⟩, _⟩ := h1    fin_cases k    · simp only [Fin.isValue, Fin.zero_eta] at *      exact ⟨hmk, hm1k, fun h => hnek h.symm⟩    · simp only [Fin.isValue, Fin.mk_one] at *      exact ⟨hm1k, hmk, hnek⟩
See it in the graphDiscuss this resultChallenge it