Lemma 4 — the induction step on the number of voters for three alternatives
ProvedStrategyProofArrow.Dictatorship.lemma_4dictatorshipp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicestrategy-proofness
Consider strict committees with three alternatives and . Suppose every strategy-proof strict voting procedure for the individuals is fully dictatorial or strong alternative-excluding. Then every strict voting procedure for the individuals , with range of elements, satisfies
With Lemma 2 as base case, this yields Lemma 5 for by induction on .
Formalization Note The individuals are ι with Fintype.card ι ≥ 1, and is Option ι. The induction hypothesis quantifies over all strict voting procedures for ι on the same three-element alternative set A. holds automatically.
Preamble
import Mathlib import Definitions.Def_StrategyProofArrow_Dictatorship_Basic
Formal statement
namespace StrategyProofArrow.Dictatorship
open AGT
/-- **Lemma 4** (Satterthwaite, p. 22). Three alternatives, `n ≥ 1`. If every strategy-proof
strict voting procedure for the `n` individuals `ι` is fully dictatorial or strong
alternative-excluding, then every strategy-proof strict voting procedure for the `n + 1`
individuals `Option ι` with `1 ≤ p ≤ 3` is fully dictatorial or strong alternative-excluding. -/
theorem lemma_4 {ι A : Type*} [Fintype ι] [Fintype A] [DecidableEq ι]
(hn : 1 ≤ Fintype.card ι) (hm : Fintype.card A = 3)
(hind : ∀ g : (ι → A → A → Prop) → A, IncentiveCompatible g →
FullyDictatorial g ∨ StrongAltExcluding g)
(f : (Option ι → 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 4, p. 22
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.