Theorem 1 (Gibbard–Satterthwaite) — a strict voting procedure with at least three possible outcomes is strategy-proof iff it is dictatorial
ProvedStrategyProofArrow.Dictatorship.theorem_1Consider a strict committee : individuals, alternatives, every preference and every ballot a strong order, and a strict voting procedure whose range has elements, with . Then
where dictatorial means that some individual exists such that, at every strict ballot set , is the alternative of the range that ranks highest.
The dictatorship is relative to the range: when the dictator obtains their best alternative among those the procedure can select, not their best alternative overall (a partial dictatorship). With the theorem is the classical Gibbard–Satterthwaite theorem. The bound cannot be lowered: with two possible outcomes, majority voting between them is strategy-proof and not dictatorial.
Formalization Note Fintype.card ι, (range f).ncard, where range f collects the values of f at strict ballot sets only. holds automatically, so follows from and is not a separate hypothesis. Strategy-proofness is AGT.IncentiveCompatible. The paper's dictator function is any single-valued selection from 's maximal elements of ; for strict ballots that element is unique, and Dictatorial f says that is it.
import Mathlib import Definitions.Def_StrategyProofArrow_Dictatorship_Basic
namespace StrategyProofArrow.Dictatorship
open AGT
/-- **Theorem 1 (Gibbard–Satterthwaite)** (Satterthwaite, p. 11). For a strict committee with
`n ≥ 1` individuals whose strict voting procedure has a range `T_p` of `p ≥ 3` alternatives
(so `m ≥ p ≥ 3`), the procedure is strategy-proof if and only if it is dictatorial: some
individual always obtains their most preferred alternative of the range. -/
theorem theorem_1 {ι A : Type*} [Fintype ι] [Fintype A] [DecidableEq ι]
(hn : 1 ≤ Fintype.card ι)
(f : (ι → A → A → Prop) → A) (hp : 3 ≤ (range f).ncard) :
IncentiveCompatible f ↔ Dictatorial f := by sorry
end StrategyProofArrow.Dictatorship
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.