An official website of the United States government
Instant runoff voting (IRV) is an increasingly-popular alternative to traditional plurality voting in which voters submit rankings over the candidates rather than single votes. In practice, elections using IRV often restrict the ballot length, the number of candidates a voter is allowed to rank on their ballot. We theoretically and empirically analyze how ballot length can influence the outcome of an election, given fixed voter preferences. We show that there exist preference profiles over k candidates such that up to k-1 different candidates win at different ballot lengths. We derive exact lower bounds on the number of voters required for such profiles and provide a construction matching the lower bound for unrestricted voter preferences. Additionally, we characterize which sequences of winners are possible over ballot lengths and provide explicit profile constructions achieving any feasible winner sequence. We also examine how classic preference restrictions influence our results—for instance, single-peakedness makes k-1 different winners impossible but still allows at least Ω(√k). Finally, we analyze a collection of 168 real-world elections, where we truncate rankings to simulate shorter ballots. We find that shorter ballots could have changed the outcome in one quarter of these elections. Our results highlight ballot length as a consequential degree of freedom in the design of IRV elections.
more »
« less
The Moderating Effect of Instant Runoff Voting
Instant runoff voting (IRV) has recently gained popularity as an alternative to plurality voting for political elections, with advocates claiming a range of advantages, including that it produces more moderate winners than plurality and could thus help address polarization. However, there is little theoretical backing for this claim, with existing evidence focused on case studies and simulations. In this work, we prove that IRV has a moderating effect relative to plurality voting in a precise sense, developed in a 1-dimensional Euclidean model of voter preferences. We develop a theory of exclusion zones, derived from properties of the voter distribution, which serve to show how moderate and extreme candidates interact during IRV vote tabulation. The theory allows us to prove that if voters are symmetrically distributed and not too concentrated at the extremes, IRV cannot elect an extreme candidate over a moderate. In contrast, we show plurality can and validate our results computationally. Our methods provide new frameworks for the analysis of voting systems, deriving exact winner distributions geometrically and establishing a connection between plurality voting and stick-breaking processes.
more »
« less
- Award ID(s):
- 2143176
- PAR ID:
- 10529838
- Publisher / Repository:
- AAAI
- Date Published:
- Journal Name:
- Proceedings of the AAAI Conference on Artificial Intelligence
- Volume:
- 38
- Issue:
- 9
- ISSN:
- 2159-5399
- Page Range / eLocation ID:
- 9909 to 9917
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
It remains an open question how to determine the winner of an election when voter preferences are incomplete or uncertain. One option is to assume some probability space over the voting profile and select the Most Probable Winner (MPW) -- the candidate or candidates with the best chance of winning. In this paper, we propose an alternative winner interpretation, selecting the Most Expected Winner (MEW) according to the expected performance of the candidates. We separate the uncertainty in voter preferences into the generation step and the observation step, which gives rise to a unified voting profile combining both incomplete and probabilistic voting profiles. We use this framework to establish the theoretical hardness of MEW over incomplete voter preferences, and then identify a collection of tractable cases for a variety of voting profiles, including those based on the popular Repeated Insertion Model (RIM) and its special case, the Mallows model. We develop solvers customized for various voter preference types to quantify the candidate performance for the individual voters, and propose a pruning strategy that optimizes computation. The performance of the proposed solvers and pruning strategy is evaluated extensively on real and synthetic benchmarks, showing that our methods are practical.more » « less
-
null (Ed.)We present Phrase-Verified Voting, a voter-verifiable remote voting system easily assembled from commercial off-the-shelf software for small private elections. The system is transparent and enables each voter to verify that the tally includes their ballot selection without requiring any understanding of cryptography. This system is an example of making voter verification usable. The paper describes the system and an experience with it in fall 2020, to vote remotely in promotion committees in a university. Each voter fills out a form in the cloud with their selection $$V$$ for each race and a two-word passphrase $$P$$. The system generates a verification prompt of the $(V,P)$ pairs and a tally of the votes, organized to help visualize how the votes add up. After the polls close, each voter verifies that this table lists their $(V,P)$ pair and that the tally is computed correctly. The system is especially appropriate for any small group making sensitive decisions. Because the system would not prevent a coercer from demanding that their victim use a specified passphrase, it is not designed for applications where such malfeasance would be likely or go undetected. Results from 43 voters show that the system performed effectively for its intended purpose, and introduced users to the concept of voter-verified elections. Compared to the commonly-used alternatives of paper ballots or voting by email, voters found the system easier to use, and that it provided greater privacy and outcome integrity.more » « less
-
We solve a long-standing challenge to the integrity of votes cast without the supervision of a voting booth: ``improper influence,'' which we define as any combination of vote buying and voter coercion. In comparison with previous proposals, our system is the first in the literature to protect against a strong adversary who learns all of the voter's keys---we call this property ``extreme coercion resistance.'' Our approach allows each voter, or their trusted agents (which we call ``hedgehogs''), to ``nullify'' (effectively cancel) their vote in a way that is unstoppable and irrevocable, and such that the nullification action is forever unattributable to that voter or their hedgehog(s). We demonstrate the security of VoteXX in the {universal composability} model. Additionally we provide concrete implementations of sub-protocols---including inalienable authentication, decentralized bulletin boards, and anonymous communication channels---that are usually left as abstract assumptions in the literature. As in many other coercion-resistant systems, voters are authorized to vote with public-private keys. Each voter registers their public keys with the Election Authority (EA) in a way that convinces the EA that the voter has complete knowledge of their private keys. Voters concerned about losing their private keys can themselves, or by delegating to one or more hedgehog(s), monitor the bulletin board for malicious ballots cast with their keys, and can act to nullify these ballots in a privacy-preserving manner with zero-knowledge proofs. In comparison with previous proposals, our system makes fewer assumptions and protects against a stronger adversary. For example, votexx makes none of the following assumptions made by previous systems: the voter must complete registration before being coerced; the election will not close before the voter can cast a ballot after coercion; the voter needs to generate a fake password to evade coercion; and the voter knows an honest Election Authority official.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1609/aaai.v38i9.28852
