text: 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.
  @cite_38: Schulze voting is a recently introduced voting system enjoying unusual popularity and a high degree of real-world use, with users including the Wikimedia foundation, several branches of the Pirate Party, and MTV. It is a Condorcet voting system that determines the winners of an election using information about paths in a graph representation of the election. We resolve the complexity of many electoral control cases for Schulze voting. We find that it falls short of the best known voting systems in terms of control resistance, demonstrating vulnerabilities of concern to some prospective users of the system.
  @cite_14: 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)
  @cite_33: 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.
  @cite_36: There are different ways for an external agent to influence the outcome of an election. We concentrate on ''control'' by adding or deleting candidates. Our main focus is to investigate the parameterized complexity of various control problems for different voting systems. To this end, we introduce natural digraph problems that may be of independent interest. They help in determining the parameterized complexity of control for different voting systems including Llull, Copeland, and plurality voting. Devising several parameterized reductions, we provide an overview of the parameterized complexity of the digraph and control problems with respect to natural parameters such as adding deleting only a bounded number of candidates or having only few voters.
  @cite_29: 
  @cite_32: Walsh [23,22], [9], and [20] studied various voting systems empirically and showed that they can often be manipulated effectively, despite their manipulation problems being NP-hard. Such an experimental approach is sorely missing for NP-hard control problems, where control refers to attempts to tamper with the outcome of elections by adding delet-ing partitioning either voters or candidates. We experimentally tackle NP-hard control problems for Bucklin and fallback voting, which among natural voting systems with efficient winner determination are the systems currently known to display the broadest resistance to control in terms of NP-hardness [12,11]. We also investigate control resistance experimentally for plurality voting, one of the first voting systems analyzed with respect to electoral control [1,18]. Our findings indicate that NP-hard control problems can often be solved effectively in practice. Moreover, our experiments allow a more fine-grained analysis and comparison--across various control scenarios, vote distribution models, and voting systems--than merely stating NP-hardness for all these control problems.
  @cite_24: Elections are a central model in a variety of areas. This paper studies parameterized computational complexity of five control problems in the Maximin election. We obtain the following results: constructive control by adding candidates is W[2]-hard with respect to the parameter ''number of added candidates''; both constructive and destructive control by adding deleting voters are W[1]-hard with respect to the parameter ''number of added deleted voters''.
  @cite_45: Schulze's rule and ranked pairs are two Condorcet methods that both satisfy many natural axiomatic properties. Schulze's rule is used in the elections of many organizations, including the Wikimedia Foundation, the Pirate Party of Sweden and Germany, the Debian project, and the Gento Project. Both rules are immune to control by cloning alternatives, but little is otherwise known about their strategic robustness, including resistance to manipulation by one or more voters, control by adding or deleting alternatives, adding or deleting votes, and bribery. Considering computational barriers, we show that these types of strategic behavior are NP-hard for ranked pairs (both constructive, in making an alternative a winner, and destructive, in precluding an alternative from being a winner). Schulze's rule, in comparison, remains vulnerable at least to constructive manipulation by a single voter and destructive manipulation by a coalition. As the first such polynomialtime rule known to resist all such manipulations, and considering also the broad axiomatic support, ranked pairs seems worthwhile to consider for practical applications.
  @cite_49: Voting systems are common tools in a variety of areas. This paper studies parameterized computational complexity of control of Plurality, Condorcet and Approval voting systems, respectively. The types of controls considered include adding or deleting candidates or voters, under constructive or destructive setting. We obtain the following results: (1) constructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter ''number of added candidates'', (2) destructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter ''number of added candidates'', (3) constructive control by adding voters in Condorcet voting is W[1]-hard with respect to the parameter ''number of added voters'', (4) constructive control by deleting voters in Condorcet voting is W[1]-hard with respect to the parameter ''number of deleted voters'', (5) constructive control by adding voters in Approval voting is W[1]-hard with respect to the parameter ''number of added voters'', and (6) constructive control by deleting voters in Approval voting is W[2]-hard with respect to the parameter ''number of deleted voters''.
  @cite_20: Some voting schemes that are in principle susceptible to control are nevertheless resistant in practice due to excessive computational costs; others are vulnerable. We illustrate this in detail for plurality voting and for Condorcet voting.
  @cite_17: Although manipulation and bribery have been extensively studied under weighted voting, there has been almost no work done on election control under weighted voting. This is unfortunate, since weighted voting appears in many important natural settings. In this paper, we study the complexity of controlling the outcome of weighted elections through adding and deleting voters. We obtain polynomial-time algorithms, NP-completeness results, and for many NP-complete cases, approximation algorithms. In particular, for scoring rules we completely characterize the complexity of weighted voter control. Our work shows that for quite a few important cases, either polynomial-time exact algorithms or polynomial-time approximation algorithms exist.
summary: From a technical standpoint, our research continues the line of work on the complexity of control. This line of work was initiated by Bartholdi, Tovey, and Trick @cite_20 , and then continued by Hemaspaandra, Hemaspaandra, and Rothe (who introduced the destructive cases), by (who considered multiwinner rules and who generalized the idea of the constructive and destructive cases), by Faliszewski, Hemaspaandra, and Hemaspaandra (who introduced multimode model of control), by Faliszewski, Hemaspaandra, and Hemaspaandra @cite_17 (who were first to consider control for weighted elections), by Rothe and Schend @cite_32 (who initiated the empirical study of the complexity of control problems), and by many other researchers, who provided results for specific voting rules and who introduced various other novel means of studying control problems (see, e.g., the following papers @cite_36 @cite_14 @cite_33 @cite_49 @cite_24 @cite_38 @cite_45 ; we also point the readers to the survey @cite_29 ).