Polynomial-time certifier for destructive control by partition of voters, approval (TP)
OpenHHRControl.PV.approval_tp_dc_certifierLet be the candidates, the distinguished candidate and a list of voters. Each voter casts an approval ballot ; write for the number of voters approving . Say that satisfies the approval-TP dethroning criterion if either for some , or there are with
and .
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 TP (ties promote). The second alternative is a partition in which strictly beats in one part and strictly beats in the other, so that no subcommittee nominates .
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 TP (Theorem 4.21, p. 19, corrected in Appendix A, pp. 34–36)
(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_tp_dc_certifier :
∃ f : List BSym → List BSym, PolyTimeComputable f ∧
∀ (m n : ℕ) (c : Fin m) (P : Fin n → Approval m),
(((∃ x : Fin m, x ≠ c ∧ approvalScore P univ c ≤ approvalScore P univ x) ∨
∃ y z : Fin m, y ≠ c ∧ z ≠ c ∧
(univ.filter fun v => c ∈ P v ∧ y ∉ P v ∧ z ∉ P v).card + 2 ≤
(univ.filter fun v => c ∉ P v ∧ (y ∈ P v ∨ z ∈ P v)).card ∧
1 ≤ (univ.filter fun v => c ∉ P v ∧ y ∈ P v).card ∧
1 ≤ (univ.filter fun v => c ∉ P v ∧ z ∈ P v).card) →
∃ V₁ : Finset (Fin n), twoStage .TP approval P V₁ ≠ {c} ∧
f (electionCode approval c P) = partitionCode V₁) ∧
(¬ ((∃ x : Fin m, x ≠ c ∧ approvalScore P univ c ≤ approvalScore P univ x) ∨
∃ y z : Fin m, y ≠ c ∧ z ≠ c ∧
(univ.filter fun v => c ∈ P v ∧ y ∉ P v ∧ z ∉ P v).card + 2 ≤
(univ.filter fun v => c ∉ P v ∧ (y ∈ P v ∨ z ∈ P v)).card ∧
1 ≤ (univ.filter fun v => c ∉ P v ∧ y ∈ P v).card ∧
1 ≤ (univ.filter fun v => c ∉ P v ∧ z ∈ P v).card) →
f (electionCode approval c P) = impossibleCode) := by sorry
end HHRControl.PV