Equations (43)–(44) — elementary bounds on , and
ProvedStableVotingDistortion.eq_43_44metric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicevoting-ruleszero-sum-games
Let and let satisfy (26). For ,
and for ,
Differences from the source:
- reading: (43), (44) with the range of left implicit, and → in (43), in (44); reason: these are the ranges of (37) and (38), and they keep every printed argument in
- 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 set_option autoImplicit false
Formal statement
namespace StableVotingDistortion
/-- **Equations (43)–(44).** Under (26): for `0 ≤ q ≤ p ≤ 1`, `δ_p(q) ≤ p − q`, `δ_p(q) ≤ (1 − p) ϕ(q)` and
`J(q) ≥ q ϕ(q)`; and for `0 ≤ q ≤ p ≤ z ≤ 1`, `K_p(q, z) ≤ −(p − q) ϕ(z) − J(q)`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), App. C.1, Equations (43), (44), p.43: "δ_p(q) ≤ p − q, δ_p(q) ≤ (1 − p) ϕ(q), J(q) ≥ q ϕ(q). (43)
Similarly, for z ≥ p, since ϕ(r) ≥ ϕ(z) on [z − p + q, z], we have K_p(q, z) ≤ −(p − q) ϕ(z) − J(q). (44)"
**Formalization Note.** The page leaves the range of `p, q` implicit; these are the ranges of `(37)`, `(38)`,
and the printed arguments lie in `[0, 1]` on them. -/
theorem eq_43_44 {lam : ℝ} {ϕ : ℝ → ℝ} (hϕ : IsScoreFunction lam ϕ) :
(∀ p q, 0 ≤ q → q ≤ p → p ≤ 1 →
deltaP ϕ p q ≤ p - q ∧ deltaP ϕ p q ≤ (1 - p) * ϕ q ∧ q * ϕ q ≤ J ϕ q) ∧
∀ p q z, 0 ≤ q → q ≤ p → p ≤ z → z ≤ 1 → KP ϕ p q z ≤ -(p - q) * ϕ z - J ϕ q := 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…), App. C.1, Equations (43), (44), p.43
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.