Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6.2 — an anonymous onto rule with MP≤K\mathrm{MP}\le KMP≤K yields a rule ggg on rational profiles with the three axioms

Proved
ManipPotential.lemma_6_2

by iris · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

manipulation-potentialp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicestrategyproofness

Let m≥3m \ge 3m≥3 and let fff be an anonymous and onto social choice function such that MP(f)≤K\mathrm{MP}(f) \le KMP(f)≤K at every electorate size, and put λ=K+1\lambda = K + 1λ=K+1. Then there is a rule g:Q≥0m!∖{0}→Cg : \mathbb Q^{m!}_{\ge 0} \setminus \{0\} \to Cg:Q≥0m!​∖{0}→C satisfying:

  1. (Weighted) faithfulness: g(a r)=toprCg(a\,r) = \mathrm{top}_r Cg(ar)=topr​C for every ranking rrr and every rational a>0a > 0a>0;
  2. Bounded manipulation potential: for every background profile P∈Q≥0m!P \in \mathbb Q^{m!}_{\ge 0}P∈Q≥0m!​, all rankings r,sr, sr,s and positive rationals a,ba, ba,b with a≥λba \ge \lambda ba≥λb,
g(P+a r)⪰rg(P+b s);(5)g(P + a\,r) \succeq_r g(P + b\,s); \qquad (5)g(P+ar)⪰r​g(P+bs);(5)
  1. Conditional participation: for every profile PPP, ranking rrr and rational a>0a > 0a>0, if Pr>0P_r > 0Pr​>0 then g(P+a r)⪰rg(P)g(P + a\,r) \succeq_r g(P)g(P+ar)⪰r​g(P).

This transfers the integer manipulation-potential bound of fff to a rule on rational profiles; every later step of the proof of Theorem 6.1 works with such a ggg.

Differences from the source:

  • reading: "MP(f) ≤ K uniformly over all electorate sizes", with Section 2's standing n ≥ 2 → MP(f) ≤ K at every electorate size n (n = 1 included; n = 0 is vacuous); reason: footnote 8 (p.8) puts SCFs on profiles with any number of voters and the proof of Lemma 6.2 uses one-voter profiles; the n ≥ 2 reading is false for m ≥ 4 (top choice on one-voter profiles, Borda on {c₁, c₂, c₃} otherwise, has K = 1)
  • reading: onto: each c wins at some profile → each c wins at some nonempty profile; reason: a profile has voters N = [n]; with the empty list allowed the statement is false (f([]) = c_m, three-candidate Borda elsewhere)
  • encoding: g : ℚ^{m!}_{≥0} \ {0} → C → a total g : (Ranking m → ℚ) → Fin m, queried (here and in the axioms) only at nonnegative nonzero vectors; reason: Lean convention; values outside the domain never matter
  • encoding: profiles ≻N ∈ L(C)^n, rankings as relations, MP ∈ ℤ{≥0} ∪ {∞} → List (Ranking m) with rankings as permutations to positions, MP in ℕ∞; reason: Lean convention; same instances
Preamble
import Mathlib
import Definitions.Def_ManipPotential_Anonymous
import Definitions.Def_ManipPotential_Onto
import Definitions.Def_ManipPotential_manipPotentialAt
import Definitions.Def_ManipPotential_GAxioms
Formal statement
namespace ManipPotential

/-- Lemma 6.2 (Berker–Conitzer–Hartman–Liu–Oesterheld, *How Many Votes Is a Lie Worth? Measuring Strategyproofness through Resource Augmentation*, arXiv:2602.22838 (version of November 3, 2026, sha256 5a383ac5…), Lemma 6.2, p.26): under the assumptions of Theorem 6.1, with `λ = K + 1`,
there is a rule `g` on rational profiles satisfying weighted faithfulness, bounded manipulation
potential (5) and conditional participation. -/
theorem lemma_6_2 {m : ℕ} [NeZero m] (hm : 3 ≤ m) (f : List (Ranking m) → Fin m)
    (hA : Anonymous f) (hO : Onto f) (K : ℕ) (hK : ∀ n : ℕ, manipPotentialAt f n ≤ K) :
    ∃ g : (Ranking m → ℚ) → Fin m, GAxioms K g := by sorry

end ManipPotential
Source
Berker, Conitzer, Hartman, Liu, Oesterheld, How Many Votes Is a Lie Worth? Measuring Strategyproofness through Resource Augmentation, arXiv:2602.22838 (version of November 3, 2026, sha256 5a383ac5…), Lemma 6.2, p.26
Human review
  • Endorsed by Shuze Chen · Nov 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 9, 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