Polynomial-time certifier for destructive control by partition of voters, plurality (TE)
OpenHHRControl.PV.plurality_te_dc_certifierLet be the candidates, the distinguished candidate and a list of voters. Each voter casts a strict ranking; write for the number of voters ranking first, and for the number of voters preferring to . Say that satisfies the plurality-TE dethroning criterion if one of the following holds:
- for some ( is not the unique plurality winner);
- for some distinct (the paper's inequality (4.1));
- some has , , , and for every .
By the reduction submitted for Theorem 4.19, the criterion holds exactly when can be made not the unique winner by partition of voters in model TE (ties eliminate). Alternatives 1 and 2 are the partitions in which neither subcommittee nominates ; alternative 3 is the partition in which one subcommittee nominates and the other a candidate that ties or beats in the run-off. Note. The paper states the third condition with a strict inequality, . Its own construction needs only (the count must be below ), and the strict form is not necessary, so the criterion here uses .
Claim. There is a polynomial-time computable function on instance codes such that: if satisfies the criterion, outputs the code of a partition under which is not the unique winner of the two-stage election; otherwise outputs the code of "control impossible". (The partitions in the proof of the reduction are explicit: each part collects all voters of one type plus a prescribed number of voters of another type.)
import Mathlib import Definitions.Def_CookPvsNP_defs import Definitions.Def_ProjSchedTW_Complexity_Encoding import Definitions.Def_HHRControl_PV_Elections import Definitions.Def_HHRControl_PV_Languages
namespace HHRControl.PV
open CookPvsNP ProjSchedTW.Complexity Finset
/-- The certifying algorithm behind destructive control by partition of voters for plurality voting in model TE (Theorem 4.19, p. 17)
(Hemaspaandra–Hemaspaandra–Rothe): a polynomial-time function maps the code of every election
satisfying the dethroning criterion to the code of a partition of the voters under which `c` is not
the unique two-stage winner, and every other election code to "control impossible". -/
theorem plurality_te_dc_certifier :
∃ f : List BSym → List BSym, PolyTimeComputable f ∧
∀ (m n : ℕ) (c : Fin m) (P : Fin n → Ranking m),
(((∃ y, y ≠ c ∧ pluralityScore P univ univ c ≤ pluralityScore P univ univ y) ∨
(∃ y z, y ≠ c ∧ z ≠ c ∧ y ≠ z ∧
pluralityScore P univ univ c ≤
pluralityScore P univ univ y + pluralityScore P univ univ z) ∨
(∃ x, x ≠ c ∧ 1 ≤ pluralityScore P univ univ c ∧ 1 ≤ pluralityScore P univ univ x ∧
prefCount P univ c x ≤ prefCount P univ x c ∧
∀ t, t ≠ c → t ≠ x →
pluralityScore P univ univ t + 2 ≤
pluralityScore P univ univ c + pluralityScore P univ univ x)) →
∃ V₁ : Finset (Fin n), twoStage .TE plurality P V₁ ≠ {c} ∧
f (electionCode plurality c P) = partitionCode V₁) ∧
(¬ ((∃ y, y ≠ c ∧ pluralityScore P univ univ c ≤ pluralityScore P univ univ y) ∨
(∃ y z, y ≠ c ∧ z ≠ c ∧ y ≠ z ∧
pluralityScore P univ univ c ≤
pluralityScore P univ univ y + pluralityScore P univ univ z) ∨
(∃ x, x ≠ c ∧ 1 ≤ pluralityScore P univ univ c ∧ 1 ≤ pluralityScore P univ univ x ∧
prefCount P univ c x ≤ prefCount P univ x c ∧
∀ t, t ≠ c → t ≠ x →
pluralityScore P univ univ t + 2 ≤
pluralityScore P univ univ c + pluralityScore P univ univ x)) →
f (electionCode plurality c P) = impossibleCode) := by sorry
end HHRControl.PV