fse_dictatorship_conjecture_false
theoremverifiedoriginal
Refutation of the dictatorship conjecture of arXiv 2402.18908 (Section 8). For every number n ≥ 2 of agents there is a scaling function (namely q(y) = 1 - 9y/10) under which some agent's preference is not single-peaked, and yet there is a deterministic mechanism into [0,1] that is strategyproof, surjective and anonymous but is not a dictatorship (the leftmost mechanism).
Statement
theorem fse_dictatorship_conjecture_false (n : ℕ) [NeZero n] (hn : 2 ≤ n) :
∃ q : ℝ → ℝ, fse_IsScaling q ∧ (∃ x ∈ Set.Icc (0 : ℝ) 1, ¬ fse_SinglePeaked q x) ∧
∃ f : (Fin n → ℝ) → ℝ, fse_MapsToDomain f ∧ fse_SP q f ∧ fse_Surjective f ∧
fse_Anonymous 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 17
- 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_isScalingq0(y) = 1 - 9y/10 is a scaling function (continuous and positive on [0,1]).
- 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.
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 of the dictatorship conjecture of arXiv 2402.18908 (Section 8).** For every number `n ≥ 2` of agents there is a scaling function (namely `q(y) = 1 - 9y/10`) under which some agent's preference is not single-peaked, and yet there is a deterministic mechanism into `[0,1]` that is strategyproof, surjective and anonymous but is not a dictatorship (the leftmost mechanism). -/theorem fse_dictatorship_conjecture_false (n : ℕ) [NeZero n] (hn : 2 ≤ n) : ∃ q : ℝ → ℝ, fse_IsScaling q ∧ (∃ x ∈ Set.Icc (0 : ℝ) 1, ¬ fse_SinglePeaked q x) ∧ ∃ f : (Fin n → ℝ) → ℝ, fse_MapsToDomain f ∧ fse_SP q f ∧ fse_Surjective f ∧ fse_Anonymous f ∧ ¬ fse_Dictatorship f := ⟨fse_q0, fse_q0_isScaling, ⟨0, by norm_num, fse_q0_not_singlePeaked⟩, fse_leftmost, fse_leftmost_mapsTo, fse_leftmost_SP_of_antitone fse_q0 fse_q0_antitone (fun y hy => le_of_lt (fse_q0_isScaling.2 y hy)), fse_leftmost_surjective, fse_leftmost_anonymous, fse_leftmost_not_dictatorship hn⟩