Theorem 5 — biased metrics are necessary and sufficient, for a fixed and
ProvedStableVotingDistortion.theorem_5metric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicevoting-ruleszero-sum-games
Let be an election, a lottery, a candidate and . Then
if and only if, for all with ,
This reduces the supremum over consistent metrics to a family described by .
Differences from the source:
- reading: an optimal candidate, and of unstated range →
aStaris a fixed arbitrary candidate on both sides, and0 ≤ lam; reason: quantifying over gives the printed use; is required, since with one candidate, one voter at distance and , (11) holds while the bound fails - encoding: →
ρ : C → ℝwith∀ c, 0 ≤ ρ c; reason: the same functions - 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: 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_IsPseudometric import Definitions.Def_StableVotingDistortion_voterMean import Definitions.Def_StableVotingDistortion_HasDistortionAtMost import Definitions.Def_StableVotingDistortion_rhoV set_option autoImplicit false open PctDistortion
Formal statement
namespace StableVotingDistortion
/-- **Theorem 5 (biased metrics are necessary and sufficient).** For a lottery `D`, a candidate `a⋆` and
`λ ≥ 0`: `E_{b∼D}[cost(b)] ≤ (1 + 2λ) cost(a⋆)` for all consistent metrics if and only if, for all
`ρ : C → ℝ≥0` with `ρ(a⋆) = 0`, `E_v[L_v(D)] ≤ λ E_v[R_v]`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), Theorem 5, p.13: "For a distribution D over candidates, E_{b∼D}[cost(b)] ≤ (1 + 2λ)cost(a⋆) for
all consistent metrics if and only if for all ρ : C → R≥0 such that ρ(a⋆) = 0, we have
E_{v∼V}[L_v(D)] ≤ λ E_{v∼V}[R_v]. (11)"
**Formalization Note.** `a⋆` is fixed on both sides, and quantifying over it gives the form used for an
optimal candidate. The page leaves the range of `λ` open. `λ ≥ 0` is required: with one candidate, one
voter at distance `1` and `λ < 0`, (11) holds while `1 ≤ 1 + 2λ` fails. -/
theorem theorem_5 {V C : Type} [Fintype V] [Nonempty V] [Fintype C] [Nonempty C] (E : Election V C)
{D : C → ℝ} (hD : D ∈ stdSimplex ℝ C) (aStar : C) {lam : ℝ} (hlam : 0 ≤ lam) :
(∀ d : V ⊕ C → V ⊕ C → ℝ, IsPseudometric d → Consistent E d →
lotteryCost d D ≤ (1 + 2 * lam) * candCost d aStar) ↔
∀ ρ : C → ℝ, (∀ c, 0 ≤ ρ c) → ρ aStar = 0 →
voterMean (fun v => Lv E D ρ v) ≤ lam * voterMean (fun v => Rv E ρ 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…), Theorem 5, p.13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.