Claim 4.29, p. 24 — a hitting set B′ of size k makes w the unique plurality winner of (B′ ∪ {c, w}, V)
ProvedHHRControl.PV.claim_4_29election-controlhitting-setp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1plurality
Let be an election of Construction 4.28 for the Hitting Set instance : candidates with , a positive integer , and the voters listed there.
Claim 4.29. If is a hitting set of of size , then is the unique plurality winner of the election
It is the first half of the correctness of the reduction from Hitting Set.
Differences from the source:
- reading: Construction 4.28: the remaining candidates, and the elements of Sᵢ, follow "in some arbitrary order" → the claim is stated for every profile satisfying IsConstruction428 (any orders, any order of the voters); reason: the paper's arbitrary choice is universal; one canonical order would be a special case
- encoding: candidates B ∪ {c, w} with B = {b1, …, bm}; S = {S1, …, Sn} → candidates Fin (m + 2) with bⱼ = candB (j − 1), c = candC m = m, w = candW m = m + 1; S : Fin n → Finset (Fin m); reason: 0-based indices; no instance changes
Preamble
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 import Definitions.Def_HHRControl_PV_Construction428
Formal statement
namespace HHRControl.PV
open CookPvsNP
/-- Claim 4.29, p. 24: in an election of Construction 4.28, if `B′` is a hitting set of `S` of size
`k`, then `w` is the unique plurality winner of the election `(B′ ∪ {c, w}, V)`. -/
theorem claim_4_29 (m n k : ℕ) (S : Fin n → Finset (Fin m)) {N : ℕ} (P : Fin N → Ranking (m + 2))
(hP : IsConstruction428 m n k S P) (B' : Finset (Fin m)) (hcard : B'.card = k)
(hhit : IsHittingSet S B') :
plurality.winners (m + 2) N P (B'.image candB ∪ {candC m, candW m}) Finset.univ =
{candW m} := by sorry
end HHRControl.PV
Source
Hemaspaandra, Hemaspaandra & Rothe, Anyone but Him: The Complexity of Precluding an Alternative, arXiv:cs/0507027v5, p. 24, Claim 4.29
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.