%ACarleton, C.%AChavrimootoo, M.%AHemaspaandra, Lane%ANarvaez, D.%ATaliancich, C.%AWelles, H.%D2023%I
%K
%MOSTI ID: 10422854
%PMedium: X
%TSeparating and Collapsing Electoral Control Types
%XElectoral control refers to attacking elections by adding, deleting,
or partitioning voters or candidates [3]. Hemaspaandra et al. [16]
discovered, for seven pairs (T , T ′ ) of seemingly distinct standard
electoral control types, that T and T ′ are identical: For each input
𝐼 and each election system E, 𝐼 is a “yes” instance of both T and T ′
under E, or of neither. Surprisingly, this had gone undetected even
as the field was score-carding how many standard control types
election systems were resistant to; various “different” cells on such
score cards were, unknowingly, duplicate effort on the same issue.
This naturally raises the worry that other pairs of control types are
also identical, and so work still is being needlessly duplicated.
We determine, for all standard control types, which pairs are, for
elections whose votes are linear orderings of the candidates, always
identical. We show that no identical control pairs exist beyond the
known seven. For three central election systems, we determine
which control pairs are identical (“collapse”) with respect to those
particular systems, and we explore containment/incomparability
relationships between control pairs. For approval voting, which has
a different “type” for its votes, Hemaspaandra et al.’s [16] seven
collapses still hold. But we find 14 additional collapses that hold
for approval voting but not for some election systems whose votes
are linear orderings. We find one additional collapse for veto and
none for plurality. We prove that each of the three election sys-
tems mentioned have no collapses other than those inherited from
Hemaspaandra et al. [16] or added here. But we show many new
containment relationships that hold between some separating con-
trol pairs, and for each separating pair of standard control types
classify its separation in terms of containment (always, and strict
on some inputs) or incomparability.
Our work, for the general case and these three important election
systems, clarifies the landscape of the 44 standard control types,
for each pair collapsing or separating them, and also providing
finer-grained information on the separations.