Lemma 14(ii) — large masses: (37), (38) for with
ProvedStableVotingDistortion.lemma_14_iimetric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-v1social-choicevoting-ruleszero-sum-games
Let , let satisfy (26) with nonincreasing on , and let . Suppose on an interval with and , that is concave on , and that for constants ,
If, for every , (25) holds and
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 (ii)
- encoding: an interval on which → with
0 ≤ rmandzp ≤ 1; reason: is a function on , so the interval lies there - 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(ii) (large masses).** Let `ϕ` satisfy (26) with `ϕ(r) + r` nonincreasing on `[λ, 1]`, and let
`λ < p₁ < 1`. Suppose `ϕ(r) = λ − r` on `[r₋, z₊]` with `r₋ < λ` and `λ + (1 − p₁) ≤ z₊`, that `ϕ` is concave on
`[λ, 1]`, and that (46) holds for constants `0 < m₀ < 1 ≤ M`. If (25) and (47) hold for every `p ∈ [p₁, 1)`, then
(37) and (38) hold for every `p ∈ [p₁, 1)` with `β(p) = p / J(p)` and
`c(p, x) = (λ − x − β(p)(1 − p) ϕ(x))₊`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), Lemma 14(ii), p.44: "(ii) Suppose that ϕ(r) = λ − r on an interval [r_−, z_+] with r_− < λ and
λ + (1 − p_1) ≤ z_+, that ϕ is concave on [λ, 1], and that for constants 0 < m_0 < 1 ≤ M, ϕ(r) − ϕ(s) ≤ m_0(s − r)
for 0 ≤ r < s ≤ r_−, ϕ(r) − ϕ(s) ≤ M(s − r) for p_1 ≤ r < s ≤ 1. (46) If, for every p ∈ [p_1, 1), Equation (25)
holds and m_0 p(1 − p) ≤ J(p) ≤ p(1 − p), p (1 − (M + 1)(1 − p)) ≥ (M − 1)J(p), (47) then Equations (37) and (38)
hold for every p ∈ [p_1, 1) with β(p) = p/J(p) and c(p, x) = (λ − x − β(p)(1 − p)ϕ(x))_+."
**Formalization Note.** `0 ≤ r₋` and `z₊ ≤ 1` say the interval lies in `ϕ`'s domain `[0, 1]`. `J(p) > 0` on
`[p₁, 1)` follows from (47), so `p / J(p)` is not a junk value there. `p₀` of the page's opening sentence
plays no part in (ii) and is not a binder. -/
theorem lemma_14_ii {lam : ℝ} {ϕ : ℝ → ℝ} (hϕ : IsScoreFunction lam ϕ)
(hadd : AntitoneOn (fun r => ϕ r + r) (Set.Icc lam 1))
{p1 : ℝ} (hp1lam : lam < p1) (hp1 : p1 < 1)
{rm zp : ℝ} (hrm0 : 0 ≤ rm) (hzp1 : zp ≤ 1) (hrm : rm < lam) (hzp : lam + (1 - p1) ≤ zp)
(hline : ∀ r ∈ Set.Icc rm zp, ϕ r = lam - r)
(hconc : ConcaveOn ℝ (Set.Icc lam 1) ϕ)
{m0 M : ℝ} (hm0 : 0 < m0) (hm01 : m0 < 1) (hM : 1 ≤ M)
(h46a : ∀ r s, 0 ≤ r → r < s → s ≤ rm → ϕ r - ϕ s ≤ m0 * (s - r))
(h46b : ∀ r s, p1 ≤ r → r < s → s ≤ 1 → ϕ r - ϕ s ≤ M * (s - r))
(h25 : ∀ p ∈ Set.Ico p1 1, Eq25 lam ϕ p)
(h47a : ∀ p ∈ Set.Ico p1 1, m0 * (p * (1 - p)) ≤ J ϕ p)
(h47b : ∀ p ∈ Set.Ico p1 1, J ϕ p ≤ p * (1 - p))
(h47c : ∀ p ∈ Set.Ico p1 1, (M - 1) * J ϕ p ≤ p * (1 - (M + 1) * (1 - p))) :
∀ p ∈ Set.Ico p1 1,
Eq37 lam ϕ (fun p => p / J ϕ p)
(fun p x => max (lam - x - p / J ϕ p * (1 - p) * ϕ x) 0) p ∧
Eq38 lam ϕ (fun p => p / J ϕ p)
(fun p x => max (lam - x - p / J ϕ p * (1 - p) * ϕ 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(ii), p.44
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.