§6.3 — consequences of (26): , and is an activation with
ProvedStableVotingDistortion.gPhi_propertiesmetric-distortionp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1social-choicevoting-ruleszero-sum-games
Let and let satisfy (26). Then:
- and on ;
- is continuous and nondecreasing and maps into ;
- and ;
- with , we have on .
So is a score function for the activation .
Differences from the source:
- generalization: continuous and nondecreasing with , → also
Set.MapsTointo , throughIsActivation (gPhi ϕ); reason: this follows from the printed clauses and Definition 3 requires it; dropping that clause gives the printed statement - 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_IsGStable import Definitions.Def_StableVotingDistortion_IsScoreFunction import Definitions.Def_StableVotingDistortion_scorePrimitives set_option autoImplicit false
Formal statement
namespace StableVotingDistortion
/-- **Consequences of (26), §6.3.** `ϕ(λ) = 0` and `ϕ ≤ 0` on `[λ, 1]`; `g_ϕ` is continuous, nondecreasing,
maps `[0, 1]` into `[0, 1]`, has `g_ϕ(0) = 0` and `g_ϕ(1) = 1`; and `ϕ = (1 + ϕ(0))(τ − g_ϕ)` on `[0, 1]`,
where `τ = ∫_0^1 g_ϕ`.
Cai et al., arXiv:2609.08259 (held version, sha256 cfdd5f3d…), §6.3, p.26: "In particular, these conditions imply that ϕ(λ) = 0 and ϕ(r) ≤ 0 on [λ, 1]. Reversing
Equation (23), the function g_ϕ(r) = (ϕ(0) − ϕ(r))/(1 + ϕ(0)) is continuous and nondecreasing with
g_ϕ(0) = 0 and g_ϕ(1) = 1, and satisfies ϕ = (1 + ϕ(0))(τ − g_ϕ) where τ = ∫_0^1 g_ϕ(r) dr."
**Formalization Note.** "Into `[0, 1]`" is not printed; it follows from the printed clauses and is what
Definition 3 needs. It is included through `IsActivation`. -/
theorem gPhi_properties {lam : ℝ} {ϕ : ℝ → ℝ} (h : IsScoreFunction lam ϕ) :
ϕ lam = 0 ∧ (∀ r ∈ Set.Icc lam 1, ϕ r ≤ 0) ∧ IsActivation (gPhi ϕ) ∧
gPhi ϕ 0 = 0 ∧ gPhi ϕ 1 = 1 ∧
∀ r ∈ Set.Icc (0 : ℝ) 1, ϕ r = (1 + ϕ 0) * ((∫ u in (0 : ℝ)..1, gPhi ϕ u) - gPhi ϕ r) := 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, p.26
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.