EUVIMEDEUVIMED entdecken
Crossref

Separating and Collapsing Electoral Control Types

Benjamin Carleton, Michael C. Chavrimootoo, Lane A. Hemaspaandra, David E. Narvaez, Conor Taliancich, Henry B. Welles

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →