Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Aether Catalog definitions — Bridges_GL3KemenyRobustness

Definition
Bridges_GL3KemenyRobustness

by raver1975 · Sep 17, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalogbridges

Definition bundle for the Aether Catalog module Bridges.GL3KemenyRobustness, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.

Definition code
-- Def bundle generated from Bridges/GL3KemenyRobustness.lean by skeleton subtraction
import Mathlib
/-
Copyright (c) 2026 Harmonic. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.

# GL3 Kemeny–Young Certified Robustness

This file formalizes certified robustness for a 3-class decision rule obtained via
Kemeny–Young aggregation. For 3 candidates, the Kemeny score of each of the 6 possible
rankings is an explicit affine-linear form in three pairwise margins. This allows us to
transfer Lipschitz control on individual class scores to a certified robustness radius for
the Kemeny winner.

## Main results

* `margin_perturbation_bound` — pairwise margins perturb by at most `2 * Kd * ε`
* `kemenyScore_perturbation_bound` — each Kemeny score perturbs by at most `6 * Kd * ε`
* `unique_kemeny_winner_stable` — if the gap exceeds `12 * Kd * ε`, the winner is preserved
* `kemeny_winner_certified_radius` — certified radius `Δ / (12 * Kd)` for winner preservation
* `kemeny_winner_label_stable` — the top-class label is preserved within the certified radius
-/


open scoped BigOperators

namespace GL3Kemeny

/-! ## Margins -/

/-- Pairwise margin: difference between score of class `i` and class `j`. -/
def margin {α : Type*} (h : α → Fin 3 → ℝ) (x : α) (i j : Fin 3) : ℝ := h x i - h x j



/-! ## The six rankings of Fin 3 -/

/-- The six possible rankings (permutations) of three candidates. Named by the order
    of preference: `r012` means `0 ≻ 1 ≻ 2`. -/
inductive KemenyRanking : Type
  | r012 | r021 | r102 | r120 | r201 | r210
  deriving DecidableEq, Repr

instance : Fintype KemenyRanking where
  elems := {KemenyRanking.r012, KemenyRanking.r021, KemenyRanking.r102,
            KemenyRanking.r120, KemenyRanking.r201, KemenyRanking.r210}
  complete := by intro x; cases x <;> simp

namespace KemenyRanking

instance : Inhabited KemenyRanking := ⟨r012⟩

/-- The top-ranked class of a ranking. -/
def topClass : KemenyRanking → Fin 3
  | r012 => 0
  | r021 => 0
  | r102 => 1
  | r120 => 1
  | r201 => 2
  | r210 => 2

end KemenyRanking

/-! ## Kemeny scores

The Kemeny score of a ranking `σ` is the sum of `margin h x (σ i) (σ j)` over pairs `i < j`
in the ranking order. For three candidates this is a sum of three signed margins. -/

/-- The Kemeny score of a ranking at point `x` under score map `h`.
    Each score is expressed as a sum of three signed margins. -/
def kemenyScore {α : Type*} (h : α → Fin 3 → ℝ) (x : α) : KemenyRanking → ℝ
  | .r012 =>  (margin h x 0 1) + (margin h x 0 2) + (margin h x 1 2)
  | .r021 =>  (margin h x 0 1) + (margin h x 0 2) - (margin h x 1 2)
  | .r102 => -(margin h x 0 1) + (margin h x 0 2) + (margin h x 1 2)
  | .r120 => -(margin h x 0 1) - (margin h x 0 2) + (margin h x 1 2)
  | .r201 =>  (margin h x 0 1) - (margin h x 0 2) - (margin h x 1 2)
  | .r210 => -(margin h x 0 1) - (margin h x 0 2) - (margin h x 1 2)

/-! ## Perturbation bounds -/

/-
The pairwise margin perturbs by at most `2 * Kd * ε` when each score perturbs by `Kd * ε`.
-/

/-
Each Kemeny score perturbs by at most `6 * Kd * ε`, since each score is a sum of three
    signed margins, each perturbing by at most `2 * Kd * ε`.
-/

/-! ## Unique winner and gap -/

/-- A ranking `s` is the unique Kemeny winner at `x` if it strictly dominates all others. -/
def isUniqueKemenyWinner {α : Type*} (h : α → Fin 3 → ℝ) (x : α) (s : KemenyRanking) : Prop :=
  ∀ t, t ≠ s → kemenyScore h x t < kemenyScore h x s

/-! ## Score gap perturbation -/

/-
The gap between any two Kemeny scores perturbs by at most `12 * Kd * ε`.
-/

/-! ## Main stability theorem -/

/-
**Kemeny winner stability**: If the unique Kemeny winner at `x` has a score gap `Δ` over
    all competitors, and each class score perturbs by at most `Kd * ε` with
    `12 * Kd * ε < Δ`, then the same ranking remains the unique winner at `y`.
-/

/-! ## Certified radius corollary -/

/-
**Certified radius**: If `ε < Δ / (12 * Kd)`, the unique Kemeny winner is preserved.
-/

/-! ## Winner label -/

/-- The Kemeny winner class: class `c` is the Kemeny winner if there exists a unique
    optimal ranking whose top element is `c`. -/
def kemenyWinner {α : Type*} (h : α → Fin 3 → ℝ) (x : α) (c : Fin 3) : Prop :=
  ∃ s, KemenyRanking.topClass s = c ∧ isUniqueKemenyWinner h x s

/-
**Label stability**: Under the certified radius, the Kemeny winner label is preserved.
-/

/-! ## Winner region characterization

For each ranking, we can characterize when it has the highest Kemeny score
in terms of explicit linear inequalities on the margins. -/

/-
Ranking `0 ≻ 1 ≻ 2` is the unique Kemeny winner iff all three basic margins are positive.
-/

end GL3Kemeny

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me