Polynomial-time certifier for destructive control by partition of voters, approval (TE)
OpenHHRControl.PV.approval_te_dc_certifierLet be the candidates, the distinguished candidate and a list of voters. Each voter casts an approval ballot . Say that satisfies the approval-TE dethroning criterion if there are (possibly equal) with
By the reduction submitted for Theorem 4.21, this holds exactly when can be made not the unique winner by partition of voters in model TE. The case says that ties or beats in total approvals.
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 approval voting in model TE (Theorem 4.21, p. 19)
(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 approval_te_dc_certifier :
∃ f : List BSym → List BSym, PolyTimeComputable f ∧
∀ (m n : ℕ) (c : Fin m) (P : Fin n → Approval m),
((∃ y z : Fin m, y ≠ c ∧ z ≠ c ∧
(univ.filter fun v => c ∈ P v ∧ y ∉ P v ∧ z ∉ P v).card ≤
(univ.filter fun v => c ∉ P v ∧ (y ∈ P v ∨ z ∈ P v)).card) →
∃ V₁ : Finset (Fin n), twoStage .TE approval P V₁ ≠ {c} ∧
f (electionCode approval c P) = partitionCode V₁) ∧
(¬ (∃ y z : Fin m, y ≠ c ∧ z ≠ c ∧
(univ.filter fun v => c ∈ P v ∧ y ∉ P v ∧ z ∉ P v).card ≤
(univ.filter fun v => c ∉ P v ∧ (y ∈ P v ∨ z ∈ P v)).card) →
f (electionCode approval c P) = impossibleCode) := by sorry
end HHRControl.PV