Example 4.10, p. 12 — Condorcet voting is susceptible to destructive control by partition of voters
ProvedHHRControl.PV.example_4_10condorcetelection-controlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1susceptibility
Example 4.10. Let and let consist of seven voters
Then is the Condorcet winner of . For and there is no Condorcet winner of and is the Condorcet winner of , so is not the unique winner of the two-stage election (in either tie-handling model). Consequently Condorcet voting is susceptible to destructive control by partition of voters.
This election witnesses the susceptibility part of the Condorcet clause of Theorem 3.6.
Differences from the source:
- encoding: candidates a, b, c; voters v1, v2, … → candidates 0, 1, 2 of Fin 3; voter vᵢ is index i − 1 of Fin n; reason: 0-based indices; no instance changes
- encoding: voters with the listed preference orders → every profile P whose ballots have the listed codes (rankingCode lists the candidates from most to least preferred); reason: rankingCode is injective, so this is exactly the listed profile; the profile exists
- encoding: Condorcet: the models TE and TP do not apply (p. 3) → stated for both tie rules; reason: a Condorcet winner is unique when it exists, so TE and TP nominate the same candidates and give the same two-stage election
Preamble
import Mathlib import Definitions.Def_HHRControl_PV_Elections
Formal statement
namespace HHRControl.PV
open Finset
/-- Example 4.10, p. 12: Condorcet voting is susceptible to destructive control by partition of
voters (in either tie-handling model). Candidates `a, b, c` are `0, 1, 2`; a ballot is given by
its code, the candidates from the most to the least preferred. -/
theorem example_4_10 :
(∀ P : Fin 7 → Ranking 3,
(∀ v, rankingCode (P v) =
![[2, 0, 1], [2, 0, 1], [2, 1, 0], [1, 0, 2], [1, 2, 0], [0, 1, 2], [0, 2, 1]] v) →
condorcet.winners 3 7 P univ univ = {2} ∧
condorcet.winners 3 7 P univ {0, 6} = ∅ ∧
condorcet.winners 3 7 P univ ({0, 6} : Finset (Fin 7))ᶜ = {1} ∧
∀ rule : TieRule, twoStage rule condorcet P {0, 6} ≠ {2}) ∧
∀ rule : TieRule, SusceptibleDC rule condorcet := by sorry
end HHRControl.PV
Source
Hemaspaandra, Hemaspaandra & Rothe, Anyone but Him: The Complexity of Precluding an Alternative, arXiv:cs/0507027v5, p. 12, Example 4.10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.