AFTD Auto-Formalizing Theoretical Domains

fse_lemmaC

lemmaverified

Key consequence of strategyproofness for all scaling functions: a unilateral deviation can change the outcome only if the outcome was at the deviator's own location.

Statement

lemma fse_lemmaC {n : ℕ} (f : (Fin n → ℝ) → ℝ) (hSP : fse_SPAll f)
    (x : Fin n → ℝ) (hx : fse_InDomain x) (i : Fin n) (t : ℝ) (ht : t ∈ Set.Icc (0 : ℝ) 1) :
    f x = x i ∨ f (Function.update x i t) = f x
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 4
  • fse_costFacility location with scaling effects (arXiv 2402.18908): an agent located at x incurs cost q y * |x - y| when the facility is placed at…
  • fse_InDomainA location profile of n agents lies in the domain [0,1].
  • fse_IsScalingA scaling function in the sense of arXiv 2402.18908: continuous and positive on [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…
Used by 2
  • 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_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

/-- Key consequence of strategyproofness for all scaling functions: a unilateral deviation can change the outcome only if the outcome was at the deviator's own location. -/lemma fse_lemmaC {n : ℕ} (f : (Fin n → ℝ) → ℝ) (hSP : fse_SPAll f)    (x : Fin n → ℝ) (hx : fse_InDomain x) (i : Fin n) (t : ℝ) (ht : t ∈ Set.Icc (0 : ℝ) 1) :    f x = x i ∨ f (Function.update x i t) = f x := by  by_contra hcon  push Not at hcon  obtain ⟨h1, h2⟩ := hcon  set y := f x with hy  set y' := f (Function.update x i t) with hy'  have hyy : 0 < |y - y'| := abs_pos.mpr (sub_ne_zero.mpr (Ne.symm h2))  have hxy : 0 < |x i - y| := abs_pos.mpr (sub_ne_zero.mpr (Ne.symm h1))  have hden : 0 < |x i - y'| + 1 := by positivity  set δ := |y - y'| * |x i - y| / (|x i - y'| + 1) with hδ  have hδpos : 0 < δ := div_pos (mul_pos hyy hxy) hden  have hδeq : δ * (|x i - y'| + 1) = |y - y'| * |x i - y| := by    rw [hδ]; field_simp  let q : ℝ → ℝ := fun z => |z - y'| + δ  have hq : fse_IsScaling q := by    refine ⟨?_, ?_⟩    · exact (Continuous.continuousOn (by fun_prop))    · intro z _; positivity  have := hSP q hq x hx i t ht  simp only [fse_cost, q] at this  rw [← hy, ← hy', sub_self, abs_zero, zero_add] at this  nlinarith [abs_nonneg (x i - y'), abs_nonneg (y - y')]
See it in the graphDiscuss this resultChallenge it