AFTD Auto-Formalizing Theoretical Domains

fse_conjecture_false_qdep

theoremverifiedoriginal

Refutation in the model with the scaling function as input. The mechanism fse_F (which receives q) is strategyproof and surjective for every scaling function, yet it is not a dictatorship: for q(y) = 1 - 9y/10, under which some agent's preference is not single-peaked, it is the (anonymous) leftmost mechanism.

Statement

theorem fse_conjecture_false_qdep (n : ℕ) [NeZero n] (hn : 2 ≤ n) :
    (∀ q : ℝ → ℝ, fse_IsScaling q →
        fse_SP q (fse_F (n := n) q) ∧ fse_Surjective (fse_F (n := n) q) ∧
        fse_MapsToDomain (fse_F (n := n) q)) ∧
      ¬ fse_SinglePeaked fse_q0 0 ∧ ¬ fse_Dictatorship (fse_F (n := n) fse_q0) ∧
      fse_Anonymous (fse_F (n := n) fse_q0)
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 18
  • fse_IsScalingA scaling function in the sense of arXiv 2402.18908: continuous and positive on [0,1].
  • fse_MapsToDomainA deterministic mechanism maps every profile in [0,1]^n to a facility location in [0,1].
  • fse_SPStrategyproofness for the scaling function q: no agent can lower her scaled cost by misreporting her location (any misreport in [0,1]).
  • fse_SurjectiveSurjectivity (onto [0,1]).
  • fse_AnonymousAnonymity: permuting the agents' labels does not change the outcome.
  • fse_Dictatorshipf is a dictatorship: some fixed agent always gets her own location.
  • fse_SinglePeakedThe (weak) single-peakedness of the preference of an agent at x under scaling q: the cost does not decrease when the facility moves away…
  • fse_leftmostThe leftmost mechanism: place the facility at the leftmost reported location.
  • fse_q0The linear scaling function q(y) = 1 - 9y/10.
  • fse_leftmost_mapsToThe leftmost mechanism maps [0,1]^n into [0,1].
  • fse_leftmost_SP_of_antitoneKey lemma: for every scaling function that is non-negative and non-increasing on [0,1], the leftmost mechanism is strategyproof.
  • fse_q0_antitoneq0 is non-increasing on [0,1].
  • fse_q0_not_singlePeakedUnder q0, the preference of the agent located at 0 is not single-peaked: the facility at 1/2 costs her 11/40, but the farther location 1…
  • fse_leftmost_surjectiveThe leftmost mechanism is surjective onto [0,1] (unanimous profiles).
  • fse_leftmost_anonymousThe leftmost mechanism is anonymous.
  • fse_leftmost_not_dictatorshipWith at least two agents the leftmost mechanism is not a dictatorship.
  • fse_FThe q-dependent mechanism used for the refutation in the model where the mechanism also receives the scaling function: the leftmost…
  • fse_dictator_SPA dictatorship is strategyproof for every non-negative scaling function.

Lean source view module on GitHub

/-- **Refutation in the model with the scaling function as input.** The mechanism `fse_F` (which receives `q`) is strategyproof and surjective for every scaling function, yet it is not a dictatorship: for `q(y) = 1 - 9y/10`, under which some agent's preference is not single-peaked, it is the (anonymous) leftmost mechanism. -/theorem fse_conjecture_false_qdep (n : ℕ) [NeZero n] (hn : 2 ≤ n) :    (∀ q : ℝ → ℝ, fse_IsScaling q →        fse_SP q (fse_F (n := n) q) ∧ fse_Surjective (fse_F (n := n) q) ∧        fse_MapsToDomain (fse_F (n := n) q)) ∧      ¬ fse_SinglePeaked fse_q0 0 ∧ ¬ fse_Dictatorship (fse_F (n := n) fse_q0) ∧      fse_Anonymous (fse_F (n := n) fse_q0) := by  have hF0 : fse_F (n := n) fse_q0 = fse_leftmost := by    funext x; simp [fse_F, fse_q0_antitone]  refine ⟨fun q hq => ?_, fse_q0_not_singlePeaked, ?_, ?_⟩  · have hpos : ∀ y ∈ Set.Icc (0 : ℝ) 1, 0 ≤ q y := fun y hy => le_of_lt (hq.2 y hy)    by_cases ha : AntitoneOn q (Set.Icc 0 1)    · have hF : fse_F (n := n) q = fse_leftmost := by funext x; simp [fse_F, ha]      rw [hF]      exact ⟨fse_leftmost_SP_of_antitone q ha hpos, fse_leftmost_surjective, fse_leftmost_mapsTo⟩    · have hF : fse_F (n := n) q = fun x => x 0 := by funext x; simp [fse_F, ha]      rw [hF]      refine ⟨fse_dictator_SP q hpos 0, fun y hy => ⟨fun _ => y, fun _ => hy, rfl⟩,        fun x hx => hx 0⟩  · rw [hF0]; exact fse_leftmost_not_dictatorship hn  · rw [hF0]; exact fse_leftmost_anonymous
See it in the graphDiscuss this resultChallenge it