Equations (34)–(35) — the potentials and are nonnegative and nondecreasing
ProvedStableVotingDistortion.W_nonneg_monotonemetric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1social-choicevoting-ruleszero-sum-games
Let , let satisfy (26), and let be nonincreasing on . Then for each , the function of (34) is nonnegative and nondecreasing on . Moreover for any election, lottery and candidate with , the function of (35) is nonnegative and nondecreasing on .
Differences from the source:
- generalization: §6.3.1's setting: a -stable lottery (for of (35)) → any lottery
D ∈ stdSimplex ℝ Cwith ; reason: is a -weighted average of the , and the argument of p.29 uses only (26) and nonincreasing; a -stable lottery is a lottery, so the statement specializes to the page's - encoding: → a function
ℝ → ℝconstrained only on[0, 1]; reason: Lean functions are total; every printed argument lies in - 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_IsScoreFunction import Definitions.Def_StableVotingDistortion_scorePrimitives import Definitions.Def_StableVotingDistortion_slices import Definitions.Def_StableVotingDistortion_offset set_option autoImplicit false open PctDistortion
Formal statement
namespace StableVotingDistortion
/-- **Equations (34)–(35): the potentials.** Under (26) with `ϕ(z) + z` nonincreasing on `[λ, 1]`: for each
`x ∈ [0, λ)`, `W_x` is nonnegative and nondecreasing on `[0, 1]`; and for any lottery with `A > 0`, so is `W`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), §6.3.1, Equations (34), (35), p.29: "Because 0 < ϕ(x) ≤ λ − x by Equation (26), the line through
(x, ϕ(x)) and (λ, 0) has slope at least −1. Provided that ϕ(z) + z is nonincreasing on [λ, 1], ϕ falls at
least as steeply as this line beyond λ, so the horizontal gap W_x(z) between them in Figure 10 is
nonnegative and grows with z. Hence W is nonnegative and nondecreasing." -/
theorem W_nonneg_monotone {lam : ℝ} {ϕ : ℝ → ℝ} (hϕ : IsScoreFunction lam ϕ)
(hadd : AntitoneOn (fun r => ϕ r + r) (Set.Icc lam 1)) :
(∀ x ∈ Set.Ico 0 lam, (∀ z ∈ Set.Icc (0 : ℝ) 1, 0 ≤ Wx lam ϕ x z) ∧
MonotoneOn (Wx lam ϕ x) (Set.Icc 0 1)) ∧
∀ {V C : Type} [Fintype V] [Nonempty V] [Fintype C] [Nonempty C] (E : Election V C) (D : C → ℝ), D ∈ stdSimplex ℝ C → ∀ aStar : C,
0 < Aval lam ϕ E D aStar →
(∀ z ∈ Set.Icc (0 : ℝ) 1, 0 ≤ WAvg lam ϕ E D aStar z) ∧
MonotoneOn (WAvg lam ϕ E D aStar) (Set.Icc 0 1) := 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, Equations (34), (35), p.29
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.