Condorcet destructive partition-of-voters criterion is decidable in polynomial time
OpenHHRControl.PV.condorcet_dc_criterion_mem_PLet be the candidates, a distinguished candidate and a list of voters with strict rankings. Say that satisfies the Condorcet dethroning criterion if there are candidates (possibly equal) such that
For this is the paper's inequality (4.2), ; taking it says that does not strictly beat , which covers the paper's trivial case where is not the Condorcet winner. By the proof of Theorem 4.20, the criterion holds exactly when can be made not the unique winner by partition of voters (in either tie-handling model).
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 paper's algorithm loops over all pairs and counts the four voter types, which takes time polynomial in and .)
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 Theorem 4.20 (Hemaspaandra–Hemaspaandra–Rothe, p. 18,
inequality (4.2)): the codes of the Condorcet elections `(C, c, V)` for which some `d₁ d₂ ≠ c`
have at most as many voters ranking `c` above both `d₁` and `d₂` as voters ranking `d₁` or `d₂`
above `c` form a language in P. -/
theorem condorcet_dc_criterion_mem_P :
{ w : List BSym | ∃ (m n : ℕ) (c : Fin m) (P : Fin n → Ranking m),
(∃ d₁ d₂ : Fin m, d₁ ≠ c ∧ d₂ ≠ c ∧
(univ.filter fun v => P v c < P v d₁ ∧ P v c < P v d₂).card ≤
(univ.filter fun v => P v d₁ < P v c ∨ P v d₂ < P v c).card) ∧
w = electionCode condorcet c P } ∈ CookPvsNP.P BSym := by sorry
end HHRControl.PV