Destructive partition-of-voters criterion for approval (TP) is decidable in polynomial time
OpenHHRControl.PV.approval_tp_dc_criterion_mem_PLet 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. 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 approval voting in model TP (Theorem 4.21, p. 19, corrected in Appendix A, pp. 34–36)
(Hemaspaandra–Hemaspaandra–Rothe): the codes of the elections satisfying the dethroning criterion
form a language in P. -/
theorem approval_tp_dc_criterion_mem_P :
{ w : List BSym | ∃ (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) ∧
w = electionCode approval c P } ∈ CookPvsNP.P BSym := by sorry
end HHRControl.PV