Proof of Theorem 1, (27)–(28) — a strategy-proof procedure induces a strategy-proof procedure on its range
ProvedStrategyProofArrow.Dictatorship.restriction_factorLet be a strategy-proof, strong alternative-excluding strict voting procedure for individuals with range , where . Then there is a strict voting procedure for the alternatives of such that, for every strict ballot set ,
and is strategy-proof. Here is the strong order on obtained from by deleting the alternatives outside .
This is displays (27)–(28) of the proof of Theorem 1 and the sentence following them: it reduces a procedure with a proper range to one whose range is its whole alternative set, to which the full-range case of Lemma 5 applies.
Formalization Note The alternative set of is the subtype ↥(range f), and is the restriction of 's strict relation to that subtype (a strict total order again). is a function on all relation profiles over the subtype; the identity is required at restrictions of strict ballot sets, and strategy-proofness quantifies over strict ballot sets on the subtype. The hypotheses include the proof's case assumptions: strong alternative exclusion and . The context hypothesis (Theorem 1) is kept. The paper derives the claim from Lemma 6, stated for ; the claim itself is stated here for , as in Theorem 1, whose proof uses it.
import Mathlib import Definitions.Def_StrategyProofArrow_Dictatorship_Basic
namespace StrategyProofArrow.Dictatorship
open AGT
/-- **Proof of Theorem 1, (27)–(28)** (Satterthwaite, p. 27). In the proof's case of a
strategy-proof, strong alternative-excluding strict voting procedure `f` with a proper range
`T = T_p` of at least three alternatives, `f` factors through the restriction of ballots to `T`:
there is a
strict voting procedure `g` for the alternative set `T` (a subtype) with
`g(θ_T(B_1), …, θ_T(B_n)) = f(B)` for every strict ballot set `B`, and `g` is strategy-proof. -/
theorem restriction_factor {ι A : Type*} [Fintype ι] [Fintype A] [DecidableEq ι]
(hn : 1 ≤ Fintype.card ι)
(f : (ι → A → A → Prop) → A) (hsp : IncentiveCompatible f)
(hstrong : StrongAltExcluding f)
(hp : 3 ≤ (range f).ncard)
(hproper : (range f).ncard < Fintype.card A) :
∃ g : (ι → range f → range f → Prop) → range f,
(∀ P : ι → A → A → Prop, IsPrefProfile P →
((g (fun i (x y : range f) => P i x y) : A) = f P)) ∧
IncentiveCompatible g := by sorry
end StrategyProofArrow.Dictatorship
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.