Destructive partition-of-voters criterion for plurality (TE) is decidable in polynomial time
OpenHHRControl.PV.plurality_te_dc_criterion_mem_PLet 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. The set of binary codes electionCode of the instances satisfying the criterion is in P: some one-tape Turing machine decides it in polynomial time. (The test loops over at most candidate pairs and counts voters, which takes time polynomial in the code length.)
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 polynomial-time test behind destructive control by partition of voters for plurality voting in model TE (Theorem 4.19, p. 17)
(Hemaspaandra–Hemaspaandra–Rothe): the codes of the elections satisfying the dethroning criterion
form a language in P. -/
theorem plurality_te_dc_criterion_mem_P :
{ w : List BSym | ∃ (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)) ∧
w = electionCode plurality c P } ∈ CookPvsNP.P BSym := by sorry
end HHRControl.PV