Example 4.16, p. 14 — plurality is susceptible to constructive and destructive control by partition of voters in model TP
ProvedHHRControl.PV.example_4_16election-controlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pluralitysusceptibility
Example 4.16. Let and let consist of eight voters: voting , voting , and voting .
Constructive case. and tie for first place in , so is not the unique plurality winner. For and , is the unique winner of , of , and wins the run-off against .
Destructive case. Let with and . Then is the unique plurality winner of . For and , is the unique winner of , of , and wins the run-off against .
Consequently plurality voting is susceptible to constructive and to destructive control by partition of voters in model TP.
These elections witness the susceptibility part of the plurality TP clauses of Theorem 3.6.
Differences from the source:
- encoding: candidates a, b, c; voters u1, u2, u3, v1, v2, w1, w2, w3 (then v3, w4) → candidates 0, 1, 2 of Fin 3; the voters are indices 0–7 in that order (then 8, 9); 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
Preamble
import Mathlib import Definitions.Def_HHRControl_PV_Elections
Formal statement
namespace HHRControl.PV
open Finset
/-- Example 4.16, p. 14: plurality voting is susceptible to constructive and to destructive control
by partition of voters in model TP. Candidates `a, b, c` are `0, 1, 2`; a ballot is given by its
code, the candidates from the most to the least preferred. The voters are listed in the order
`u₁, u₂, u₃, v₁, v₂, w₁, w₂, w₃` (then `v₃, w₄` for the election `(C, V′)`). -/
theorem example_4_16 :
(∀ P : Fin 8 → Ranking 3,
(∀ v, rankingCode (P v) = ![[0, 2, 1], [0, 2, 1], [0, 2, 1], [1, 0, 2], [1, 0, 2],
[2, 0, 1], [2, 0, 1], [2, 0, 1]] v) →
plurality.winners 3 8 P univ univ = {0, 2} ∧
plurality.winners 3 8 P univ {0, 1, 5, 6, 7} = {2} ∧
plurality.winners 3 8 P univ ({0, 1, 5, 6, 7} : Finset (Fin 8))ᶜ = {1} ∧
twoStage .TP plurality P {0, 1, 5, 6, 7} = {2}) ∧
(∀ P' : Fin 10 → Ranking 3,
(∀ v, rankingCode (P' v) = ![[0, 2, 1], [0, 2, 1], [0, 2, 1], [1, 0, 2], [1, 0, 2],
[2, 0, 1], [2, 0, 1], [2, 0, 1], [1, 0, 2], [2, 0, 1]] v) →
plurality.winners 3 10 P' univ univ = {2} ∧
plurality.winners 3 10 P' univ {0, 1, 2, 5, 6} = {0} ∧
plurality.winners 3 10 P' univ ({0, 1, 2, 5, 6} : Finset (Fin 10))ᶜ = {1} ∧
twoStage .TP plurality P' {0, 1, 2, 5, 6} = {0}) ∧
SusceptibleCC .TP plurality ∧ SusceptibleDC .TP plurality := by sorry
end HHRControl.PV
Source
Hemaspaandra, Hemaspaandra & Rothe, Anyone but Him: The Complexity of Precluding an Alternative, arXiv:cs/0507027v5, p. 14, Example 4.16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.