Lemma 9 (Upper Bound) — functions exist satisfying the Verifier Lemma with
ProvedStableVotingDistortion.lemma_9metric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicevoting-ruleszero-sum-games
There exist , , and satisfying the hypotheses of the Verifier Lemma (Lemma 8) with
This makes the Verifier Lemma's hypotheses nonvacuous at the value of needed for the main theorem.
Differences from the source:
- reading: "the functions , , and recorded in checker/certificate.json" → an existential over ; reason: the certificate is outside the paper, and the existential is all the proof of Theorem 1 uses
- encoding: → a function
ℝ → ℝconstrained only on[0, 1]; reason: Lean functions are total; every printed argument lies in - encoding: , → total functions constrained only on those domains; reason: Lean functions are total; only printed arguments are used
Preamble
import Mathlib import Definitions.Def_StableVotingDistortion_VerifierHypotheses set_option autoImplicit false
Formal statement
namespace StableVotingDistortion
/-- **Lemma 9 (Upper Bound).** There are `λ, ϕ, β, c` satisfying the hypotheses of Lemma 8 with
`1 + 2λ ≤ 2.1248`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), Lemma 9, p.31: "The functions ϕ⋆, β, and c recorded in checker/certificate.json satisfy the
hypotheses of Lemma 8, with 1 + 2λ ≤ 2.1248."
**Formalization Note.** The certificate is not in the paper, so the functions are existentially quantified.
This is all the proof of Theorem 1 uses. The bound on `λ` is part of the statement: without it
`VerifierHypotheses` says nothing about `2.1248`. -/
theorem lemma_9 :
∃ (lam : ℝ) (ϕ β : ℝ → ℝ) (c : ℝ → ℝ → ℝ),
VerifierHypotheses lam ϕ β c ∧ 1 + 2 * lam ≤ 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…), Lemma 9, p.31
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.