Theorem 4 — a -stable lottery gives every candidate expected activation at most
ProvedStableVotingDistortion.theorem_4metric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicevoting-ruleszero-sum-games
Let be continuous and non-decreasing, let be an election and a -stable lottery. Then for every candidate ,
This is the guarantee stability gives against an attacker, including candidates outside the lottery's support.
Differences from the source:
- reading: , with overloaded on p.8 →
activation: the average of over 's interval if , and at the left boundary if ; reason: p.8 makes the attacker's rank a uniformly random point of its interval, p.22 gives the zero-mass value, and the proof of Theorem 4 needs a uniformly random rank under - encoding: solves →
IsGStable: instdSimplex ℝ Cminimizes over lotteries; reason: p.11: the maximum over of a linear objective equals - encoding: → a function
ℝ → ℝwithIsActivation g, constrained only on[0, 1]; reason: Lean functions are total; every printed argument lies in - encoding: voters and a finite set →
[Fintype V] [Nonempty V] [Fintype C] [Nonempty C], withV C : Type; reason: an expectation over voters and a lottery over candidates need both nonempty
Preamble
import Mathlib import Definitions.Def_PctDistortion_Election import Definitions.Def_StableVotingDistortion_voterMean import Definitions.Def_StableVotingDistortion_activation import Definitions.Def_StableVotingDistortion_IsGStable set_option autoImplicit false open PctDistortion
Formal statement
namespace StableVotingDistortion
/-- **Theorem 4.** In any election, a `g`-stable lottery gives every candidate expected activation at most
`∫_0^1 g`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), Theorem 4, p.10: "In any election with g-stable lottery D_g, we have
E_{v∼V}[g(rank_v(a; D_g))] ≤ ∫_0^1 g(t) dt. (10) for all candidates a."
**Formalization Note.** `g(rank_v(a; D))` is the attacker's random-copy rank, `activation`. -/
theorem theorem_4 {V C : Type} [Fintype V] [Nonempty V] [Fintype C] [Nonempty C] {g : ℝ → ℝ}
(hg : IsActivation g) (E : Election V C) {D : C → ℝ} (hD : IsGStable g E D) (a : C) :
voterMean (fun v => activation g E D v a) ≤ ∫ t in (0 : ℝ)..1, g t := by sorry
end StableVotingDistortion
Source
Cai, Frank, Hastings, Ramakrishnan, Wang, Ye, Stable Voting Rules on the Edge of Optimal Metric Distortion, arXiv:2609.08259 (held version, sha256 cfdd5f3d…), Theorem 4, p.10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.