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
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.
/-- **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