Equation (36) — the block-score bounds and
ProvedStableVotingDistortion.eq_36metric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1social-choicevoting-ruleszero-sum-games
Let , satisfy (26), be a lottery, with , and a voter. Write and . Then
and for every with ,
Differences from the source:
- generalization: §6.3.1's setting: a -stable lottery → any lottery
D ∈ stdSimplex ℝ C; reason: (36) bounds the score of a block on one rank line using only (26); a -stable lottery is a lottery, so the statement specializes to the page's - encoding: → ; reason: is a point of the rank line , on which is defined
- 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_IsScoreFunction import Definitions.Def_StableVotingDistortion_scorePrimitives import Definitions.Def_StableVotingDistortion_slices set_option autoImplicit false open PctDistortion
Formal statement
namespace StableVotingDistortion
/-- **Equation (36).** Under (26), for any lottery, `ρ ≥ 0` with `ρ(a⋆) = 0`, `t ≥ 0` and a voter `v`, with
`p = p_t` and `q = q_v(t)`: `k_v(t) ≤ δ_p(q)`, and `k_v(t) ≤ K_p(q, z)` for every `z` with `z_v(t) ≤ z ≤ 1`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), §6.3.1, Equation (36), p.29: "k_v(t) ≤ δ_p(q) = J(1 − p + q) − J(q), k_v(t) ≤ K_p(q, z) =
J(z − p + q) − J(z) − J(q). (36)"; the page's sentence before it: "in terms of p = p_t, q = q_v(t), and
z ≥ z_v(t)". -/
theorem eq_36 {V C : Type} [Fintype V] [Nonempty V] [Fintype C] [Nonempty C] (E : Election V C)
{lam : ℝ} {ϕ : ℝ → ℝ} (hϕ : IsScoreFunction lam ϕ)
{D ρ : C → ℝ} (hD : D ∈ stdSimplex ℝ C) (hρ : ∀ b, 0 ≤ ρ b) {aStar : C} (hstar : ρ aStar = 0)
{t : ℝ} (ht : 0 ≤ t) (v : V) :
kv E D ρ ϕ v t ≤ deltaP ϕ (pt D ρ t) (qv E D ρ v t) ∧
∀ z, zv E D ρ v t ≤ z → z ≤ 1 → kv E D ρ ϕ v t ≤ KP ϕ (pt D ρ t) (qv E D ρ v t) z := 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, Equation (36), p.29
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.