fse_path
lemmaverified
Path 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 is also v.
Statement
lemma fse_path {n : ℕ} (f : (Fin n → ℝ) → ℝ) (hSP : fse_SPAll f)
(c z : Fin n → ℝ) (hc : fse_InDomain c) (hz : fse_InDomain z) (v : ℝ) (hv : f c = v)
(hdiff : ∀ j, c j ≠ z j → c j ≠ v) : f z = v- 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_InDomainA location profile of n agents lies in the domain [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_lemmaCKey consequence of strategyproofness for all scaling functions: a unilateral deviation can change the outcome only if the outcome was at…
- fse_mixProfiles obtained from c by replacing the first k coordinates with those of z.
- Used by 2
- fse_mem_rangeA surjective mechanism that is strategyproof for all scaling functions always outputs some agent's reported location.
- 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…
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.
/-- Path 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` is also `v`. -/lemma fse_path {n : ℕ} (f : (Fin n → ℝ) → ℝ) (hSP : fse_SPAll f) (c z : Fin n → ℝ) (hc : fse_InDomain c) (hz : fse_InDomain z) (v : ℝ) (hv : f c = v) (hdiff : ∀ j, c j ≠ z j → c j ≠ v) : f z = v := by have hmixD : ∀ k, fse_InDomain (fse_mix c z k) := by intro k j; unfold fse_mix; split_ifs · exact hz j · exact hc j have key : ∀ k : ℕ, k ≤ n → f (fse_mix c z k) = v := by intro k induction k with | zero => intro _ have : fse_mix c z 0 = c := by funext j; simp [fse_mix] rw [this]; exact hv | succ k ih => intro hk have ih' := ih (by omega) set jk : Fin n := ⟨k, by omega⟩ with hjk have hupd : fse_mix c z (k + 1) = Function.update (fse_mix c z k) jk (z jk) := by funext j by_cases hj : j = jk · rw [hj, Function.update_self]; simp [fse_mix, hjk] · rw [Function.update_of_ne hj] have hne : j.val ≠ k := fun h => hj (Fin.ext (by simp [hjk, h])) simp only [fse_mix] by_cases hlt : j.val < k · simp [hlt, show j.val < k + 1 by omega] · simp [hlt, show ¬ j.val < k + 1 by omega] have hval : fse_mix c z k jk = c jk := by simp [fse_mix, hjk] by_cases hcz : c jk = z jk · have : fse_mix c z (k + 1) = fse_mix c z k := by rw [hupd, ← hcz, ← hval, Function.update_eq_self] rw [this]; exact ih' · have hne : f (fse_mix c z k) ≠ fse_mix c z k jk := by rw [ih', hval]; exact fun h => hdiff jk hcz h.symm rcases fse_lemmaC f hSP _ (hmixD k) jk (z jk) (hz jk) with h | h · exact absurd h hne · rw [hupd, h, ih'] have hfin : fse_mix c z n = z := by funext j; simp [fse_mix, j.isLt] rw [← hfin]; exact key n le_rfl