Lemma 6.2 — an anonymous onto rule with yields a rule on rational profiles with the three axioms
ProvedManipPotential.lemma_6_2manipulation-potentialp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicestrategyproofness
Let and let be an anonymous and onto social choice function such that at every electorate size, and put . Then there is a rule satisfying:
- (Weighted) faithfulness: for every ranking and every rational ;
- Bounded manipulation potential: for every background profile , all rankings and positive rationals with ,
- Conditional participation: for every profile , ranking and rational , if then .
This transfers the integer manipulation-potential bound of to a rule on rational profiles; every later step of the proof of Theorem 6.1 works with such a .
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.