Proposition 3 — stationarity of -stable lotteries, in multiplicative form
ProvedStableVotingDistortion.proposition_3metric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicevoting-ruleszero-sum-games
Let be as in Definition 3, an election, and a -stable lottery. For every candidate ,
Equivalently, when : sampling a voter uniformly and a rank with density proportional to , and outputting the candidate occupying that rank, reproduces .
Differences from the source:
- encoding: the sampled candidate has distribution , for a rank with density proportional to → for every ; reason: this is the printed proof's display for ; a density proportional to is undefined for , which Definition 3 allows, and there both sides are
- 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_leftRank import Definitions.Def_StableVotingDistortion_IsGStable set_option autoImplicit false open PctDistortion
Formal statement
namespace StableVotingDistortion
/-- **Proposition 3 (stationarity).** For a `g`-stable lottery `D` and every candidate `a`,
`(∫_0^1 g) · D(a) = E_v[∫_{rank_v(a)}^{rank_v(a) + D(a)} g]`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), Proposition 3, p.11: "Given a g-stable lottery D_g, define a distribution D̂ as follows. Sample a
voter v ∼ V uniformly and a rank r ∼ [0, 1] with density proportional to g(r), and output the candidate
occupying rank r. Then D̂ = D_g."
**Formalization Note.** The right side is `(∫ g) · D̂(a)` by the display in the printed proof, so the
statement is `D̂ = D` when `∫ g > 0`. It is stated multiplicatively because "density proportional to g"
is undefined for `g ≡ 0`, which Definition 3 allows; there both sides are `0`. -/
theorem proposition_3 {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) :
(∫ t in (0 : ℝ)..1, g t) * D a =
voterMean (fun v => ∫ r in (leftRank E D v a)..(leftRank E D v a + D a), g r) := 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…), Proposition 3, p.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.