We study the computational complexity of committee selection problem for several approval-based voting rules in the presence of outliers. Our first result shows that outlier consideration makes committee selection problem intractable for approval, net approval, and minisum approval voting rules. We then study parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter, the number of candidates outside the committee), the number of outliers (and its dual parameter, the number of non-outliers). For net approval and minisum approval voting rules, we provide a dichotomous result, resolving the parameterized complexity of this problem for all subsets of five natural parameters considered (by showing either FPT or W[1]-hardness for all subsets of parameters). For the approval voting rule, we resolve the parameterized complexity of this problem for all subsets of parameters except one. We also study approximation algorithms for this problem. We show that there does not exist any alpha(.) factor approximation algorithm for approval and net approval voting rules, for any computable function alpha(.), unless P=NP. For the minisum voting rule, we provide a pseudopolynomial (1+eps) factor approximation algorithm.
The notion of outliers is quite prominent in the literature pertaining to closest strings, where the usual setting is that we are given @math strings over some alphabet @math , and the task is to find a string @math that minimizes either the maximum Hamming distance from any string, or the sum of its Hamming distances from all strings. In the context of social choice theory, the notion of outliers are intimately related to manipulation and control of election by removing voters and candidates @cite_0 @cite_43 @cite_42 @cite_12 @cite_27 @cite_38 @cite_17 @cite_8 @cite_14 @cite_5 @cite_2 @cite_24 .
@cite_38 @cite_14 @cite_8 @cite_42 @cite_0 @cite_43 @cite_27 @cite_24 @cite_2 @cite_5 @cite_12 @cite_17
119722335 2126893170 2123942784 1972375916 2161392628 2003296459 2570387407 2167625605 2065691221 1529060712 236418988 1644945789
3 Voting 17 3.1 Voting Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.1 Scoring Rules . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1.2 Condorcet Extensions . . . . . . . . . . . . . . . . . . . 19 3.1.3 Other Rules . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.1 The Gibbard-Satterthwaite Impossibility . . . . . . . . . . 24 3.2.2 Restricted Domains of Preferences . . . . . . . . . . . . . 24 3.2.3 Computational Hardness of Manipulation . . . . . . . . . 26 3.2.4 Probabilistic Voting Rules . . . . . . . . . . . . . . . . . 29 3.2.5 Irresolute Voting Rules . . . . . . . . . . . . . . . . . . . 30 3.3 Possible and Necessary Winners . . . . . . . . . . . . . . . . . . 31 Although recent years have seen a surge of interest in the computational aspects of social choice, no specific attention has previously been devoted to elections with multiple winners, e.g., elections of an assembly or committee. In this paper, we characterize the worst-case complexity of manipulation and control in the context of four prominent multiwinner voting systems, under different formulations of the strategic agent's goal. In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks on elections-- attempts to improve the election outcome by such actions as adding deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i.e., multimode) attack. We do so to more realistically capture the richness of real-life settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks. By constructing polynomialtime multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time. 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. 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. We show how computational complexity might protect the integrity of social choice. We exhibit a voting rule that efficiently computes winners but is computationally resistant to strategic manipulation. It is NP-complete for a manipulative voter to determine how to exploit knowledge of the preferences of others. In contrast, many standard voting schemes can be manipulated with only polynomial computational effort. 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. In particular, 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. There are different ways for an external agent to influence the outcome of an election. We concentrate on "control" by adding or deleting candidates of an election. 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 votings. Devising several parameterized reductions, we provide a parameterized complexity overview of the digraph and control problems with respect to natural parameters. The concept of distance rationalizability has several applications within social choice. In the context of voting, it allows one to define ("rationalize") voting rules via a consensus class (roughly, a set of elections in which it is obvious who should win) and a distance function: namely, a candidate is said to be an election winner if it is ranked first in one of the nearest (with respect to the given distance) consensus elections. It is known that many classic voting rules can be represented in this manner. In this paper, we provide new results on distance rationalizability of several well-known voting rules such as all scoring rules, Approval, Young's rule and Maximin. We also show that a previously published proof of distance rationalizability of Young's rule is incorrect: the consensus notion and the distance function used in that proof give rise to a voting rule that is similar to---but distinct from---the Young's rule. Finally, we demonstrate that some voting rules cannot be rationalized via certain notions of consensus. To the best of our knowledge, these are the first non-distance-rationalizability results for voting rules. Although recent years have seen a surge of interest in the computational aspects of social choice, no attention has previously been devoted to elections with multiple winners, e.g., elections of an assembly or committee. In this paper, we fully characterize the worst-case complexity of manipulation and control in the context of four prominent multi-winner voting systems. Additionally, we show that several tailor-made multi-winner voting schemes are impractical, as it is NP-hard to select the winners in these schemes. We provide an overview of some recent progress on the complexity of election systems. The issues studied include the complexity of the winner, manipulation, bribery, and control problems.