Theorem 1′ — with indifference allowed, a strategy-proof voting procedure with ≥ 3 outcomes is dictatorial
ProvedStrategyProofArrow.WeakGS.theorem_1_primeConsider a committee of individuals and a finite set of alternatives in which every weak order (indifference allowed) is an admissible ballot. Let be a voting procedure whose range contains alternatives (so ). If is strategy-proof, then is dictatorial: there is an individual such that
that is, is always among 's most preferred elements of the range.
This is the extension of the Gibbard–Satterthwaite theorem to ballots with indifference. Only the "only if" direction holds: a dictator's ties may be broken by a manipulable rule (for instance a Borda count of the other ballots), so a dictatorial procedure need not be strategy-proof once indifference is admissible.
Formalization Note Ballot sets are WeakProfile ι A and the procedure is a total function on them, so is Set.range v and is 3 ≤ (Set.range v).ncard; is automatic for a finite type A. Strategy-proofness compares outcomes by the strict part of the true ballot and allows any weak order as the substituted ballot. The paper defines dictatorship through a function that picks, with an unspecified tie-break, a -maximal element of ; we state the equivalent condition that is -maximal in , without fixing the tie-break. is as printed.
import Mathlib import Definitions.Def_StrategyProofArrow_WeakGS_Basic
namespace StrategyProofArrow.WeakGS
/-- **Theorem 1'** (Satterthwaite, p. 43). Consider a committee in which indifference is admissible
on ballots, with `n ≥ 2` individuals and `m ≥ p ≥ 3`, where `p` is the number of alternatives in the
range `T_p` of the voting procedure `v` over all ballot sets `π^n_m`. If `v` is strategy-proof, then
it is dictatorial. -/
theorem theorem_1_prime {ι A : Type*} [Fintype ι] [Fintype A] [DecidableEq ι]
(hn : 2 ≤ Fintype.card ι) (v : VotingProcedure ι A)
(hp : 3 ≤ (Set.range v).ncard) :
StrategyProof v → Dictatorial v := by sorry
end StrategyProofArrow.WeakGS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.