More Like this

1. Separating and Collapsing Electoral Control Types

   Carleton, C.; Chavrimootoo, M.; Hemaspaandra, Lane A.; Narvaez, D.; Taliancich, C.; Welles, H. (May 2023, Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems)

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

   more » « less
2. Separations and Collapses in Computational Social Choice (Doctoral Consortium)

   Chavrimootoo, Michael C. (May 2023, Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems)

   Following the seminal work of Bartholdi et al. [2], there has been a slew of research on the complexity of constructive and destructive control for specific election systems (a.k.a. voting rules), which was driven by the field’s desire to find a natural election system that is “resistant” to as many control attacks (types) as possible. While this race was happening, many proofs were devised for a variety of election systems, and yet unbeknownst to many, several control attacks were in fact exactly the same (when viewed as decision problems, which is the common framework). Hemaspaandra et al. [14] were the first to make this observation, demonstrating that there was a general lack of understanding of the standard control attacks. My work continues this line of research in three ways: (1) determining the relationships of electoral control types both in the “general” setting and in concrete settings, (2) finding axiomatic- sufficient conditions to determine if a particular equality between control types (a.k.a. collapse) occurs, and (3) linking results in the more abstract decision model to the more explicit search model. 

   more » « less
3. Search versus Search for Collapsing Electoral Control Types (extended abstract)

   Carleton, B.; Chavrimootoo, Michael C.; Hemaspaandra, Lane A.; Narvaez, D.; Taliancich, C.; Welles, H. (May 2023, Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems)

   Hemaspaandra et al. [6] and Carleton et al. [3, 4] found that many pairs of electoral (decision) problems about the same election sys- tem coincide as sets (i.e., they are collapsing pairs), which had pre- viously gone undetected in the literature. While both members of a collapsing pair certainly have the same decision complexity, there is no guarantee that the associated search problems also have the same complexity. For practical purposes, search problems are more relevant than decision problems. Our work focuses on exploring the relationships between the search versions of collapsing pairs. We do so by giving a framework that relates the complexity of search problems via efficient reduc- tions that transform a solution from one problem to a solution of the other problem on the same input. We not only establish that the known decision collapses carry over to the search model, but also refine our results by determining for the concrete systems plurality, veto, and approval whether collapsing search-problem pairs are polynomial-time computable or NP-hard. 

   more » « less
4. Rage Against the Machine?: Assessing Election Administrators’ Perceptions of Electronic Voting Systems

   https://doi.org/10.33774/apsa-2025-xc6kf  

   Albert, Craig; Murray, Gregg; Schwarzmann, Alex; Hatcher, William (September 2025, APSA Preprints)

   Concerns over foreign and domestic interference have raised questions about the legitimacy of U.S. elections. While research has explored election administration and public views on electronic voting, little attention has been given to election administrators’ perspectives. This study addresses that gap by examining how Georgia election officials perceive the use of electronic pollbooks (e-pollbooks) for voter check-in. The research hypothesizes that administrators view e-pollbooks as enhancing democratic legitimacy and election security. To test this, the paper presents findings from an NSF-funded online survey conducted two months before the 2024 general election. The survey was distributed to all 159 Georgia county election administrators and received IRB approval. It asked respondents to evaluate the security, reliability, ease of use, and fairness of various voter check-in systems, along with broader characteristics of elections in their counties. The results offer insight into how those managing elections assess the tools that support electoral integrity. 

   more » « less
5. Pandering in a (flexible) representative democracy

   Sun, Xiaolin; Masur, Jacob; Abramowitz, Ben; Mattei, Nicholas; Zheng, Zizhan (August 2023, Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence)

   In representative democracies, regular election cycles are supposed to prevent misbehavior by elected officials, hold them accountable, and subject them to the “will of the people." Pandering, or dishonest preference reporting by candidates campaigning for election, undermines this democratic idea. Much of the work on Computational Social Choice to date has investigated strategic actions in only a single election. We introduce a novel formal model of pandering and examine the resilience of two voting systems, Representative Democracy (RD) and Flexible Representative Democracy (FRD), to pandering within a single election and across multiple rounds of elections. For both voting systems, our analysis centers on the types of strategies candidates employ and how voters update their views of candidates based on how the candidates have pandered in the past. We provide theoretical results on the complexity of pandering in our setting for a single election, formulate our problem for multiple cycles as a Markov Decision Process, and use reinforcement learning to study the effects of pandering by single candidates and groups of candidates over many rounds. 

   more » « less