Theorem 1 (Gibbard–Satterthwaite) — a strict voting procedure with ≥ 3 outcomes is strategy-proof iff dictatorial
ProvedStrategyProofArrow.WeakGS.theorem_1Consider a strict committee: individuals, a finite set of alternatives, and ballots restricted to strong orders (no indifference between distinct alternatives). Let be a strict voting procedure whose range contains alternatives (so ). Then
where dictatorial means that some individual obtains, at every strict ballot set , the -best element of .
This is the Gibbard–Satterthwaite theorem in the form that allows a range smaller than the alternative set: a strategy-proof procedure that never selects some alternatives is still dictatorial on its range ("partially dictatorial"). In the extension to ballots with indifference (Theorem 1′) it is applied to the strict procedure produced by Lemma 9.
Formalization Note Strict ballot sets are StrongProfile ι A (functions into the subtype of strong orders), the procedure is a total function on them, and is Set.range ν, so is 3 ≤ (Set.range ν).ncard; is automatic for a finite type A. The individuals form a finite type ι with . Dictatorial is StrictDictatorial: for all , which for strong orders says is 's top element of . This restates the goal of the companion mission on strict committees in this mission's encoding.
import Mathlib import Definitions.Def_StrategyProofArrow_WeakGS_Basic
namespace StrategyProofArrow.WeakGS
/-- **Theorem 1 (Gibbard–Satterthwaite)** (Satterthwaite, p. 11). For a strict committee with
`n ≥ 1` individuals and `m ≥ p ≥ 3`, where `p` is the number of alternatives in the range of the
strict voting procedure `ν`, `ν` is strategy-proof if and only if it is dictatorial. -/
theorem theorem_1 {ι A : Type*} [Fintype ι] [Fintype A] [DecidableEq ι]
(hn : 1 ≤ Fintype.card ι) (ν : StrictVotingProcedure ι A)
(hp : 3 ≤ (Set.range ν).ncard) :
StrictStrategyProof ν ↔ StrictDictatorial ν := by sorry
end StrategyProofArrow.WeakGS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.