Lemma 5 — a strategy-proof strict voting procedure is fully dictatorial or strong alternative-excluding
ProvedStrategyProofArrow.Dictatorship.lemma_5dictatorshipp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicestrategy-proofness
Consider a strict committee with , and . If is strategy-proof, then
When the range is all of this is the classical Gibbard–Satterthwaite theorem; when the range is a proper subset, it asserts Condition U. The paper proves the case (Lemmas 2–4) and refers to its reference [13] for the induction on .
Formalization Note The case is the published theorem AGT.gibbard_satterthwaite (an incentive compatible social choice function onto more than two alternatives has a voter whose unique top alternative is always elected), included in this mission as a reference item.
Preamble
import Mathlib import Definitions.Def_StrategyProofArrow_Dictatorship_Basic
Formal statement
namespace StrategyProofArrow.Dictatorship
open AGT
/-- **Lemma 5** (Satterthwaite, p. 25). For a strict committee with `n ≥ 1`, `m ≥ 3` and
`p ≥ 1`, a strategy-proof strict voting procedure is either fully dictatorial or strong
alternative-excluding. -/
theorem lemma_5 {ι A : Type*} [Fintype ι] [Fintype A] [DecidableEq ι]
(hn : 1 ≤ Fintype.card ι) (hm : 3 ≤ Fintype.card A)
(f : (ι → A → A → Prop) → A) (hp : 1 ≤ (range f).ncard)
(hsp : IncentiveCompatible f) :
FullyDictatorial f ∨ StrongAltExcluding f := by sorry
end StrategyProofArrow.Dictatorship
Source
Satterthwaite, Strategy-proofness and Arrow's Conditions, Northwestern Discussion Paper No. 122 (rev. Dec. 12, 1974), Lemma 5, p. 25
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.