is_two_facility_feasible_of_is_fixed_dictator_output
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.
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.
rw [IsTwoFacilityFeasible] simp only [IsFixedDictatorOutput] at hw rcases hw with ⟨i, _, _, h0, h1⟩ | ⟨_, i, j, _, _, h0, h1⟩ | ⟨k, _, i, _, h0, h1⟩
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.
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⟩
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.
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⟩
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.
uses
Finset.mem_erase· simp only [IsClosestCandidate, Finset.mem_erase] at h0 h1 obtain ⟨hmk, _⟩ := h0 obtain ⟨⟨hnek, hm1k⟩, _⟩ := h1 fin_cases k
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.
uses
Fin.zero_eta· simp only [Fin.isValue, Fin.zero_eta] at * exact ⟨hmk, hm1k, fun h => hnek h.symm⟩
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.
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
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 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⟩