Equation (27) — the layer-cake identity and
ProvedStableVotingDistortion.eq_27metric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1social-choicevoting-ruleszero-sum-games
Let be a lottery, with , and a voter. Then is integrable on ,
and for every ,
Differences from the source:
- generalization: §6.3.1's setting: a -stable lottery, satisfying (26) → any lottery
D ∈ stdSimplex ℝ C, no ; reason: (27) is a layer-cake identity and an ordering fact on one rank line; neither stability nor enters; a -stable lottery is a lottery, so the statement specializes to the page's - encoding: → also
IntegrableOnof onSet.Ioi 0; reason: a Bochner integral of a non-integrable function is , so the identity needs integrability to say what the page says; is bounded and vanishes for large - encoding: →
ρ : C → ℝwith∀ c, 0 ≤ ρ c; reason: the same functions - 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_rhoV import Definitions.Def_StableVotingDistortion_slices set_option autoImplicit false open PctDistortion
Formal statement
namespace StableVotingDistortion
/-- **Equation (27).** For any lottery `D`, `ρ ≥ 0` with `ρ(a⋆) = 0` and any voter `v`:
`∫_0^∞ q_v(t) dt = L_v`, and for every `t ≥ 0`, `z_v(t + R_v) ≤ q_v(t)` and `q_v(t) ≤ s_v`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), §6.3.1, Equation (27), p.27: "Since ρ(a⋆) = 0, we have a⋆ ∉ S_t, and therefore q_v(t) ≤ s_v for all
t ≥ 0. Observe that q_v(t) and z_v(t) satisfy ∫_0^∞ q_v(t) dt = L_v, z_v(t + R_v) ≤ q_v(t). (27)"
**Formalization Note.** Integrability of `q_v` on `(0, ∞)` is part of the conclusion, since a Bochner
integral of a non-integrable function would be `0`. -/
theorem eq_27 {V C : Type} [Fintype V] [Nonempty V] [Fintype C] [Nonempty C] (E : Election V C)
{D ρ : C → ℝ} (hD : D ∈ stdSimplex ℝ C) (hρ : ∀ c, 0 ≤ ρ c) {aStar : C} (hstar : ρ aStar = 0)
(v : V) :
MeasureTheory.IntegrableOn (qv E D ρ v) (Set.Ioi 0) ∧
∫ t in Set.Ioi (0 : ℝ), qv E D ρ v t = Lv E D ρ v ∧
(∀ t, 0 ≤ t → zv E D ρ v (t + Rv E ρ v) ≤ qv E D ρ v t) ∧
∀ t, 0 ≤ t → qv E D ρ v t ≤ sv E D aStar 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, Equation (27), p.27
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.