Lemma 8 (Verifier Lemma) — satisfying (26), (37), (38) give distortion at most
ProvedStableVotingDistortion.lemma_8metric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicevoting-ruleszero-sum-games
Let , let satisfy (26) with nonincreasing on , and let and satisfy (37) and (38) for every and . Then in any election, every -stable lottery has distortion at most .
The hypotheses mention no election, which makes this a checkable analytic criterion.
Differences from the source:
- reading: distortion at most , as the ratio →
HasDistortionAtMost: for all consistent and all candidates ; reason: the same for a positive minimum; it avoids division by zero, and with a zero minimum it forces - 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 pseudometric on →
d : V ⊕ C → V ⊕ C → ℝwithIsPseudometric; reason: a sum type tags voters and candidates; a voter and a candidate may be at distance - encoding: → a function
ℝ → ℝconstrained only on[0, 1]; reason: Lean functions are total; every printed argument lies in - encoding: , → total functions constrained only on those domains; reason: Lean functions are total; only printed arguments are used
- 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_HasDistortionAtMost import Definitions.Def_StableVotingDistortion_IsGStable import Definitions.Def_StableVotingDistortion_scorePrimitives import Definitions.Def_StableVotingDistortion_VerifierHypotheses set_option autoImplicit false open PctDistortion
Formal statement
namespace StableVotingDistortion
/-- **Lemma 8 (Verifier Lemma).** If `λ, ϕ, β, c` satisfy the hypotheses of the lemma, then in any election
every `g_ϕ`-stable lottery has distortion at most `1 + 2λ`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), Lemma 8, p.31: "Let ϕ satisfy Equation (26) and let ϕ(r) + r be nonincreasing on [λ, 1]. Let
β : (0, 1) → R≥0 and c : (0, 1) × [0, λ) → R≥0 satisfy Equations (37) and (38) for every p ∈ (0, 1) and
x ∈ [0, λ). Then every g_ϕ-stable lottery has distortion at most 1 + 2λ." -/
theorem lemma_8 {lam : ℝ} {ϕ β : ℝ → ℝ} {c : ℝ → ℝ → ℝ} (h : VerifierHypotheses lam ϕ β c)
{V C : Type} [Fintype V] [Nonempty V] [Fintype C] [Nonempty C] (E : Election V C) {D : C → ℝ}
(hD : IsGStable (gPhi ϕ) E D) : HasDistortionAtMost E D (1 + 2 * lam) := 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…), Lemma 8, p.31
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.