Lemma 9 (second sentence) — every strategy-proof procedure is a tie-breaker followed by a strict strategy-proof procedure
ProvedStrategyProofArrow.WeakGS.lemma_9_iiConsider a committee of individuals and a finite set of alternatives, with indifference admissible on ballots. If the voting procedure is strategy-proof, then there exist a strict strategy-proof voting procedure and a tie-breaking function such that
The tie-breaking function need not be regular: may depend on the whole ballot set , not only on . This decomposition reduces the case of ballots with indifference to the strict case, and is the step that carries Theorem 1 over to Theorem 1′.
Formalization Note A tie-breaking function only has to keep every strict preference of every ballot; no regularity is required. The hypotheses and are the paper's standing assumptions on a committee (p. 6).
import Mathlib import Definitions.Def_StrategyProofArrow_WeakGS_Basic
namespace StrategyProofArrow.WeakGS
/-- **Lemma 9, second sentence** (Satterthwaite, p. 41). In a committee (`n ≥ 1`, `m ≥ 3`), if the
voting procedure `v` is strategy-proof, then there exist a strict strategy-proof voting procedure
`ν` and a tie-breaking function `α` (not necessarily regular) with `v(B) = ν[α(B)]` for all
`B ∈ π^n_m`. -/
theorem lemma_9_ii {ι A : Type*} [Fintype ι] [Fintype A] [DecidableEq ι]
(hn : 1 ≤ Fintype.card ι) (hm : 3 ≤ Fintype.card A)
(v : VotingProcedure ι A) (hv : StrategyProof v) :
∃ (ν : StrictVotingProcedure ι A) (α : WeakProfile ι A → StrategyProofArrow.Correspondence.StrongProfile ι A),
StrictStrategyProof ν ∧ IsTieBreaking α ∧ ∀ B : WeakProfile ι A, v B = ν (α B) := by sorry
end StrategyProofArrow.WeakGS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.