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
Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences
We consider two-alternative elections where voters' preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. As a special case, our model captures the common scenario where voters can be categorized into three types: those who always prefer one alternative, those who always prefer the other, and those contingent voters whose preferences depends on the state. In this setting, even if every voter is a contingent voter, agents voting according to their private information need not result in the adoption of the universally preferred alternative, because the signals can be systematically biased.We present a mechanism that elicits and aggregates the private signals from the voters, and outputs the alternative that is favored by the majority. In particular, voters truthfully reporting their signals forms a strong Bayes Nash equilibrium (where no coalition of voters can deviate and receive a better outcome).
more »
« less
- NSF-PAR ID:
- 10316791
- Date Published:
- Journal Name:
- Advances in Neural Information Processing Systems 34 pre-proceedings (NeurIPS 2021)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the voting game where agents' preferences are endogenously decided by the information they receive, and they can collaborate in a group. We show that strategic voting behaviors have a positive impact on leading to the "correct" decision, outperforming the common non-strategic behavior of informative voting and sincere voting. Our results give merit to strategic voting for making good decisions. To this end, we investigate a natural model, where voters' preferences between two alternatives depend on a discrete state variable that is not directly observable. Each voter receives a private signal that is correlated with the state variable. We reveal a surprising equilibrium between a strategy profile being a strong equilibrium and leading to the decision favored by the majority of agents conditioned on them knowing the ground truth (referred to as the informed majority decision): as the size of the vote goes to infinity, every ε-strong Bayes Nash Equilibrium with ε converging to 0 formed by strategic agents leads to the informed majority decision with probability converging to 1. On the other hand, we show that informative voting leads to the informed majority decision only under unbiased instances, and sincere voting leads to the informed majority decision only when it also forms an equilibrium.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
-
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
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
