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
Separating and Collapsing Electoral Control Types
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
- Award ID(s):
- 2006496
- NSF-PAR ID:
- 10422854
- Date Published:
- Journal Name:
- Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems
- Volume:
- 22
- ISSN:
- 2523-5699
- Page Range / eLocation ID:
- 1743 - 1751
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
more » « less
We propose a modified spatial‐voting rule to explain why congressional candidates adopt more extreme ideological positions than their constituents' preferences. Our model accepts the standard spatial‐voting model with one critical exception: voters in the same party as a candidate tolerate extremism without imposing an electoral penalty. This, in turn, creates “leeway” for candidates to adopt extreme positions as they increasingly depend on voters from their own party. Electoral simulations demonstrate that a key election‐level implication of this model is that it explains candidate polarization without relying on institutional factors like primary elections. Finally, we show that asymmetry in perceptual bias is one possible mechanism and that real‐world patterns of ideological representation are consistent with our simulation results.
-
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
-
We solve a long-standing challenge to the integrity of votes cast without the supervision of a voting booth: ``{\it improper influence},'' which typically refers to any combination of vote buying and voter coercion. Our approach allows each voter, or their trusted agents (which we call ``{\it hedgehogs}''), to {\it ``nullify''} (effectively cancel) their vote in a way that is unstoppable, irrevocable, and forever unattributable to the voter. In particular, our approach enhances security of online, remote, public-sector elections, for which there is a growing need and the threat of improper influence is most acute. We introduce the new approach, give detailed cryptographic protocols, show how it can be applied to several voting settings, and describe our implementation. The protocols compose a full voting system, which we call {\it {\votexx}}, including registration, voting, nullification, and tallying---using an anonymous communication system for registration, vote casting, and other communication in the system. We demonstrate how the technique can be applied to known systems, including where ballots can be mailed to voters and voters use codes on the ballot to cast their votes online. In comparison with previous proposals, our system makes fewer assumptions and protects against a strong adversary who learns all of the voter's keys. In {\votexx}, each voter has two public-private key pairs. Without revealing their private keys, each voter registers their public keys with the election authority. Each voter may share their keys with one or more hedgehogs. During nullification, the voter, or one or more of their hedgehogs, can interact through the anonymous communication system to nullify a vote by proving knowledge of one of the voter's private keys via a zero-knowledge proof without revealing the private key. We describe a fully decentralizable implementation of {\votexx}, including its public bulletin board, which could be implemented on a blockchain.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
