Polynomial-time certifier for Condorcet destructive control by partition of voters
OpenHHRControl.PV.condorcet_dc_certifierLet 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. There is a polynomial-time computable function on instance codes such that: if satisfies the criterion, then outputs the code of a partition in which is the Condorcet winner of neither nor ; otherwise outputs the code of "control impossible". (The paper's stage 2 gives such a partition: holds the voters and of the voters.)
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 Theorem 4.20 (Hemaspaandra–Hemaspaandra–Rothe, p. 18): a
polynomial-time function maps the code of every Condorcet election satisfying inequality (4.2) for
some `d₁ d₂ ≠ c` to the code of a partition `(V₁, V₁ᶜ)` in which `c` is the Condorcet winner of
neither part, and every other election code to "control impossible". -/
theorem condorcet_dc_certifier :
∃ f : List BSym → List BSym, PolyTimeComputable f ∧
∀ (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) →
∃ V₁ : Finset (Fin n), c ∉ condorcet.winners m n P univ V₁ ∧
c ∉ condorcet.winners m n P univ V₁ᶜ ∧
f (electionCode condorcet c P) = partitionCode V₁) ∧
(¬ (∃ 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) →
f (electionCode condorcet c P) = impossibleCode) := by sorry
end HHRControl.PV