Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 1, (27)–(28) — a strategy-proof procedure induces a strategy-proof procedure on its range

Proved
StrategyProofArrow.Dictatorship.restriction_factor

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicestrategy-proofness

Let vnmv^{nm}vnm be a strategy-proof, strong alternative-excluding strict voting procedure for n≥1n\ge 1n≥1 individuals with range T=TpT=T_pT=Tp​, where m>p≥3m>p\ge 3m>p≥3. Then there is a strict voting procedure vnpv^{np}vnp for the ppp alternatives of TTT such that, for every strict ballot set B∈ρmnB\in\rho^n_mB∈ρmn​,

vnp[θT(B1),…,θT(Bn)]=vnm(B1,…,Bn),v^{np}\bigl[\theta_T(B_1),\dots,\theta_T(B_n)\bigr]=v^{nm}(B_1,\dots,B_n),vnp[θT​(B1​),…,θT​(Bn​)]=vnm(B1​,…,Bn​),

and vnpv^{np}vnp is strategy-proof. Here θT(Bi)\theta_T(B_i)θT​(Bi​) is the strong order on TTT obtained from BiB_iBi​ by deleting the alternatives outside TTT.

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 vnpv^{np}vnp is the subtype ↥(range f), and θT(Bi)\theta_T(B_i)θT​(Bi​) is the restriction of BiB_iBi​'s strict relation to that subtype (a strict total order again). vnpv^{np}vnp 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 m>p≥3m>p\ge 3m>p≥3. The context hypothesis n≥1n\ge 1n≥1 (Theorem 1) is kept. The paper derives the claim from Lemma 6, stated for n≥2n\ge 2n≥2; the claim itself is stated here for n≥1n\ge 1n≥1, as in Theorem 1, whose proof uses it.

Preamble
import Mathlib
import Definitions.Def_StrategyProofArrow_Dictatorship_Basic
Formal statement
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
Source
Satterthwaite, Strategy-proofness and Arrow's Conditions, Northwestern Discussion Paper No. 122 (rev. Dec. 12, 1974), §3, proof of Theorem 1, displays (27)–(28) and the following sentence, p. 27
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me