AFTD Auto-Formalizing Theoretical Domains

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

/-- 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)
See it in the graphDiscuss this resultChallenge it