We consider the problem of predicting winners in elections, for the case where we are given complete knowledge about all possible candidates, all possible voters (together with their preferences), but where it is uncertain either which candidates exactly register for the election or which voters cast their votes. Under reasonable assumptions, our problems reduce to counting variants of election control problems. We either give polynomial-time algorithms or prove #P-completeness results for counting variants of control by adding deleting candidates voters for Plurality, k-Approval, Approval, Condorcet, and Maximin voting rules. We consider both the general case, where voters' preferences are unrestricted, and the case where voters' preferences are single-peaked.
Another model of predicting election outcomes is that of @cite_0 . They consider a situation where each voter is undecided regarding several possible votes. That is, for each voter we are given several possible preference orders and a probability distribution over these votes. The question is, what is the probability that a designated candidate wins.
@cite_0
2140055348
We investigate the extent to which it is possible to compute the probability of a particular candidate winning an election, given imperfect information about the preferences of the electorate. We assume that for each voter, we have a probability distribution over a set of preference orderings. Thus, for each voter, we have a number of possible preference orderings - we do not know which of these orderings actually represents the preferences of the voter, but for each ordering, we know the probability that it does. For the case where the number of candidates is a constant, we are able to give a polynomial time algorithm to compute the probability that a given candidate will win. We present experimental results obtained with an implementation of the algorithm, illustrating how the [email protected]?s performance in practice is better than its predicted theoretical bound. However, when the number of candidates is not bounded, we prove that the problem becomes #P-hard for the Plurality, k-approval, Borda, Copeland, and Bucklin voting rules. We further show that even evaluating if a candidate has any chance of winning is NP-complete for the Plurality voting rule in the case where voters may have different weights. With unweighted voters, we give a polynomial algorithm for Plurality, and show that the problem is hard for many other voting rules. Finally, we give a Monte Carlo approximation algorithm for computing the probability of a candidate winning in any settings, with an error that is as small as desired. Voting is a way to aggregate individual voters' preferences. Traditionally a voter's preference is represented by a total order on the set of candidates. However, sometimes one may not have complete information about a voter's preference, and in this case, can only model a voter's preference as a partial order. Given this framework, there has been work on computing the possible and necessary winners of a (partial) profile. In this paper, we take a step further, look at sets of questions to ask in order to determine the outcome of such a partial profile. Specifically, we call a set of questions a deciding set for a candidate if the outcome of the vote for the candidate is determined no matter how the questions are answered by the voters, and a possible winning (losing) set if there is a way to answer these questions to make the candidate a winner (loser) of the vote. We discuss some interesting properties about these sets of queries, prove some complexity results about them under some well-known voting rules such as plurality and Borda, and consider their application in vote elicitation. We consider approval voting elections in which each voter votes for a (possibly empty) set of candidates and the outcome consists of a set of k candidates for some parameter k, e.g., committee elections. We are interested in the min-imax approval voting rule in which the outcome represents a compromise among the voters, in the sense that the maximum distance between the preference of any voter and the outcome is as small as possible. This voting rule has two main drawbacks. First, computing an outcome that minimizes the maximum distance is computationally hard. Furthermore, any algorithm that always returns such an outcome provides incentives to voters to misreport their true preferences. In order to circumvent these drawbacks, we consider approximation algorithms, i.e., algorithms that produce an outcome that approximates the minimax distance for any given instance. Such algorithms can be considered as alternative voting rules. We present a polynomial-time 2-approximation algorithm that uses a natural linear programming relaxation for the underlying optimization problem and deterministically rounds the fractional solution in order to compute the outcome; this result improves upon the previously best known algorithm that has an approximation ratio of 3. We are furthermore interested in approximation algorithms that are resistant to manipulation by (coalitions of) voters, i.e., algorithms that do not motivate voters to misreport their true preferences in order to improve their distance from the outcome. We complement previous results in the literature with new upper and lower bounds on strategyproof and group-strategyproof algorithms. A possible winner of an election is a candidate that has, in some kind of incomplete-information election, the possibility to win in a complete extension of the election. The first type of problem we study is the Possible co-Winner with respect to the Addition of New Candidates (PcWNA) problem, which asks, given an election with strict preferences over the candidates, is it possible to make a designated candidate win the election by adding a limited number of new candidates to the election? In the case of unweighted voters we show NP-completeness of PcWNA for a broad class of pure scoring rules. We will also briefly study the case of weighted voters. The second type of possible winner problem we study is Possible Winner co-Winner under Uncertain Voting System (PWUVS and PcWUVS). Here, uncertainty is present not in the votes but in the election rule itself. For example, PcWUVS is the problem of whether, given a set C of candidates, a list of votes over C, a distinguished candidate c ∈ C, and a class of election rules, there is at least one election rule from this class under which c wins the election. We study these two problems for a class of systems based on approval voting, the family of Copelandα elections, and a certain class of scoring rules. Our main result is that it is NP-complete to determine whether there is a scoring vector that makes c win the election, if we restrict the set of possible scoring vectors for an m-candidate election to those of the form (α1,..., αm−4, x1, x2, x3, 0), with xi = 1 for at least one i ∈ 1, 2, 3 . We study the computational complexity of the counting version of the POSSIBLE-WINNER problem for elections. In the POSSIBLE-WINNER problem we are given a profile of voters, each with a partial preference order, and ask if there are linear extensions of the votes such that a designated candidate wins. We also analyze a special case of POSSIBLE-WINNER, the MANIPULATION problem. We provide polynomial-time algorithms for counting manipulations in a class of scoring protocols and in several other voting rules. We show #P-hardness of the counting variant of POSSIBLE-WINNER for plurality and veto and give a simple yet general and practically useful randomized algorithm for a variant of POSSIBLE-WINNER for all voting rules for which a winner can be computed in polynomial time. We consider the problem of manipulating elections by cloning candidates. In our model, a manipulator can replace each candidate c by several clones, i.e., new candidates that are so similar to c that each voter simply replaces c in his vote with a block of these new candidates, ranked consecutively. The outcome of the resulting election may then depend on the number of clones as well as on how each voter orders the clones within the block. We formalize what it means for a cloning manipulation to be successful (which turns out to be a surprisingly delicate issue), and, for a number of common voting rules, characterize the preference profiles for which a successful cloning manipulation exists. We also consider the model where there is a cost associated with producing each clone, and study the complexity of finding a minimum-cost cloning manipulation. Finally, we compare cloning with two related problems: the problem of control by adding candidates and the problem of possible (co)winners when new alternatives can join. We study the complexity of the bribery problem with distance restrictions. In particular, in the bribery problem, we are given an election and a distinguished candidate p, and are asked whether we can make p win not win the election by bribing at most k voters to recast their votes. In the bribery problem with distance restrictions, we require that the votes recast by the bribed voters are close to their original votes. To measure the closeness between two votes, we adopt the prevalent Kendall-Tau distance and the Hamming distance. We achieve a wide range of complexity results for this problem under a variety of voting correspondences, including the Borda, Condorcet, Copelandα for every 0 ≤ e ≤ 1 and Maximin. We present a systematic study of Plurality elections with strategic voters who, in addition to having preferences over election winners, also have secondary preferences, governing their behavior when their vote cannot affect the election outcome. Specifically, we study two models that have been recently considered in the literature: lazy voters, who prefer to abstain when they are not pivotal, and truth-biased voters, who prefer to vote truthfully when they are not pivotal. For both lazy and truth-biased voters, we are interested in their behavior under different tie-breaking rules (lexicographic rule, random voter rule, random candidate rule). Two of these six combinations of secondary preferences and tie-breaking rules have been studied in prior work; for the remaining four, we characterize pure Nash equilibria (PNE) of the resulting strategic games and study the complexity of related computational problems. We then use these results to analyze the impact of different secondary preferences and tie-breaking rules on the election outcomes. Our results extend to settings where some of the voters are non-strategic. The original possible winner problem is: Given an unweighted election with partial preferences and a distinguished candidate c, can the preferences be extended to total ones such that c wins? We introduce a novel variant of this problem in which not some of the voters' preferences are uncertain but some of their weights. Not much has been known previously about the weighted possible winner problem. We present a general framework to study this problem, both for integer and rational weights, with and without upper bounds on the total weight to be distributed, and with and without ranges to choose the weights from. We study the complexity of these problems for important voting systems such as scoring rules, Copeland, ranked pairs, plurality with runoff, and (simplified) Bucklin and fallback voting. Plurality voting is perhaps the most commonly used way to aggregate the preferences of multiple voters. The purpose of this paper is to provide a comprehensive study of people's voting behaviour in various online settings under the Plurality rule. Our empirical methodology consisted of a voting game in which participants vote for a single candidate out of a given set. We implemented voting games that replicate two common real-world voting scenarios: In the first, a single voter votes once after seeing a large pre-election poll. In the second game, several voters play simultaneously, and change their vote as the game progresses, as in small committees. The winning candidate in each game (and hence the subject's payment) is determined using the plurality rule. For each of these settings we generated hundreds of game instances, varying conditions such as the number of voters and their preferences. We show that people can be classified into at least three groups, two of which are not engaged in any strategic behavior. The third and largest group tends to select the natural "default" action when there is no clear strategic alternative. When an active strategic decision can be made that improves their immediate payoff, people usually choose that strategic alternative. Our study has insight for multi-agent system designers in uncovering patterns that provide reasonable predictions of voters' behaviors, which may facilitate the design of agents that support people or act autonomously in voting systems. We study the sensitivity of election outcomes to small changes in voters' preferences. We assume that a voter may err by swapping two adjacent candidates in his vote; we would like to check whether the election outcome would remain the same given up to delta errors. We show that this problem can be viewed as the destructive version of the unit-cost swap bribery problem, and demonstrate that it is polynomial-time solvable for all scoring rules as well as for the Condorcet rule. We are also interested in identifying elections that are maximally robust with respect to a given voting rule. We define the robustness radius of an election with respect to a given voting rule as the maximum number of errors that can be made without changing the election outcome; the robustness of a voting rule is defined as the robustness radius of the election that is maximally robust with respect to this rule. We derive bounds on the robustness of various voting rules, including Plurality, Borda, and Condorcet. We study the control complexity of fallback voting. Like manipulation and bribery, electoral control describes ways of changing the outcome of an election; unlike manipulation or bribery attempts, control actions---such as adding deleting partitioning either candidates or voters---modify the participative structure of an election. Via such actions one can try to either make a favorite candidate win ("constructive control") or prevent a despised candidate from winning ("destructive control"). Computational complexity can be used to protect elections from control attempts, i.e., proving an election system resistant to some type of control shows that the success of the corresponding control action, though not impossible, is computationally prohibitive. We show that fallback voting, an election system combining approval with majority voting, is resistant to each of the common types of candidate control and to each common type of constructive control. Among natural election systems with a polynomial-time winner problem, only plurality and sincere-strategy preference-based approval voting (SP-AV) were previously known to be fully resistant to candidate control, and only Copeland voting and SP-AV were previously known to be fully resistant to constructive control. However, plurality has fewer resistances to voter control, Copeland voting has fewer resistances to destructive control, and SP-AV (which like fallback voting has 19 out of 22 proven control resistances) is arguably less natural a system than fallback voting. Elections involving a large voter population often lead to outcomes that surprise many. A better prediction of the true outcome helps reduce the adverse effect of surprise on the economy of a sizable population. This paper starts from the basic observation that individuals in the underlying population build estimates of the distribution of preferences of the whole population based on their immediate neighbors in the underlying social network. The outcome of the election leads to a surprise if these local estimates contradict the outcome of the election for some fixed voting rule. To get a quantitative understanding, we propose a novel mathematical model of the setting where the individuals in the population and their connections are described by a random graph with connection probabilities that are biased based on the preferences of the individuals. Each individual also has some estimate of the bias in their connections. The connection model is inspired by the homophily effect in social networks. We show that the election outcome leads to a surprise if the discrepancy between the estimated bias and the true bias in the local connections exceeds a certain threshold, and confirm the phenomenon that surprising outcomes are associated only with closely contested elections. We consider large elections with networked voters and compare standard voting rules based on their performance on surprise. Our results show that the rules have different behavior for different parts of the population. It also hints at an impossibility result that any reasonable voting rule will be less surprising for all parts of a population. To attest some of our theoretical predictions, we experiment with the large dataset of UK-EU referendum (a.k.a. Brexit). Many analyses of plurality-rule elections predict the complete coordination of strategic voting, and hence support for only two candidates. Here I suggest that stable multi-candidate support will arise in equilibrium. A group of voters must partially coordinate behind one of two challenging candidates in order to dislodge a disliked incumbent. In a departure from existing models, the popular support for each challenger is uncertain. This support must be inferred from the private observation of informative signals, such as the social communication of preferences throughout the electorate, or the imperfect observation of opinion polls. The uniquely stable voting equilibrium entails only limited strategic voting and hence incomplete coordination. This is due to the surprising presence of negative feedback: an increase in the degree of strategic voting by others reduces the incentives for an individual to vote strategically. The incentive to vote strategically is lower in relatively marginal elections, after controlling for the distance from contention of a trailing preferred challenger. A calibration of the model applied to the UK General Election of 1997 is consistent with the impact of strategic voting and the reported accuracy of voters understanding of the electoral situation. It suggests that nearly 50 seats may have been lost by the Conservative party due to strategic voting. In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable. One could try to avoid manipulation by using protocols where determining a beneficial manipulation is hard. Especially among computational agents, it is reasonable to measure this hardness by computational complexity. Some earlier work has been done in this area, but it was assumed that the number of voters and candidates is unbounded. Such hardness results lose relevance when the number of candidates is small, because manipulation algorithms that are exponential only in the number of candidates (and only slightly so) might be available. We give such an algorithm for an individual agent to manipulate the Single Transferable Vote (STV) protocol, which has been shown hard to manipulate in the above sense. This motivates the core of this article, which derives hardness results for realistic elections where the number of candidates is a small constant (but the number of voters can be large). The main manipulation question we study is that of coalitional manipulation by weighted voters. (We show that for simpler manipulation problems, manipulation cannot be hard with few candidates.) We study both constructive manipulation (making a given candidate win) and destructive manipulation (making a given candidate not win). We characterize the exact number of candidates for which manipulation becomes hard for the plurality, Borda, STV, Copeland, maximin, veto, plurality with runoff, regular cup, and randomized cup protocols. We also show that hardness of manipulation in this setting implies hardness of manipulation by an individual in unweighted settings when there is uncertainty about the others' votes (but not vice-versa). To our knowledge, these are the first results on the hardness of manipulation when there is uncertainty about the others' votes. Multi-winner elections model scenarios where voters must select a fixed-size group of candidates based on their individual preferences. In such scenarios, it is often the case that voters are incentivized to manipulate, i.e. misreport their preferences in order to obtain a better outcome. In this paper, we study the complexity of manipulating multi-winner elections under scoring rules, with a particular focus on the role of tie-breaking rules. We consider both lexicographic tie-breaking rules, which break ties according to a fixed ordering of the candidates, and a natural randomized tie-breaking rule. We describe polynomial-time manipulation algorithms for several special cases of our problem. Specifically, we show that finding a successful manipulation is easy if the underlying voting rule is k-Approval or the number of candidates to be elected is bounded by a constant (for both types of tie-breaking rules), as well as if the manipulator's utility function only takes values in 0, 1 and the ties are broken in the manipulator's favor. Approval voting is a well-known voting procedure for single-winner elections. Voters approve of as many candidates as they like, and the candidate with the most approvals wins (Brams and Fishburn 1978, 1983, 2005). But Merrill and Nagel (1987) point out that there are many ways to aggregate approval votes to determine a winner, justifying a distinction between approval balloting, in which each voter submits a ballot that identifies the candidates the voter approves of, and approval voting, the procedure of ranking the candidates according to their total numbers of approvals. We theoretically and experimentally study voter behavior in a setting characterized by plurality rule and mandatory voting, where voters choose from three options. We are interested in the occurrence of strategic voting in an environment where Condorcet cycles may occur. In particular, we focus on how information about the distribution of preferences affects strategic behavior. We also vary the relative importance of the second preferred option to investigate how this affects the strategic vote. Quantal response equilibrium analysis is used to analyze the game and proves to be a good predictor for the experimental data. Our results indeed show that strategic voting arises, the extent of which depends on (i) the availability of information; (ii) the relative importance of the intermediate candidate; (iii) the electorate's relative support for one's preferred candidate; and (iv) the relative position of the plurality-supported candidate in a voter's preference ordering. Our results show that information serves as a coordination device where strategic voting does not harm the plurality-preferred candidate's chances of winning. The theoretical guarantees provided by voting have distinguished it as a prominent method of preference aggregation among autonomous agents. However, unlike humans, agents usually assign each candidate an exact utility, whereas an election is resolved based solely on each voter's linear ordering of candidates. In essence, the agents' cardinal (utility-based) preferences are embedded into the space of ordinal preferences. This often gives rise to a distortion in the preferences, and hence in the social welfare of the outcome. In this paper, we formally define and analyze the concept of distortion. We fully characterize the distortion under different restrictions imposed on agents' cardinal preferences; both possibility and strong impossibility results are established. We also tackle some computational aspects of calculating the distortion. Ultimately, we argue that, whenever voting is applied in a multiagent system, distortion must be a pivotal consideration. We study sincere-strategy preference-based approval voting (SP-AV), a system proposed by Brams and Sanver [1] and here adjusted so as to coerce admissibility of the votes (rather than excluding inadmissible votes a priori), with respect to procedural control. In such control scenarios, an external agent seeks to change the outcome of an election via actions such as adding deleting partitioning either candidates or voters. SP-AV combines the voters' preference rankings with their approvals of candidates, where in elections with at least two candidates the voters' approval strategies are adjusted – if needed – to approve of their most-preferred candidate and to disapprove of their least-preferred candidate. This rule coerces admissibility of the votes even in the presence of control actions, and hybridizes, in effect, approval with pluralitiy voting. We prove that this system is computationally resistant (i.e., the corresponding control problems are NP-hard) to 19 out of 22 types of constructive and destructive control. Thus, SP-AV has more resistances to control than is currently known for any other natural voting system with a polynomial-time winner problem. In particular, SP-AV is (after Copeland voting, see [2, 3]) the second natural voting system with an easy winner-determination procedure that is known to have full resistance to constructive control, and unlike Copeland voting it in addition displays broad resistance to destructive control (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)