We study the complexity of Destructive Shift Bribery. In this problem, we are given an election with a set of candidates and a set of voters (each ranking the candidates from the best to the worst), a despised candidate @math , a budget @math , and prices for shifting @math back in the voters' rankings. The goal is to ensure that @math is not a winner of the election. We show that this problem is polynomial-time solvable for scoring protocols (encoded in unary), the Bucklin and Simplified Bucklin rules, and the Maximin rule, but is NP-hard for the Copeland rule. This stands in contrast to the results for the constructive setting (known from the literature), for which the problem is polynomial-time solvable for @math -Approval family of rules, but is NP-hard for the Borda, Copeland, and Maximin rules. We complement the analysis of the Copeland rule showing W-hardness for the parameterization by the budget value, and by the number of affected voters. We prove that the problem is W-hard when parameterized by the number of voters even for unit prices. From the positive perspective we provide an efficient algorithm for solving the problem parameterized by the combined parameter the number of candidates and the maximum bribery price (alternatively the number of different bribery prices).
A variant of was studied by @cite_38 in their work on testing how robust are winners of given elections. They presented an analysis of the case where every swap has a unit price and they showed that the problem is easy for scoring protocols and for the Condorcet rule. The authors' definition of the Condorcet rule slightly differs from a standard one usually seen in the literature. They assume that if there is no unique Condorcet winner the rule returns the whole set of candidates instead of an empty set (well established as a return value for this case in the literature.) This work is very closely related to ours, but the definition of the problem is somewhat different (more general types of swaps but less general price functions). Very recently @cite_19 studied an analogous setting ( with unit prices) for the case of multiwinner voting rules.
@cite_19 @cite_38
1542680652 2033267281 2083397025 2124837549
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 generalize the idea of a Condorcet winner to committee elections to select a Condorcet committee of size m. As in the case of a Condorcet winner, the Condorcet committee need not exist. We adapt two methods to measure how far a set of m candidates is from being the Condorcet committee. In particular, we generalize a procedure proposed by Lewis Carroll for selecting the candidate that is closest to being the Condorcet winner to allow the selection of a committee. We also generalize Kemeny’s method, which gives a complete transitive ranking, to the selection of committees and show that it is closely related to the first method.We show that these methods lead to some surprising inconsistencies. For example, the committee of size k may be disjoint from the committee of size j or they may overlap in any manner, the committee arising from Carroll’s method may appear at any locations in the Kemeny ranking, and except for two highly restrictive cases, the members of the committee arising from Kemeny’s method may appear at any location in the Kemeny ranking. This paper investigates one of the possible weakening of the (too demanding) assumptions of the Gibbard-Satterthwaite theorem. Namely we deal with a class of voting schemes where at the same time the domain of possible preference preordering of any agent is limited to single-peaked preferences, and the message that this agent sends to the central authority is simply its ‘peak’ — his best preferred alternative. In this context we have shown that strategic considerations justify the central role given to the Condorcet procedure which amounts to elect the ‘median’ peak: namely all strategy-proof anonymous and efficient voting schemes can be derived from the Condorcet procedure by simply adding some fixed ballots to the agent's ballots (with the only restriction that the number of fixed ballots is strictly less than the number of agents). We investigate two systems of fully proportional representation suggested by Chamberlin & Courant and Monroe. Both systems assign a representative to each voter so that the "sum of misrepresentations" is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these "minimax" versions of classical rules appeared to be still NP-hard. We investigated the parameterized complexity of winner determination of the two classical and two new rules with respect to several parameters. Here we have a mixture of positive and negative results: e.g., we proved fixed-parameter tractability for the parameter the number of candidates but fixed-parameter intractability for the number of winners. For single-peaked electorates our results are overwhelmingly positive: we provide polynomial-time algorithms for most of the considered problems. The only rule that remains NP-hard for single-peaked electorates is the classical Monroe rule.