News outlets, surveyors, and other organizations often conduct polls on social networks to gain insights into public opinion. Such a poll is typically started by someone on a social network who sends it to her friends. If a person participates in the poll, the poll information gets published on her wall, which in turn enables her friends to participate, and the process continues. Eventually, a subset of the population participates in the poll, and the pollster learns the outcome of that poll. We initiate the study of a new but natural type of election control in such online elections. We study how difficult/easy it is to sway the outcome of such polls in one's favor/against (aka constructive vs destructive) by any malicious influencer who nudges/bribes people for seemingly harmless actions like non-participation. These questions are important from the standpoint of studying the power of resistance of online voting against malicious behavior. The destructive version is also important to quantify the robustness of the winner of an online voting. We show that both problems are computationally intractable even if the election is over only two candidates and the influencer has an infinite amount of money to spend (that is, every voter can be persuaded to not participate). We strengthen this result by proving that the computational task remains substantially challenging even if the underlying network is a tree. Finally, we show that there is a polynomial-time algorithm for the constructive version of the problem when we have O(1) candidates, and the treewidth of the underlying graph is O(1); the algorithm for the destructive version does not even need to assume O(1) number of candidates. Hence, we observe that the destructive version is computationally easier than the constructive version.

Standard (offline) control scenarios in elections (such as adding, deleting, or partitioning either voters or candidates) have been studied for many voting systems, natural and less natural ones, and the related control problems have been classified in terms of their complexity. However, for one of the most important natural voting systems, the Borda Count, only a few such complexity results are known. We reduce the number of missing cases by pinpointing the complexity of three control scenarios for Borda elections, including some that arguably are among the practically most relevant ones. We also study online candidate control, an interesting dynamical, partial-information model due to Hemaspaandra et al. (2012a), who mainly focused on general complexity bounds by constructing artificial voting systems—only recently they succeeded in classifying four problems of online candidate control for one natural voting system: sequential plurality (Hemaspaandra et al. 2016). We settle the complexity of another four natural cases: constructive and destructive online control by deleting and adding candidates in sequential Borda elections.

An important problem in computational social choice theory is the complexity of undesirable behavior among agents, such as control, manipulation, and bribery in election systems. These kinds of voting strategies are often tempting at the individual level but disastrous for the agents as a whole. Creating election systems where the determination of such strategies is difficult is thus an important goal. An interesting set of elections is that of scoring protocols. Previous work in this area has demonstrated the complexity of misuse in cases involving a fixed number of candidates, and of specific election systems on unbounded number of candidates such as Borda. In contrast, we take the first step in generalizing the results of computational complexity of election misuse to cases of infinitely many scoring protocols on an unbounded number of candidates. Interesting families of systems include $k$-approval and $k$-veto elections, in which voters distinguish $k$ candidates from the candidate set. Our main result is to partition the problems of these families based on their complexity. We do so by showing they are polynomial-time computable, NP-hard, or polynomial-time equivalent to another problem of interest. We also demonstrate a surprising connection between manipulation in election systems and some graph theory problems.

Preference aggregation in a multiagent setting is a central issue in both human and computer contexts. In this paper, we study in terms of complexity the vulnerability of preference aggregation to destructive control. That is, we study the ability of an election's chair to, through such mechanisms as voter/candidate addition/suppression/partition, ensure that a particular candidate (equivalently, alternative) does not win. And we study the extent to which election systems can make it impossible, or computationally costly (NP-complete), for the chair to execute such control. Among the systems we study--plurality, Condorcet, and approval voting--we find cases where systems immune or computationally resistant to a chair choosing the winner nonetheless are vulnerable to the chair blocking a victory. Beyond that, we see that among our studied systems no one system offers the best protection against destructive control. Rather, the choice of a preference aggregation system will depend closely on which types of control one wishes to be protected against. We also find concrete cases where the complexity of or susceptibility to control varies dramatically based on the choice among natural tie-handling rules.

Control and bribery are settings in which an external agent seeks to influence the outcome of an election. Constructive control of elections refers to attempts by an agent to, via such actions as addition/deletion/partition of candidates or voters, ensure that a given candidate wins. Destructive control refers to attempts by an agent to, via the same actions, preclude a given candidate's victory. An election system in which an agent can sometimes affect the result and it can be determined in polynomial time on which inputs the agent can succeed is said to be vulnerable to the given type of control. An election system in which an agent can sometimes affect the result, yet in which it is NP-hard to recognize the inputs on which the agent can succeed, is said to be resistant to the given type of control. Aside from election systems with an NP-hard winner problem, the only systems previously known to be resistant to all the standard control types were highly artificial election systems created by hybridization. This paper studies a parameterized version of Copeland voting, denoted by Copeland^\alpha, where the parameter \alpha is a rational number between 0 and 1 that specifies how ties are valued in the pairwise comparisons of candidates. In every previously studied constructive or destructive control scenario, we determine which of resistance or vulnerability holds for Copeland^\alpha for each rational \alpha, 0 \leq \alpha \leq 1. In particular, we prove that Copeland^{0.5}, the system commonly referred to as ``Copeland voting,'' provides full resistance to constructive control, and we prove the same for Copeland^\alpha, for all rational \alpha, 0 < \alpha < 1. Among systems with a polynomial-time winner problem, Copeland voting is the first natural election system proven to have full resistance to constructive control. In addition, we prove that both Copeland^0 and Copeland^1 (interestingly, Copeland^1 is an election system developed by the thirteenth-century mystic Llull) are resistant to all standard types of constructive control other than one variant of addition of candidates. Moreover, we show that for each rational \alpha, 0 \leq \alpha \leq 1, Copeland^\alpha voting is fully resistant to bribery attacks, and we establish fixed-parameter tractability of bounded-case control for Copeland^\alpha. We also study Copeland^\alpha elections under more flexible models such as microbribery and extended control, we integrate the potential irrationality of voter preferences into many of our results, and we prove our results in both the unique-winner model and the nonunique-winner model. Our vulnerability results for microbribery are proven via a novel technique involving min-cost network flow.

Voting on multiple related issues is an important and difficult problem. The key difficulty is that the number of alternatives is exponential in the number of issues, and hence it is infeasible for the agents to rank all the alternatives. A simple approach is to vote on the issues one at a time, in sequence; however, a drawback is that the outcome may depend on the order in which the issues are voted upon and decided, which gives the chairperson some control over the outcome of the election because she can strategically determine the order. While this is undeniably a negative feature of sequential voting, in this paper we temper this judgment by showing that the chairperson's control problem is, in most cases, computationally hard.