AFTD Auto-Formalizing Theoretical Domains

fse_scaling_oblivious_dictatorship

theoremverifiedoriginal

The dictatorship conjecture holds for scaling-oblivious mechanisms. If a mechanism into [0,1] does not depend on the scaling function and is strategyproof for every continuous positive scaling function, and it is surjective onto [0,1], then it is a dictatorship.

Statement

theorem fse_scaling_oblivious_dictatorship {n : ℕ} [NeZero n] (f : (Fin n → ℝ) → ℝ)
    (hSP : fse_SPAll f) (hsurj : fse_Surjective f) : fse_Dictatorship f
Related work
operator (Claude), 2026-10-05: resolution of the conjecture of Facility Location Games with Scaling Effects (arXiv:2402.18908v3), Section 2, Theorem 4 and the concluding conjecture that the deterministic strategyproof and surjective mechanisms under scaled preferences are dictatorships: true for mechanisms that do not depend on the scaling function and are strategyproof for every continuous positive q (they are dictatorships); false when the mechanism knows q, via q(y) = 1 - 9y/10 (not single-peaked) and the leftmost mechanism; found by a search agent, checked by the Lean kernel
Verified
05 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • fse_InDomainA location profile of n agents lies in the domain [0,1].
  • fse_SurjectiveSurjectivity (onto [0,1]).
  • fse_Dictatorshipf is a dictatorship: some fixed agent always gets her own location.
  • 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.
  • fse_mem_rangeA surjective mechanism that is strategyproof for all scaling functions always outputs some agent's reported location.
  • 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.
Used by 1

Lean source view module on GitHub

/-- **The dictatorship conjecture holds for scaling-oblivious mechanisms.** If a mechanism into `[0,1]` does not depend on the scaling function and is strategyproof for every continuous positive scaling function, and it is surjective onto `[0,1]`, then it is a dictatorship. -/theorem fse_scaling_oblivious_dictatorship {n : ℕ} [NeZero n] (f : (Fin n → ℝ) → ℝ)    (hSP : fse_SPAll f) (hsurj : fse_Surjective f) : fse_Dictatorship f := by  -- a profile with distinct coordinates  let p0 : Fin n → ℝ := fun i => (i.val : ℝ) / n  have hn : (0 : ℝ) < n := by exact_mod_cast Nat.pos_of_ne_zero (NeZero.ne n)  have hp0 : fse_InDomain p0 := by    intro i    refine ⟨by positivity, ?_⟩    rw [div_le_one hn]; exact_mod_cast i.isLt.le  have hp0inj : ∀ a b : Fin n, p0 a = p0 b → a = b := by    intro a b h    simp only [p0] at h    rw [div_left_inj' hn.ne'] at h    exact Fin.ext (by exact_mod_cast h)  obtain ⟨istar, hstar⟩ := fse_mem_range f hSP hsurj p0 hp0  refine ⟨istar, fun x hx => ?_⟩  obtain ⟨t0, ht0, ht0n⟩ := fse_exists_avoid (Set.range x ∪ Set.range p0)    ((Set.finite_range x).union (Set.finite_range p0))  simp only [Set.mem_union, Set.mem_range, not_or, not_exists] at ht0n  obtain ⟨hx0, hp00⟩ := ht0n  -- step a: move agent istar to t0 in p0  have ha : f (Function.update p0 istar t0) = t0 :=    fse_follow f hSP hsurj p0 hp0 istar hstar      (fun k hk h => hk (hp0inj k istar h)) t0 ht0  -- step b: move all other agents to their x-locations  have hz : fse_InDomain (Function.update x istar t0) := by    intro k    by_cases hk : k = istar    · subst hk; simp [ht0]    · simp [Function.update_of_ne hk, hx k]  have hc1 : fse_InDomain (Function.update p0 istar t0) := by    intro k    by_cases hk : k = istar    · subst hk; simp [ht0]    · simp [Function.update_of_ne hk, hp0 k]  have hb : f (Function.update x istar t0) = t0 := by    apply fse_path f hSP _ _ hc1 hz t0 ha    intro j hj    by_cases hjs : j = istar    · subst hjs; simp at hj    · rw [Function.update_of_ne hjs]; exact fun h => hp00 j h  -- step c: move agent istar back to x istar  have hc := fse_follow f hSP hsurj (Function.update x istar t0) hz istar    (by simp [hb]) (fun k hk => by      rw [Function.update_of_ne hk, Function.update_self]; exact fun h => hx0 k h)    (x istar) (hx istar)  rw [Function.update_idem, Function.update_eq_self] at hc  exact hc
See it in the graphDiscuss this resultChallenge it