Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3 — voters 1, …, n cannot manipulate an (n+1)-voter procedure iff all its sections are strategy-proof

Proved
StrategyProofArrow.Dictatorship.lemma_3

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

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

Consider a strict committee ⟨In+1,S3,vn+1,3,Tp⟩\langle I_{n+1},S_3,v^{n+1,3},T_p\rangle⟨In+1​,S3​,vn+1,3,Tp​⟩ with n≥1n\ge 1n≥1 and 1≤p≤31\le p\le 31≤p≤3. Write a ballot set as (B,Bn+1)(B,B_{n+1})(B,Bn+1​) with B=(B1,…,Bn)B=(B_1,\dots,B_n)B=(B1​,…,Bn​). For each strict ballot bbb of individual n+1n+1n+1, the section vbn,3(B)=vn+1,3(B,b)v^{n,3}_b(B)=v^{n+1,3}(B,b)vbn,3​(B)=vn+1,3(B,b) is a strict voting procedure for the first nnn individuals; for three alternatives there are six of them, display (6). Then

(no i∈In can manipulate vn+1,3 at any (B,Bn+1)∈ρ3n+1)  ⟺  (every section vbn,3 is strategy-proof).\Bigl(\text{no } i\in I_n \text{ can manipulate } v^{n+1,3} \text{ at any } (B,B_{n+1})\in\rho^{n+1}_3\Bigr)\iff \Bigl(\text{every section } v^{n,3}_b \text{ is strategy-proof}\Bigr).(no i∈In​ can manipulate vn+1,3 at any (B,Bn+1​)∈ρ3n+1​)⟺(every section vbn,3​ is strategy-proof).

Individual n+1n+1n+1 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 n+1n+1n+1. The lemma is the device by which the induction on nnn passes from nnn to n+1n+1n+1 individuals.

Formalization Note The n+1n+1n+1 individuals are Option ι, with none the individual n+1n+1n+1 and some i the individual i∈Ini\in I_ni∈In​; the section for ballot bbb 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 bbb". The paper prints the ballot set as (B,Bn+1)∈πmn+1(B,B_{n+1})\in\pi^{n+1}_m(B,Bn+1​)∈πmn+1​; since the committee is strict this is read as ρ3n+1\rho^{n+1}_3ρ3n+1​, and it prints v1n,…,v6nv^n_1,\dots,v^n_6v1n​,…,v6n​ for v1n,3,…,v6n,3v^{n,3}_1,\dots,v^{n,3}_6v1n,3​,…,v6n,3​. The hypotheses n≥1n\ge 1n≥1 and p≥1p\ge 1p≥1 are kept as printed although the equivalence does not need them.

Preamble
import Mathlib
import Definitions.Def_StrategyProofArrow_Dictatorship_Basic
Formal statement
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
Source
Satterthwaite, Strategy-proofness and Arrow's Conditions, Northwestern Discussion Paper No. 122 (rev. Dec. 12, 1974), Lemma 3 and display (6), pp. 16–17
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