Lemma 3 — voters 1, …, n cannot manipulate an (n+1)-voter procedure iff all its sections are strategy-proof
ProvedStrategyProofArrow.Dictatorship.lemma_3Consider a strict committee with and . Write a ballot set as with . For each strict ballot of individual , the section is a strict voting procedure for the first individuals; for three alternatives there are six of them, display (6). Then
Individual is excluded from the left-hand side; including them would make the right-to-left direction false, since a family of strategy-proof sections can still be manipulated by individual . The lemma is the device by which the induction on passes from to individuals.
Formalization Note The individuals are Option ι, with none the individual and some i the individual ; the section for ballot is sectionAt f b. The six sections of display (6) are the sections for the six strict orders on three alternatives, quantified as "every strict total order ". The paper prints the ballot set as ; since the committee is strict this is read as , and it prints for . The hypotheses and are kept as printed although the equivalence does not need them.
import Mathlib import Definitions.Def_StrategyProofArrow_Dictatorship_Basic
namespace StrategyProofArrow.Dictatorship
open AGT
/-- **Lemma 3** (Satterthwaite, pp. 16–17). Let the committee have `n + 1` individuals, encoded as
`Option ι` with `none` the individual `n + 1`, three alternatives, `n ≥ 1` and `1 ≤ p ≤ 3`. No
individual `i ∈ I_n` (individual `n + 1` excluded) can manipulate `f` at any strict ballot set if
and only if every section `sectionAt f b` (voter `n + 1` casting the strict ballot `b`) is a
strategy-proof strict voting procedure for the `n` remaining individuals. -/
theorem lemma_3 {ι A : Type*} [Fintype ι] [Fintype A] [DecidableEq ι]
(hn : 1 ≤ Fintype.card ι) (hm : Fintype.card A = 3)
(f : (Option ι → A → A → Prop) → A) (hp : 1 ≤ (range f).ncard) :
(∀ P : Option ι → A → A → Prop, IsPrefProfile P →
∀ (i : ι) (r' : A → A → Prop), IsStrictTotalOrder A r' →
¬ P (some i) (f (Function.update P (some i) r')) (f P)) ↔
∀ b : A → A → Prop, IsStrictTotalOrder A b → IncentiveCompatible (sectionAt f b) := by sorry
end StrategyProofArrow.Dictatorship
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.