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
Determining Winners in Elections with Absent Votes
An important question in elections is determining whether a candidate can be a winner when some votes are absent. We study this determining winner with absent votes (WAV) problem with elections that take top-truncated ballots. We show that the WAV problem is NP-complete for single transferable vote, Maximin, and Copeland, and propose a special case of positional scoring rule such that the problem can be computed in polynomial time. Our results for top-truncated rankings differ from the results in full rankings as their hardness results still hold when the number of candidates or the number of missing votes are bounded, while we show that the problem can be solved in polynomial time in either case.
more »
« less
- PAR ID:
- 10546020
- Publisher / Repository:
- International Joint Conferences on Artificial Intelligence Organization
- Date Published:
- ISBN:
- 978-1-956792-04-1
- Page Range / eLocation ID:
- 2816 to 2824
- Format(s):
- Medium: X
- Location:
- Jeju, South Korea
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Guruswami, Venkatesan (Ed.)This paper considers elections in which voters choose one candidate each, independently according to known probability distributions. A candidate receiving a strict majority (absolute or relative, depending on the version) wins. After the voters have made their choices, each vote can be inspected to determine which candidate received that vote. The time (or cost) to inspect each of the votes is known in advance. The task is to (possibly adaptively) determine the order in which to inspect the votes, so as to minimize the expected time to determine which candidate has won the election. We design polynomial-time constant-factor approximation algorithms for both the absolute-majority and the relative-majority version. Both algorithms are based on a two-phase approach. In the first phase, the algorithms reduce the number of relevant candidates to O(1), and in the second phase they utilize techniques from the literature on stochastic function evaluation to handle the remaining candidates. In the case of absolute majority, we show that the same can be achieved with only two rounds of adaptivity.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
-
Abstract This article proposes a new statistical model to infer interpretable population-level preferences from ordinal comparison data. Such data is ubiquitous, e.g., ranked choice votes, top-10 movie lists, and pairwise sports outcomes. Traditional statistical inference on ordinal comparison data results in an overall ranking of objects, e.g., from best to worst, with each object having a unique rank. However, the ranks of some objects may not be statistically distinguishable. This could happen due to insufficient data or to the true underlying object qualities being equal. Because uncertainty communication in estimates of overall rankings is notoriously difficult, we take a different approach and allow groups of objects to have equal ranks or berank-clusteredin our model. Existing models related to rank-clustering are limited by their inability to handle a variety of ordinal data types, to quantify uncertainty, or by the need to pre-specify the number and size of potential rank-clusters. We solve these limitations through our proposed BayesianRank-Clustered Bradley–Terry–Luce (BTL)model. We accommodate rank-clustering via parameter fusion by imposing a novel spike-and-slab prior on object-specific worth parameters in the BTL family of distributions for ordinal comparisons. We demonstrate rank-clustering on simulated and real datasets in surveys, elections, and sports analytics.more » « less
-
Abstract In this paper, we consider an application of lot-streaming for processing a lot of multiple items in a hybrid flow shop (HFS) for the objective of minimizing makespan. The HFS that we consider consists of two stages with a single machine available for processing in Stage 1 andmidentical parallel machines in Stage 2. We call this problem a 1 + mTSHFS-LSP (two-stage hybrid flow shop, lot streaming problem), and show it to be NP-hard in general, except for the case when the sublot sizes are treated to be continuous. The novelty of our work is in obtaining closed-form expressions for optimal continuous sublot sizes that can be solved in polynomial time, for a given number of sublots. A fast linear search algorithm is also developed for determining the optimal number of sublots for the case of continuous sublot sizes. For the case when the sublot sizes are discrete, we propose a branch-and-bound-based heuristic to determine both the number of sublots and sublot sizes and demonstrate its efficacy by comparing its performance against that of a direct solution of a mixed-integer formulation of the problem by CPLEX®.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.24963/ijcai.2024/312
