Lemma 6 — the choice of a strategy-proof procedure depends only on the ballots' rankings of its range
ProvedStrategyProofArrow.Dictatorship.lemma_6p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicestrategy-proofness
Consider a strict committee with , , and . If is strategy-proof and two strict ballot sets satisfy for every , that is, each and rank the elements of in the same order, then
This is an "independence of irrelevant alternatives" property: alternatives outside the range do not influence the choice. It lets a strategy-proof procedure be viewed as a procedure on the alternatives of its range alone.
Formalization Note is AgreeOn (range f) (C i) (D i): the strict parts of and agree on . The paper states ; the hypothesis is kept as printed. holds automatically (the range is a subset of the alternatives) and is not stated.
Preamble
import Mathlib import Definitions.Def_StrategyProofArrow_Dictatorship_Basic
Formal statement
namespace StrategyProofArrow.Dictatorship
open AGT
/-- **Lemma 6** (Satterthwaite, p. 26). For a strict committee with `n ≥ 2`, `m ≥ 3` and
`p ≥ 1` (`m ≥ p` holds automatically), if `f` is strategy-proof and the strict ballot sets `C`,
`D` satisfy `θ_T(C_i) = θ_T(D_i)` for every individual `i`, where `T = T_p` is the range, then
`f C = f D`. -/
theorem lemma_6 {ι A : Type*} [Fintype ι] [Fintype A] [DecidableEq ι]
(hn : 2 ≤ Fintype.card ι) (hm : 3 ≤ Fintype.card A)
(f : (ι → A → A → Prop) → A) (hp : 1 ≤ (range f).ncard)
(hsp : IncentiveCompatible f)
(C D : ι → A → A → Prop) (hC : IsPrefProfile C) (hD : IsPrefProfile D)
(hCD : ∀ i, AgreeOn (range f) (C i) (D i)) :
f C = f D := by sorry
end StrategyProofArrow.Dictatorship
Source
Satterthwaite, Strategy-proofness and Arrow's Conditions, Northwestern Discussion Paper No. 122 (rev. Dec. 12, 1974), Lemma 6, p. 26
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.