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
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.
/-- 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')]