An official website of the United States government
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
Election with Bribe-Effect Uncertainty: A Dichotomy Result
We consider the electoral bribery problem in computational social choice. In this context, extensive studies have been carried out to analyze the computational vulnerability of various voting (or election) rules. However, essentially all prior studies assume a deterministic model where each voter has an associated threshold value, which is used as follows. A voter will take a bribe and vote according to the attacker's (i.e., briber's) preference when the amount of the bribe is above the threshold, and a voter will not take a bribe when the amount of the bribe is not above the threshold (in this case, the voter will vote according to its own preference, rather than the attacker's). In this paper, we initiate the study of a more realistic model where each voter is associated with a willingness function, rather than a fixed threshold value. The willingness function characterizes the likelihood a bribed voter would vote according to the attacker's preference; we call this bribe-effect uncertainty. We characterize the computational complexity of the electoral bribery problem in this new model. In particular, we discover a dichotomy result: a certain mathematical property of the willingness function dictates whether or not the computational hardness can serve as a deterrence to bribery attackers.
more »
« less
- Award ID(s):
- 2004096
- PAR ID:
- 10184367
- Date Published:
- Journal Name:
- International Joint Conference on Artificial Intelligence
- Page Range / eLocation ID:
- 158 to 164
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)A boardroom election is an election with a small number of voters carried out with public communications. We present BVOT, a self-tallying boardroom voting protocol with ballot secrecy, fairness (no tally information is available before the polls close), and dispute-freeness (voters can observe that all voters correctly followed the protocol). BVOT works by using a multiparty threshold homomorphic encryption system in which each candidate is associated with a set of masked primes. Each voter engages in an oblivious transfer with an untrusted distributor: the voter selects the index of a prime associated with a candidate and receives the selected prime in masked form. The voter then casts their vote by encrypting their masked prime and broadcasting it to everyone. The distributor does not learn the voter's choice, and no one learns the mapping between primes and candidates until the audit phase. By hiding the mapping between primes and candidates, BVOT provides voters with insufficient information to carry out effective cheating. The threshold feature prevents anyone from computing any partial tally---until everyone has voted. Multiplying all votes, their decryption shares, and the unmasking factor yields a product of the primes each raised to the number of votes received. In contrast to some existing boardroom voting protocols, BVOT does not rely on any zero-knowledge proof; instead, it uses oblivious transfer to assure ballot secrecy and correct vote casting. Also, BVOT can handle multiple candidates in one election. BVOT prevents cheating by hiding crucial information: an attempt to increase the tally of one candidate might increase the tally of another candidate. After all votes are cast, any party can tally the votes.more » « less
-
null (Ed.)The computational study of election problems generally focuses on questions related to the winner or set of winners of an election. But social preference functions such as Kemeny rule output a full ranking of the candidates (a consensus). We study the complexity of consensus-related questions, with a particular focus on Kemeny and its qualitative version Slater. The simplest of these questions is the problem of determining whether a ranking is a consensus, and we show that this problem is coNP-complete. We also study the natural question of the complexity of manipulative actions that have a specific consensus as a goal. Though determining whether a ranking is a Kemeny consensus is hard, the optimal action for manipulators is to simply vote their desired consensus. We provide evidence that this simplicity is caused by the combination of election system (Kemeny), manipulative action (manipulation), and manipulative goal (consensus). In the process we provide the first completeness results at the second level of the polynomial hierarchy for electoral manipulation and for optimal solution recognition.more » « less
-
In many parts of the world including the western United States, the allocation of water is governed by complex water laws that dictate who receives water, how much they receive, and when. Because these rules are generally based on the seniority of water rights, they are not necessarily focused on maximizing economic value across the entire economy. The maximization of value from water use economy-wide is a complex optimization problem that must explicitly consider each user’s water demand, willingness to pay (WTP) function, and the feedbacks among users in a coupled natural-human system model. In this study, we distill these complexities into a simple MATLAB® model developed to represent a two-user economy with water-dependent sectors representative of agriculture and industry. We feed the model with realistic values of relative water use, relative willingness to pay, and return flows to explore the relationships among these factors in water-limited systems. We find that the total economic value generated from water-dependent users depends primarily on the total water available in the system. However, for a given volume of water available, economic value is not necessarily maximized when all the water is appropriated to the user with the highest WTP. Rather, total economic value depends on the amount of water available, the relative WTP between the two users, and on the return flows generated from each sector’s water use. While our simple two-user model is a significant abstraction of the complexities inherent in natural systems, our study provides important insights into the coupled natural-human system dynamics of water allocation and use in water-limited environments.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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.24963/ijcai.2019/23
