It remains an open question how to determine the winner of an election given incomplete or uncertain voter preferences. One solution is to assume some probability space for the voting profile and declare that the candidates having the best chance of winning are the (co-)winners. We refer to this interpretation as the Most Probable Winner (MPW). In this paper, we focus on elections that use positional scoring rules, and propose an alternative winner interpretation, 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
This content will become publicly available on June 27, 2024
Ballot Length in Instant Runoff Voting
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
- Award ID(s):
- 2143176
- NSF-PAR ID:
- 10437354
- Date Published:
- Journal Name:
- Proceedings of the AAAI Conference on Artificial Intelligence
- Volume:
- 37
- Issue:
- 5
- ISSN:
- 2159-5399
- Page Range / eLocation ID:
- 5841 to 5849
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Ballot marking devices (BMDs) allow voters to select candidates on a computer kiosk, which prints a paper ballot that the voter can review before inserting it into a scanner to be tabulated. Unlike paperless voting machines, BMDs provide voters an opportunity to verify an auditable physical record of their choices, and a growing number of U.S. jurisdictions are adopting them for all voters. However, the security of BMDs depends on how reliably voters notice and correct any adversarially induced errors on their printed ballots. In order to measure voters' error detection abilities, we conducted a large study (N = 241) in a realistic polling place setting using real voting machines that we modified to introduce an error into each printout. Without intervention, only 40% of participants reviewed their printed ballots at all, and only 6.6% told a poll worker something was wrong. We also find that carefully designed interventions can improve verification performance. Verbally instructing voters to review the printouts and providing a written slate of candidates for whom to vote both significantly increased review and reporting rates-although the improvements may not be large enough to provide strong security in close elections, especially when BMDs are used by all voters. Based on these findings, we make several evidence-based recommendations to help better defend BMD-based elections.more » « less
-
In many real world situations, collective decisions are made using voting and, in scenarios such as committee or board elections, employing voting rules that return multiple winners. In multi-winner approval voting (AV), an agent submits a ballot consisting of approvals for as many candidates as they wish, and winners are chosen by tallying up the votes and choosing the top-k candidates receiving the most approvals. In many scenarios, an agent may manipulate the ballot they submit in order to achieve a better outcome by voting in a way that does not reflect their true preferences. In complex and uncertain situations, agents may use heuristics instead of incurring the additional effort required to compute the manipulation which most favors them. In this paper, we examine voting behavior in single-winner and multi-winner approval voting scenarios with varying degrees of uncertainty using behavioral data obtained from Mechanical Turk. We find that people generally manipulate their vote to obtain a better outcome, but often do not identify the optimal manipulation. There are a number of predictive models of agent behavior in the social choice and psychology literature that are based on cognitively plausible heuristic strategies. We show that the existing approaches do not adequately model our real-world data. We propose a novel model that takes into account the size of the winning set and human cognitive constraints; and demonstrate that this model is more effective at capturing real-world behaviors in multi-winner approval voting scenarios.more » « less
-
With each successive election since at least 1994, congressional elections in the United States have transitioned toward nationalized two-party government. Fewer voters split their tickets for different parties between President and Congress. Regional blocs and incumbency voting --- a key feature of U.S. elections in the latter 20th century --- appear to have given way to strong party discipline among candidates and nationalized partisanship among voters. Observers of modern American politics are therefore tempted to write off the importance of the swing voter, defined here as voters who are indifferent between the two parties and thus likely to split their ticket or switch their party support. By assembling data from historical elections (1950 -- 2020), surveys (2008 -- 2018), and cast vote record data (2010 -- 2018), and through developing statistical methods to analyze such data, I argue that although they comprise a smaller portion of the electorate, each swing voter is disproportionately decisive in modern American politics, a phenomenon I call the swing voter paradox. Historical comparisons across Congressional, state executive, and state legislative elections confirm the decline in aggregate measures of ticket splitting suggested in past work. But the same indicator has not declined nearly as much in county legislative or county sheriff elections (Chapter 1). Ticket splitters and party switchers tend to be voters with low news interest and ideological moderate. Consistent with a spatial voting model with valence, voters also become ticket splitters when incumbents run (Chapter 2). I then provide one of the first direct measures of ticket splitting instate and local office using cast vote records. I find that ticket splitting is more prevalent in state and local elections (Chapter 3). This is surprising given the conventional wisdom that party labels serve as heuristics and down-ballot elections are low information environments. A major barrier for existing studies of the swing voter lies in the measurement from incomplete electoral data. Traditional methods struggle to extract information about subgroups from large surveys or cast vote records, because of small subgroup samples, multi-dimensional data, and systematic missingness. I therefore develop a procedure for reweighting surveys to small areas through expanding poststratification targets (Chapter 4), and a clustering algorithm for survey or ballot data with multiple offices to extract interpretable voting blocs (Chapter 5). I provide open-source software to implement both methods. These findings challenge a common characterization of modern American politics as one dominated by rigidly polarized parties and partisans. The picture that emerges instead is one where swing voters are rare but can dramatically decide the party in power, and where no single demographic group is a swing voter. Instead of entrenching elections into red states and blue states, nationalization may heighten the role of the persuadable voter.more » « less
-
Boardroom Voting: Verifiable Voting with Ballot Privacy Using Low-Tech Cryptography in a Single RoomA boardroom election is an election that takes place in a single room — the boardroom — in which all voters can see and hear each other. We present an initial exploration of boardroom elections with ballot privacy and voter verifiability that use only “low-tech cryptography” without using computers to mark or collect ballots. Specifically, we define the problem, introduce several building blocks, and propose a new protocol that combines these blocks in novel ways. Our new building blocks include “foldable ballots” that can be rotated to hide the alignment of ballot choices with voting marks, and “visual secrets” that are easy to remember and use but hard to describe. Although closely seated participants in a boardroom election have limited privacy, the protocol ensures that no one can determine how others voted. Moreover, each voter can verify that their ballot was correctly cast, collected, and counted, without being able to prove how they voted, providing assurance against undue influence. Low-tech cryptography is useful in situations where constituents do not trust computer technology, and it avoids the complex auditing requirements of end-to-end cryptographic voting systems such as Prêt-à-Voter. This paper’s building blocks and protocol are meant to be a proof of concept that might be tested for usability and improved.more » « less
