Lemma 14(i) — small masses: (37), (38) for with
ProvedStableVotingDistortion.lemma_14_imetric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicevoting-ruleszero-sum-games
Let , let satisfy (26) with nonincreasing on , and let . Let satisfy
Then (37) and (38) hold for every with and .
Differences from the source:
- reading: " satisfy the hypotheses of Lemma 8", and → the hypotheses on only, and ; reason: and are what the lemma produces, and plays no part in (i)
- encoding: → a function
ℝ → ℝconstrained only on[0, 1]; reason: Lean functions are total; every printed argument lies in
Preamble
import Mathlib import Definitions.Def_StableVotingDistortion_IsScoreFunction import Definitions.Def_StableVotingDistortion_scorePrimitives import Definitions.Def_StableVotingDistortion_VerifierHypotheses set_option autoImplicit false
Formal statement
namespace StableVotingDistortion
/-- **Lemma 14(i) (small masses).** Let `ϕ` satisfy (26) with `ϕ(r) + r` nonincreasing on `[λ, 1]`, and let
`0 < p₀ < λ`. If `β₀ > 0` satisfies (45), then (37) and (38) hold for every `p ∈ (0, p₀]` with `β(p) = β₀` and
`c(p, x) = ((1 + β₀ p) ϕ(x) − (λ − x))₊`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), Lemma 14(i), p.44: "Let ϕ satisfy the hypotheses of Lemma 8, and let 0 < p_0 < λ < p_1 < 1. (i) Let
β_0 > 0 satisfy β_0 ϕ(p_0) ≥ 1, p_0 (1 + β_0(1 + ϕ(0))) ≤ λ, p_0 [1 − β_0 (ϕ(p_0) − ϕ(x))] ≤ σ(x) for 0 ≤ x ≤ λ.
(45) Then Equations (37) and (38) hold for every p ∈ (0, p_0] with β(p) = β_0 and
c(p, x) = ((1 + β_0 p)ϕ(x) − (λ − x))_+."
**Formalization Note.** "The hypotheses of Lemma 8" are those on `ϕ`: `β` and `c` are what this lemma
produces. `p₁` of the page's opening sentence plays no part in (i) and is not a binder. -/
theorem lemma_14_i {lam : ℝ} {ϕ : ℝ → ℝ} (hϕ : IsScoreFunction lam ϕ)
(hadd : AntitoneOn (fun r => ϕ r + r) (Set.Icc lam 1))
{p0 : ℝ} (hp0 : 0 < p0) (hp0lam : p0 < lam) {β0 : ℝ} (hβ0 : 0 < β0)
(h45a : 1 ≤ β0 * ϕ p0) (h45b : p0 * (1 + β0 * (1 + ϕ 0)) ≤ lam)
(h45c : ∀ x ∈ Set.Icc 0 lam, p0 * (1 - β0 * (ϕ p0 - ϕ x)) ≤ sigma lam ϕ x) :
∀ p ∈ Set.Ioc 0 p0,
Eq37 lam ϕ (fun _ => β0) (fun p x => max ((1 + β0 * p) * ϕ x - (lam - x)) 0) p ∧
Eq38 lam ϕ (fun _ => β0) (fun p x => max ((1 + β0 * p) * ϕ x - (lam - x)) 0) p := 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 14(i), p.44
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.