Separating and Collapsing Electoral Control Types
Journal of Artificial Intelligence Research · 11.09.2024 · 81 · 71-116
DOI: 10.1613/jair.1.15483 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 11.09.2024. Verfasst von Benjamin Carleton und 5 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref).
Abstract (Originalsprache)
Electoral control refers to attacking elections by adding, deleting, or partitioning voters or candidates. Hemaspaandra, Hemaspaandra, and Menton recently discovered, for seven pairs (T, T′) of seemingly distinct standard electoral control types, that T and T′ are in practice identical: For each input I and each election system E, I is a “yes” instance of both T and T′ under E, or of neither. Surprisingly, this had previously gone undetected even as the field was score-carding how many standard control types various 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 perhaps other pairs of control types are identical, and so work still is being needlessly duplicated. We completely determine, for all standard control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. In particular, we prove that no identical control pairs exist beyond the known seven. We also for three central election systems completely determine which control pairs are identical (“collapse”) with respect to those particular election systems, and we also explore containment and incomparability relationships between control pairs. For approval voting, which has a different “type” for its votes, Hemaspaandra, Hemaspaandra, and Menton’s seven collapses still hold (since we observe that their argument applies to all election systems). However, we find 14 additional collapses that hold for approval voting but do not hold for some election systems whose votes are linear orderings of the candidates. We find one new collapse for veto elections and none for plurality. We prove that each of the three election systems mentioned have no collapses other than those inherited from Hemaspaandra, Hemaspaandra, and Menton or added in the present paper. We establish many new containment relationships between separating control pairs, and for each separating pair of standard control types classify its separation in terms of either 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.
Zitieren
APA
Carleton, B., Chavrimootoo, M. C., Hemaspaandra, L. A., Narvaez, D. E., Taliancich, C., & Welles, H. B. (2024). Separating and Collapsing Electoral Control Types. Journal of Artificial Intelligence Research, 81, 71-116. https://doi.org/10.1613/jair.1.15483
Vancouver
Carleton B, Chavrimootoo MC, Hemaspaandra LA, Narvaez DE, Taliancich C, Welles HB. Separating and Collapsing Electoral Control Types. Journal of Artificial Intelligence Research. 2024;81:71-116. doi:10.1613/jair.1.15483
BibTeX
@article{Carleton2024,
author = {Carleton, Benjamin and Chavrimootoo, Michael C. and Hemaspaandra, Lane A. and Narvaez, David E. and Taliancich, Conor and Welles, Henry B.},
title = {Separating and Collapsing Electoral Control Types},
journal = {Journal of Artificial Intelligence Research},
year = {2024},
volume = {81},
pages = {71--116},
doi = {10.1613/jair.1.15483}
}
EUVIMED