Theorem 1 — a continuous activation exists for which every -stable lottery has distortion at most
ProvedStableVotingDistortion.theorem_1metric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicevoting-ruleszero-sum-games
There exists a continuous, non-decreasing function with and such that in any election a -stable lottery exists, and every -stable lottery satisfies, for every pseudometric consistent with and every candidate ,
The function is chosen once, before the election. The lower bound for any randomized voting rule is , so this comes within of it.
Differences from the source:
- reading: p.11: "every -stable lottery has distortion at most 2.1248"; p.3: "There is a randomized voting rule with distortion at most 2.1248" → also
∃ D, IsGStable g E Dfor each election; reason: the bound alone would be vacuous on an election with no -stable lottery; p.4 states existence, and with it the p.3 form follows - 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
ℝ → ℝ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_HasDistortionAtMost import Definitions.Def_StableVotingDistortion_IsGStable set_option autoImplicit false open PctDistortion
Formal statement
namespace StableVotingDistortion
/-- **Theorem 1.** There exists a continuous, non-decreasing `g : [0, 1] → [0, 1]` with `g(0) = 0`, `g(1) = 1`
such that in any election a `g`-stable lottery exists, and every `g`-stable lottery has distortion at most
`2.1248`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), Theorem 1, p.11: "There exists a continuous, non-decreasing function g : [0, 1] → [0, 1] with
g(0) = 0, g(1) = 1, such that in any election, every g-stable lottery has distortion at most 2.1248."; p.3:
"There is a randomized voting rule with distortion at most 2.1248."
**Formalization Note.** `g` is chosen once, before the election. The existence clause keeps "every `g`-stable
lottery" from being vacuous, and with it the p.3 form follows. Distortion is the inequality
`HasDistortionAtMost`, so a zero optimum is not excluded. -/
theorem theorem_1 :
∃ g : ℝ → ℝ, IsActivation g ∧ g 0 = 0 ∧ g 1 = 1 ∧
∀ (V C : Type) [Fintype V] [Nonempty V] [Fintype C] [Nonempty C] (E : Election V C),
(∃ D : C → ℝ, IsGStable g E D) ∧
∀ D : C → ℝ, IsGStable g E D → HasDistortionAtMost E D 2.1248 := 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 1, p.11; also p.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.