Lemma 11 — breaking the social ordering's ties by a regular tie-breaker preserves CS, NNR and IIA
ProvedStrategyProofArrow.WeakArrow.lemma_11Let and , let be a social welfare function on weak ballot sets, and let be a strong order on . Define a new social welfare function by breaking the ties of each social ordering according to :
If satisfies CS, NNR and IIA, then has range contained in and satisfies CS, NNR and IIA.
This lemma lets the proof of Theorem 3' pass from an arbitrary Arrovian social welfare function to one with strong-order range, to which Lemma 10 applies.
Formalization Note The paper applies a regular tie-breaking function , defined on ballot sets, to the single ordering ; we read this as the component tie-breaker with tie-breaking order , the order the proof of Theorem 3' calls ", the tie-breaking order for ". The printed "define the social welfare function " is read as , as (44) shows. The range claim holds by construction (the tie-broken order is a strong order) and is stated as the first conjunct. CS is stated for distinct alternatives.
import Mathlib import Definitions.Def_StrategyProofArrow_WeakArrow_Basic
namespace StrategyProofArrow.WeakArrow
/-- **Lemma 11**, Satterthwaite p. 48: let `u` be a social welfare function on weak ballot sets,
with `n ≥ 2` and `m ≥ 3`, and let `μ(B) = γ[u(B)]` break the ties of each social ordering by a
regular tie-breaker with tie-breaking order `Q`. If `u` satisfies CS, NNR and IIA, then `μ` has
range contained in the strong orders and satisfies CS, NNR and IIA. -/
theorem lemma_11 {ι A : Type*} [Fintype ι] [Fintype A] [DecidableEq ι] [DecidableEq A]
(hn : 2 ≤ Fintype.card ι) (hm : 3 ≤ Fintype.card A)
(u : WeakProfile ι A → WeakOrder A) (Q : StrongOrder A)
(hCS : CS u) (hNNR : NNR u) (hIIA : IIA u) :
(∀ B, (breakTies Q (u B)).1.IsStrong) ∧
CS (fun B => (breakTies Q (u B)).1) ∧
NNR (fun B => (breakTies Q (u B)).1) ∧
IIA (fun B => (breakTies Q (u B)).1) := by sorry
end StrategyProofArrow.WeakArrow
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.