Equations (30)–(31) — the two consequences of stability
ProvedStableVotingDistortion.eq_30_31metric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1social-choicevoting-ruleszero-sum-games
Let , let satisfy (26), and let be a -stable lottery. Then every set of candidates has expected score zero across voters,
in particular ; and for the left endpoint of any candidate's interval,
Differences from the source:
- generalization: for the slice → the same for every
S : Finset C; reason: is the instanceSt ρ t, and the page's argument is linearity over candidates - generalization: the left endpoint of 's interval → the left endpoint of any candidate's interval; reason: is an instance; nothing in (31) uses its optimality
- encoding: → a function
ℝ → ℝ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_IsGStable import Definitions.Def_StableVotingDistortion_IsScoreFunction import Definitions.Def_StableVotingDistortion_scorePrimitives import Definitions.Def_StableVotingDistortion_slices set_option autoImplicit false open PctDistortion
Formal statement
namespace StableVotingDistortion
/-- **Equations (30)–(31).** For a `g_ϕ`-stable lottery under (26): every set `S` of candidates has
`E_v[score of S on v's rank line] = 0`, and for `s_v` the left boundary of any candidate,
`E_v[ϕ(s_v)] ≥ 0`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), §6.3.1, Equations (30), (31), p.28: "linearity of expectation shows that the total score k_v(t) of S_t
on v's rank line satisfies E_v[k_v(t)] = 0. (30) Second, since ϕ is nonincreasing, its value at the left
endpoint s_v of a⋆'s interval is at least its average over that interval; as a⋆ has expected score at most
zero (Theorem 4), this gives E_v[ϕ(s_v)] ≥ 0. (31)"
**Formalization Note.** (30) is stated for every subset of `C`; `S_t` is the instance `St ρ t`, and
`blockScore E D ϕ v (St ρ t)` is `kv E D ρ ϕ v t` by definition. -/
theorem eq_30_31 {V C : Type} [Fintype V] [Nonempty V] [Fintype C] [Nonempty C] (E : Election V C)
{lam : ℝ} {ϕ : ℝ → ℝ} (hϕ : IsScoreFunction lam ϕ) {D : C → ℝ} (hD : IsGStable (gPhi ϕ) E D) :
(∀ S : Finset C, voterMean (fun v => blockScore E D ϕ v S) = 0) ∧
∀ a : C, 0 ≤ voterMean (fun v => ϕ (sv E D a v)) := 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…), §6.3.1, Equations (30), (31), p.28
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.