fse_mem_range
lemmaverified
A surjective mechanism that is strategyproof for all scaling functions always outputs some agent's reported location.
Statement
lemma fse_mem_range {n : ℕ} (f : (Fin n → ℝ) → ℝ) (hSP : fse_SPAll f) (hsurj : fse_Surjective f)
(x : Fin n → ℝ) (hx : fse_InDomain x) : ∃ i, f x = x i- Source
- step towards fse_scaling_oblivious_dictatorship / fse_dictatorship_conjecture_false (dictatorship conjecture of Facility Location Games with Scaling Effects (arXiv:2402.18908v3), Conclusion)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- fse_InDomainA location profile of n agents lies in the domain [0,1].
- fse_SurjectiveSurjectivity (onto [0,1]).
- fse_SPAllA scaling-oblivious mechanism is strategyproof for *every* scaling function: the mechanism does not know q, and no agent can gain under…
- fse_pathPath lemma: if the outcome at c is v, and every coordinate in which z differs from c has c-value different from v, then the outcome at z…
- fse_exists_avoidSome point of [0,1] avoids any given finite set.
- Used by 2
- fse_scaling_oblivious_dictatorshipThe dictatorship conjecture holds for scaling-oblivious mechanisms. If a mechanism into [0,1] does not depend on the scaling function and…
- fse_followMoving the coordinate of agent i when i's location is not shared and the outcome is at i's location: the outcome follows agent i.
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.
/-- A surjective mechanism that is strategyproof for all scaling functions always outputs some agent's reported location. -/lemma fse_mem_range {n : ℕ} (f : (Fin n → ℝ) → ℝ) (hSP : fse_SPAll f) (hsurj : fse_Surjective f) (x : Fin n → ℝ) (hx : fse_InDomain x) : ∃ i, f x = x i := by by_contra hcon push Not at hcon set c := f x with hcdef obtain ⟨d, hd, hdc⟩ := fse_exists_avoid {c} (Set.finite_singleton c) obtain ⟨e, he, hecd⟩ := fse_exists_avoid {c, d} (Set.toFinite _) simp only [Set.mem_singleton_iff] at hdc simp only [Set.mem_insert_iff, Set.mem_singleton_iff, not_or] at hecd obtain ⟨w, hw, hfw⟩ := hsurj d hd let w' : Fin n → ℝ := fun i => if w i = c then e else w i have hw' : fse_InDomain w' := by intro i; simp only [w']; split_ifs · exact he · exact hw i have h1 : f w' = d := by apply fse_path f hSP w w' hw hw' d hfw intro j hj simp only [w'] at hj split_ifs at hj with hjc · rw [hjc]; exact fun h => hdc h.symm · exact absurd rfl hj have h2 : f w' = c := by apply fse_path f hSP x w' hx hw' c rfl intro j _ h exact hcon j h.symm exact hdc (h1.symm.trans h2)