Ties Matter: Complexity of Voting Manipulation Revisited

1 Introduction

Computational social choice is an actively growing subarea of multiagent systems that provides theoretical foundations for preference aggregation and collective decision-making in multiagent domains. One of the most influential early contributions to this area is the paper by Bartholdi, Tovey, and Trick entitled "The computational difficulty of manipulating an election" [Bartholdi et al., 1989]. In this paper, the authors suggested that computational complexity can serve as a barrier to dishonest behavior by the voters, and proposed classifying voting rules according to how difficult it is to manipulate them. In particular, they argued that such well-known voting rules as Plurality, Borda, Copeland and Maximin are easy to manipulate, yet a variant of the Copeland rule known as second-order Copeland is computationally resistant to manipulation. In a subsequent paper, Bartholdi and Orlin [1991]

Noam Hazon

Robotics Institute Carnegie Mellon University, USA

showed that another well-known voting rule, namely, STV, is NP-hard to manipulate as well.

Since then, the computational complexity of manipulation under various voting rules, either by a single voter or by a coalition of voters, received considerable attention in the literature, both from the theoretical and from the experimental perspective (see, in particular, [Xia et al., 2009; 2010] and the recent survey [Faliszewski and Procaccia, 2010] for the former, and [Walsh, 2009; Davies et al., 2010] for the latter). While it has been argued that worst-case complexity does not provide adequate protection against malicious behavior (see, e.g. [Procaccia and Rosenschein, 2007; Xia and Conitzer, 2008; Friedgut et al., 2008; Isaksson et al., 2010]), determining whether a given voting rule is NP-hard to manipulate is still a natural first step in evaluating its resistance to manipulation in realistic scenarios.

An important property of the voting rules discussed in [Bartholdi et al., 1989] is that they may produce multiple winners, i.e., they are, in fact, voting correspondences (see Section 2 for the formal definitions). It is not immediately clear what it means for manipulation to be successful in such a case. [Bartholdi et al., 1989] take a rather liberal approach: they define a manipulation to be successful if, as a result, the manipulator's preferred candidate is one of the election winners. This approach is equivalent to assuming that ties are broken in favor of the manipulator. Now, a careful examination of the algorithm in [Bartholdi et al., 1989] shows that it works as long as ties are broken either adversarially to the manipulator or according to an arbitrary fixed lexicographic order over the candidates. However, in real-life settings, when an election ends in a tie, it is not uncommon to choose the winner using a tie-breaking rule that is nonlexicographic in nature. Indeed, perhaps the most common approach is to toss a coin, i.e., select the winner uniformly at random among all tied alternatives. A more sophisticated example is provided by the second-order Copeland rule studied in [Bartholdi et al., 1989], which is effectively the Copeland rule combined with a rather involved tie-breaking method; despite its apparent complexity, the second-order Copeland is the voting rule of choice for several organizations [Bartholdi et al., 1989]. Thus, it is natural to ask under what conditions on the tie-breaking rule the voting correspondences considered in [Bartholdi et al., 1989] remain easy to manipulate.

In this paper, we make two contributions towards answering this question. We first consider the randomized tiebreaking rule, which chooses the winner uniformly at random among all tied candidates. Now, to formalize the notion of a successful manipulation under this rule, we need additional information about the manipulator's preferences: knowing the manipulator's preference order is insufficient for determining whether he prefers a tie between his top candidate and his least favorite candidate to his second choice becoming the unique winner. Thus, following [Desmedt and Elkind, 2010], we endow the manipulator with utilities for all candidates, and seek a manipulation that maximizes his expected utility, where the expectation is taken over the random bits used to select the winner. We demonstrate that for all scoring rules such a manipulation can be found in polynomial time. This is also true for Maximin as long as the manipulator's utility function has a special form that is inspired by the notion of manipulation employed in [Bartholdi et al., 1989]: namely, the manipulator values one of the candidates at 1 and the rest of the candidates at 0.

Given these easiness results, it is natural to ask whether all (efficiently computable) tie-breaking rules produce easily manipulable rules when combined with the voting correspondences considered in [Bartholdi et al., 1989]. Now, [Bartholdi et al., 1989] show that for Copeland this is not the case, by proving that the second-order Copeland rule is hard to manipulate. However, prior to our work, no such result was known for other rules considered in [Bartholdi et al., 1989]. Our second contribution is in demonstrating that Maximin and Borda, as well as many families of scoring rules, become hard to manipulate if we allow arbitrary polynomial-time tie-breaking rules; our proof also works for Copeland. One can view these results as a continuation of the line of work suggested in [Conitzer and Sandholm, 2003; Elkind and Lipmaa, 2005], namely, identifying minor tweaks to voting rules that make them hard to manipulate. Indeed, here we propose to "tweak" a voting rule by combining it with an appropriate tie-breaking rule; arguably, such a tweak affects the original rule less than the modifications proposed in [Conitzer and Sandholm, 2003] and [Elkind and Lipmaa, 2005] (i.e., combining a voting rule with a preround or taking a "hybrid" of the rule with itself or another rule).

The rest of the paper is organized as follows. We introduce the necessary notation and definitions in Section 2. Section 3 discusses the algorithm and the formal model of [Bartholdi et al., 1989]. We describe the algorithms for scoring rules and Maximin under randomized tie-breaking in Section 4, and prove our hardness results in Section 5. Section 6 concludes.

2 Preliminaries

An election is specified by a set of candidates C, |C| = m, and a set of voters V = {v1, . . . , vn}, where each voter vi is associated with a linear order Ri over the candidates in C; this order is called vi's preference order. We denote the space of all linear orderings over C by L(C). For readability, we will sometimes denote Ri by ≻i. When a ≻i b for some a, b ∈ C, we say that voter vi prefers a to b. The vector R = (R1, . . . ,Rn), where each Ri is a linear order over C, is called a preference profile. A voting rule F is a mapping that, given a preference profile R over C outputs a candidate c ∈ C; we write c = F(R). Many classic voting rules, such as the ones defined below, are, in fact, voting correspondences, i.e., they map a preference profile R to a non-empty subset S of C. Voting correspondences can be transformed into voting rules using tie-breaking rules. A tie-breaking rule for an election (C, V ) is a mapping T = T (R, S) that for any S ⊆ C, S ̸= ∅, outputs a candidate c ∈ S. We say that a tiebreaking rule T is lexicographic with respect to a preference ordering ≻ over C if for any preference profile R over C and any S ⊆ C it selects the most preferred candidate from S with respect to ≻, i.e., we have T (S) = c if and only if c ≻ a for all a ∈ S \ {c}.

A composition of a voting correspondence F and a tiebreaking rule T is a voting rule T ◦F that, given a preference profile R over C, outputs T(R,F(R)). Clearly, T ◦ F is a voting rule and T ◦ F(R) ∈ F(R).

We will now describe the voting rules (correspondences) considered in this paper. All these rules assign scores to candidates; the winners are the candidates with the highest scores.

Scoring rules Any vector α = (α1, . . . , αm) ∈ Rm with α1 ≥ · · · ≥ αm defines a scoring rule Fα. Under this rule, each voter grants αi points to the candidate it ranks in the i-th position; the score of a candidate is the sum of the scores it receives from all voters. The vector α is called a scoring vector. A scoring rule is said to be faithful if α1 > · · · > αm. We are interested in scoring rules that are succinctly representable; therefore, throughout this paper we assume that the coordinates of α are nonnegative integers given in binary. We remark that scoring rules are defined for a fixed number of candidates. Therefore, we will often consider families of scoring rules, i.e., collections of the form (αm)∞m=1 , where αm = (αm 1 , . . . , αm m). We require such families to be polynomial-time computable, i.e., we only consider families of voting rules (αm)∞m=1 for which there exists a polynomial-time algorithm that given an m ∈ N outputs αm 1 , . . . , αm m. Two well-known examples of polynomialtime computable families of scoring rules are Borda, given by αm = (m - 1, . . . , 1, 0), and k-approval, given by αm i = 1 if i ≤ k, αm i = 0 if i > k. 1-approval is also known as Plurality.

Copeland We say that a candidate a wins a pairwise election against b if more than half of the voters prefer a to b; if exactly half of the voters prefer a to b, then a is said to tie his pairwise election against b. Given a rational value α ∈ [0, 1], under the Copelandα rule each candidate gets 1 point for each pairwise election he wins and α points for each pairwise election he ties.

Maximin The Maximin score of a candidate c ∈ C is equal to the number of votes he gets in his worst pairwise election, i.e., mind∈C\{c} |{i | c ≻i d}|.

Given a preference profile R over a set of candidates C, for any preference order L over C we denote by (R-i, L) the preference profile obtained from R by replacing Ri with L. We say that a voter vi can successfully manipulate an election (C, V ) with a preference profile (R1, . . . , Rn) with respect to a voting rule F if F(R-i, L) ≻i F(R). We will now define the computational problem that corresponds to this notion.

An instance of the F-MANIPULATION problem is given by a set of candidates C, a set of voters V , a preference profile R, and the manipulating voter vi. It is a "yes"-instance if there exists a vote L such that F(R-i, L) ≻i F(R) and a "no"-instance otherwise.

3 The model and the algorithm of Bartholdi, Tovey and Trick

Before we describe the algorithm presented in [Bartholdi et al., 1989], we remark that the definition of successful manipulation given in [Bartholdi et al., 1989] differs from our definition of F-MANIPULATION (which is modeled after the standard social choice definition, see, e.g. [Gibbard, 1973; Satterthwaite, 1975]), even if we assume that F is a voting rule rather than a voting correspondence. Specifically, in [Bartholdi et al., 1989] it is assumed that the manipulator has a preferred candidate p, and his goal is to make p elected; we will refer to this problem as F-MANIPULATION(p). However, a poly-time algorithm for F-MANIPULATION(p) can be converted into a polytime algorithm for F-MANIPULATION: we can run FMANIPULATION(p) on all candidates ranked by the manipulator above the current winner, and pick the best among the candidates for which F-MANIPULATION(p) outputs "yes". Thus, if F-MANIPULATION is hard, F-MANIPULATION(p) is hard, too. Moreover, all of our hardness reductions directly show hardness of both variants of the problem.

The algorithm for F-MANIPULATION(p) proposed in [Bartholdi et al., 1989] assumes that the voting rule assigns scores to all candidates, and the winners are the candidates with the highest scores. Let v be the manipulator, and let p be her preferred candidate. The algorithm places p first, and then fills in the remaining positions in the vote from top to bottom, searching for a candidate that can be placed in the next available position in v's vote so that his score does not exceed that of p. This approach works as long as the rule is monotone and we can determine a candidate's final score given his position in v's vote and the identities of the candidates that v ranks above him. It is not hard to show that Plurality and Borda (and, in fact, all scoring rules), as well as Copeland and Maximin have this property.

We can easily modify this algorithm for the setting where the ties are broken adversarially to the manipulator: in that case, when the manipulator fills a position i in his vote, i > 1, he needs to ensure that the score of the candidate in that position is strictly less than that of p. A similar approach works for an arbitrary lexicographic ordering ≻ over the candidates.

4 Randomized Tie-Breaking Rules

In this section, we consider a very common approach to tiebreaking, namely, choosing the winner uniformly at random among all tied candidates. In this case, knowing the manipulator's preference ordering is not sufficient to determine his optimal strategy. For example, suppose that voter v prefers a to b to c, and by voting strategically he can change the output of the voting correspondence from b to {a, c}. It is not immediately clear if this manipulation is beneficial. Indeed, if v strongly prefers a, but is essentially indifferent between b and c, then the answer is probably positive, but if v strongly dislikes c and slightly prefers a to b, the answer is likely to be negative (of course, this also depends on v's risk attitude).

Thus, to model this situation appropriately, we need to know the utilities that the manipulator assigns to all candidates. Under the natural assumption of risk neutrality, the manipulator's utility for a set of candidates is equal to his expected utility when the candidate is drawn from this set uniformly at random, or, equivalently, to his average utility for a candidate in this set. Since we are interested in computational issues, it is reasonable to assume that all utilities are rational numbers; by scaling, we can assume that all utilities are positive integers given in binary.

Formally, given a set of candidates C, we assume that the manipulator is endowed with a utility function u : C → N. This function can be extended to sets of candidates by setting u(S) = 1 |S| ∑c∈S u(c) for any S ⊆ C. Given a voting correspondence F and an election (C, V ) with a preference profile R, we say that a vote L is optimal for a voter vi ∈ V with a utility function ui : C → N with respect to F combined with the randomized tie-breaking rule if ui(F(R-i, L)) ≥ ui(F(R-i), L′ ) for all L′ ∈ L(C). We say that vi has a successful manipulation if his optimal vote L satisfies ui(F(R-i, L)) > ui(F(R)). In the rest of this section, we will explore the complexity of finding an optimal vote with respect to scoring rules and Maximin.

4.1 Scoring rules

All scoring rules turn out to be easy to manipulate under randomized tie-breaking.

Theorem 4.1 For any election E = (C, V ) with |C| = m, any voter v ∈ V with a utility function u : C → N, and any scoring vector α = (α1, . . . , αm), we can find in polynomial time an optimal vote for v with respect to the scoring rule Fα combined with the randomized tie-breaking rule.

Proof Fix a voter v ∈ V with a utility function u, and let R′ denote the preference profile consisting of all other voters' preferences. Let si denote the score of candidate ci after all voters other than v have cast their vote. Let us renumber the candidates in order of increasing score, and, within each group with the same score, in order of decreasing utility. That is, under the new ordering we have s1 ≤ · · · ≤ sm and if si = sj for some i < j then u(ci) ≥ u(cj). We say that two candidates ci, cj with si = sj belong to the same level. Thus, all candidates are partitioned into h ≤ m levels H1, . . . , Hh, so that if ci ∈ Hk and cj ∈ Hℓ, k < ℓ, then si < sj.

Consider first the vote L0 given by c1 ≻ . . . ≻ cm, and let T be the number of points obtained by the winner(s) in (R′ , L0). We claim that for any L ∈ L(C), in the preference profile (R′ , L) the winner(s) will get at least T points. Indeed, let ci be the last candidate to get T points in (R′ , L0), and suppose that there exists a vote L such that ci gets less than T points in (R′ , L). By the pigeonhole principle, this means that L assigns at least αi points to some cj with j > i, and we have sj + αi ≥ si + αi = T , i.e., some other candidate gets at least T points, as claimed. We will say that a vote L is conservative if the winners' score in (R′ , L) is T .

We will now argue that if L maximizes v's utility, then either L is conservative or it can be chosen so that Fα has a unique winner under (R′ , L). Indeed, suppose that this is not the case, i.e., any vote L that maximizes v's utility is such that the set S = Fα(R′ , L) is of size at least 2, and all candidates in S get T ′ > T points. Let ci be v's most preferred candidate in S; we have u(ci) ≥ u(S). Suppose that L grants αj points to ci. Since we have ci +αj > T , it follows that j < i. Now, consider the vote obtained from L0 by swapping ci and cj. Clearly, all candidates in C\{ci, cj} get at most T points, and ci gets T ′ > T points. Further, cj gets sj +αi ≤ sj +αj ≤ T points. Thus, in this case ci is a unique winner and u(ci) ≥ u(S), a contradiction.

Therefore, to find an optimal manipulation, it suffices to (i) check for each candidate c ∈ C whether c can be made the unique winner with a score that exceeds T and (ii) find an optimal conservative vote. The optimal manipulation can then be selected from the ones found in (i) and (ii).

Step (i) is easy to implement. Indeed, a candidate ci can be made the unique winner with a score that exceeds T if and only if si +α1 > T . To see this, observe that if si +α1 > T , we can swap c1 and ci in L0: ci will get more than T points, and all other candidates will get at most T points. Conversely, if si + α1 ≤ T, then the score of ci is at most T no matter how v votes.

Thus, it remains to show how to implement (ii). Intuitively, our algorithm proceeds as follows. We start with the set of winners produced by L0; we will later show that this set is minimal, in the sense that if it contains x candidates from some level, then for any vote the set of winners will contain at least x candidates from that level. Note also that due to the ordering of the candidates we select the best candidates from each level at this step. We then try to increase the average utility of the winners' set. To this end, we order the remaining candidates by their utility, and try to add them to the set of winners one by one as long as this increases its average utility. We will now give a formal description of our algorithm and its proof of correctness.

Let S0 = Fα(R′ , L0). We initialize S and L by setting S = S0, L = L0. Let ≻∗ be some ordering of the set C that ranks the candidates in S0 first, followed by the candidates in C \ S0 in the order of decreasing utility, breaking ties arbitrarily. We order the candidates from C \ S0 according to ≻∗ , and process the candidates in this ordering one by one. For each candidate ci, we check if u(ci) > u(S); if this is not the case, we terminate, as all subsequent candidates have even lower utility. Otherwise, we check if we can swap ci with another candidate that is currently not in S and receives T -si points from L (so that ci gets T points in the resulting vote). If this is the case, we update L by performing the swap and set S = S ∪ {ci}. We then proceed to the next candidate on the list.

We claim that the vote L obtained in the end of this process is optimal for the manipulator, among all conservative votes. We remark that at any point in time S is exactly the set of candidates that get T points in (R′ , L). Thus, we claim that any conservative vote ˆL satisfies u(Fα(R′ , ˆL)) ≤ u(S).

Assume that this is not the case. Among all optimal conservative votes, we will select one that is most "similar" to L

in order to obtain a contradiction. Formally, let L0 be the set of all optimal conservative votes, and let L1 be the subset of L0 that consists of all votes L′ that maximize the size of the set Fα(R′ , L′ )∩S. The ordering ≻∗ induces a lexicographic ordering on the subsets of C. Let ˆL be the vote such that the set Fα(R′ , ˆL) is minimal with respect to this ordering, over all votes in L1. Set ˆ S = Fα(R′ , ˆL); by our assumption we have u( ˆ S) > u(S).

Observe first that our algorithm never removes a candidate from S: when we want to add ci to S and search for an appropriate swap, we only consider candidates that have not been added to S yet. Also, at each step of our algorithm the utility of the set S strictly increases. These observations will be important for the analysis of our algorithm.

ˆ

The following lemma shows that S \ S is empty.

Proof Suppose ˆ S \ S ̸= ∅, and let ci be a candidate in ˆ S \ S. Suppose that ci appears in the j-th position in our ordering of C \ S0. If our algorithm terminated at or before the j-th step, we have u(ci) < u(S) < u( ˆ S), and hence u( ˆ S \ {ci}) > u( ˆ S), a contradiction to the optimality of ˆL.

Thus, when our algorithm considered ci, it could not find a suitable swap. Since ci ∈ ˆ S, it has to be the case that there exists an entry of the scoring vector that equals T - si; however, when our algorithm processed ci it was unable to place ci in a position that grants T - si points. This could only happen if all candidates that were receiving T -si points from L at that point were in S at that time; denote the set of all such candidates by Bi. Note that all candidates in Bi belong to the same level as ci. Also, all candidates in Bi∩S0 have the same or higher utility than ci, because initially we order the candidates at the same level by their utility, so that L0 grants a higher score to the best candidates at each level. On the other hand, all candidates in Bi \S0 were added to S at some point, which means that they have been processed before ci. Since at this stage of the algorithm we order the candidates by their utility, it means that they, too, have the same or higher utility than ci.

Now, since ˆL grants T - si points to ci, it grants less than T - si points to one of the candidates in Bi. Let ck be any such candidate, and consider the vote ˆL′ obtained from ˆL by swapping ci and ck. Let ˆ S′ = Fα(R′ , ˆL′ ); we have ˆ S′ = ( ˆ S \ {ci}) ∪ {ck}. By the argument above, we have either u(ck) > u(ci) or u(ck) = u(ci). In the former case, we get u( ˆ S′ ) > u( ˆ S). In the latter case, we get u( ˆ S′ ) = u( ˆ S) and | ˆ S′ ∩ S| > | ˆ S ∩ S|. In both cases, we obtain a contradiction to our choice of ˆL.

Thus, we have ˆ S ⊆ S, and it remains to show that S ⊆ ˆ S. We will first show that ˆ S contains all candidates in S0.

Lemma 4.3 We have S0 ⊆ ˆ S.

Proof Suppose that |S0 ∩Hk| = mk for k = 1, . . . , h. We will first show that | ˆ S ∩Hk| ≥ mk for k = 1, . . . , h. Indeed, fix a k ≤ h, and suppose that the first candidate in the k-th level is ci. Then in (R′ , L0) the scores of the candidates in Hk are si +αi, . . . , si +αj for some j ≥ i. If si +αi < T, then mk = 0 and our claim is trivially true for this value of k. Otherwise, by the pigeonhole principle, if it holds that in (R′ , ˆL) less than mk voters in Hk get T points, it has to be the case that at least one candidate in Hk+1∪· · ·∪Hh receives at least αi points from ˆL. However, for any cℓ ∈ Hk+1∪· · ·∪Hh we have sℓ > si, so sℓ+αi > T , a contradiction to our choice of ˆL. ˆ

Now, suppose that S0 ∩ Hk ̸⊆ S ∩ Hk for some k ≤ h, and consider a candidate cℓ ∈ (S0 ∩ Hk) \ ( ˆ S ∩Hk). Since we have argued that | ˆ S ∩Hk| ≥ mk, it must be the case that there also exists a candidate cj ∈ ( ˆ S ∩Hk) \ (S0 ∩Hk). It is easy to see that S0 contains the mk best candidates from Hk, so u(cℓ) ≥ u(cj). The rest of the proof is similar to that of Lemma 4.2: Consider the vote ˆL′ obtained from ˆL by swapping cℓ and cj and let ˆ S′ = Fα(R′ , ˆL′ ). Since cℓ and cj belong to the same level, we have ˆ S′ = ( ˆ S \ {cℓ}) ∪ {ck}. Thus, either u( ˆ S′ ) > u( ˆ S) or u( ˆ S′ ) = u( ˆ S) and | ˆ S′ ∩ S| > | ˆ S ∩ S|. In both cases we get a contradiction. Thus, we have S0 ∩Hk ⊆ ˆ S ∩Hk. Since this holds for every value of k, the proof is complete.

Given Lemma 4.2 and Lemma 4.3, it is easy to complete the proof. Suppose that ˆ S is a strict subset of S. Observe first that for any subset S′ of S there is a vote L′ such that Fα(R′ , L′ ) = S′ : we can simply ignore the candidates that are not members of S′ when running our algorithm, as this only increases the number of "available" swaps at each step. Now, order the candidates in C \ S0 according to ≻∗ . Let ci be the first candidate in this order that appears in S, but not in ˆ S. If there is a candidate cj that appears later in the sequence and is contained in both S and ˆ S, consider the set S′ = ˆ S\{cj}∪{ci}. As argued above, there is a vote L′ such that Fα(R′ , L′ ) = S′ . Now, if u(ci) > u(cj), this set has a higher average utility that ˆ S. Thus, this is a contradiction to our choice of ˆL. On the other hand, if u(cj) = u(ci), then we have u(S′ ) = u( ˆ S), |S ∩ S′ | = |S ∩ ˆ S|, and S′ precedes ˆ S is the lexicographic ordering induced by ≻∗ , a contradiction with the choice of ˆL again. Therefore, none of the candidates in S that appear after ci in the ordering belongs to ˆ S. Now, when we added ci to S, we did so because its utility was higher than the average utility of S at that point. However, by construction, the latter is exactly equal to u( ˆ S). Thus, u( ˆ S ∪ {ci}) > u( ˆ S), a contradiction again. Therefore, the proof is complete.

4.2 Maximin

For Maximin with randomized tie-breaking, we have not been able to design an efficient algorithm for finding an optimal manipulation in the general utility model. However, this problem admits a poly-time algorithm if the manipulator's utility function has a special structure. Specifically, recall that in the model of [Bartholdi et al., 1989] the manipulator's goal is to make a specific candidate p a winner. This suggests that the manipulator's utility can be modeled by setting u(p) = 1, u(c) = 0 for all c ∈ C \ {p}. We will now show that for such utilities there exists a poly-time algorithm for finding an optimal manipulation under Maximin combined with the randomized tie-breaking rule.

Theorem 4.4 If the manipulator's utility function is given by u(p) = 1, u(c) = 0 for c ∈ C \ {p}, the problem of finding an optimal manipulation under Maximin combined with the randomized tie-breaking rule is in P.

Proof sketch We construct a directed graph whose vertices are candidates, and there is an edge from ci to cj if ci is cj's most dangerous opponent. Let sM(c) denote the Maximin score of c. Under the utility function u, our goal is to make p one of the winners and minimize the number of candidates tied with p. This can only be achieved if s(p) ≥ maxi s(ci)- 1; assume that this is indeed the case. We say that a vertex c is purple if s(c) = s(p) + 1, and red if s(c) = s(p). Then the manipulator's goal can be reformulated as follows: order the vertices of the graph so that each purple vertex, and as many red vertices as possible, have an incoming edge from a predecessor. This can be achieved by purely graph-theoretic means, but the algorithm is not straightforward; in particular, it may have to contract and then expand cycles.

5 Hardness results

In this section, we consider deterministic polynomial-time tie-breaking rules, We will first present a specific tie-breaking rule T, and then show that manipulating the composition of this rule with Borda, Copeland or Maximin is NP-hard.

Recall that an instance C of 3-SAT is given by a set of s variables X = {x1, . . . , xs} and a collection of t clauses Cl = {c1, . . . , ct}, where each clause ci ∈ Cl is a disjunction of three literals over X, i.e., variables or their negations; we denote the negation of xi by xi. It is a "yes"-instance if there is a truth assignment for the variables in X such that all clauses in Cl are satisfied, and a "no"-instance otherwise. This problem is known to be hard even if we assume that all literals in each clause are distinct, so from now on we assume that this is the case. Now, given s variables x1, . . . , xs, there are exactly ℓ = (2s 3 ) 3-literal clauses that can be formed from these variables (this includes clauses of the form x1∧x1∧x2). Ordering the literals as x1 < x1 < · · · < xs < xs induces a lexicographic ordering over all 3-literal clauses. Let φi denote the i-th clause in this ordering. Thus, we can encode an instance C of 3-SAT with s variables as a binary string σ(C) of length ℓ, where the i-th bit of σ(C) is 1 if and only if φi appears in C.

We are ready to describe T. Given a set S ⊆ C of candidates, where |C| = m, T first checks if m = ℓ + 2s + 4 for some s > 0 and ℓ = (2s 3 ). If this is not the case, it outputs the lexicographically first candidate in S and stops. Otherwise, it checks whether cm ∈ S and for every i = 1, . . . , s, the set S satisfies |S ∩ {cℓ+2i-1, cℓ+2i}| = 1. If this is not the case, it outputs the lexicographically first candidate in S and stops. If the conditions above are satisfied, it constructs an instance C = (X, Cl ) of 3-SAT by setting X = {x1, . . . , xs}, Cl = {φi | 1 ≤ i ≤ ℓ, ci ∈ S}. Next, it constructs a truth assignment (ξ1, . . . , ξs) for C by setting ξi = ⊤ if cℓ+2i-1 ∈ S, cℓ+2i ̸∈ S and ξi = ⊥ if cℓ+2i-1 ̸∈ S, cℓ+2i ∈ S. Finally, if C(ξ1, . . . , ξs) = ⊤, it outputs cm and otherwise it outputs the lexicographically first candidate in S. Clearly, T is polynomial-time computable, and hence the problem T ◦ F-MANIPULATION is in NP for any polynomial-time computable rule F (and, in particular, for Borda, Maximin and Copeland). In the rest of this section, we will show that T ◦ F-MANIPULATION is NP-hard for all these rules.

In all cases, our argument proceeds as follows. Given an instance C of 3-SAT with s variables, we create an election with m = ℓ + 2s + 4 candidates, where ℓ = (2s 3 ). The manipulator v ranks cm first, followed by cm-1, followed by all the remaining candidates. The voters' preferences are set so that if v votes truthfully, cm-1 wins, so v can only benefit from the manipulation if he can make cm the winner. Moreover, the preferences of the non-manipulators are selected so that (a) the set of candidates in {c1, . . . , cℓ} with the maximum score encodes C, and the manipulator cannot change this without jeopardizing cm's chances of winning; (b) for each pair (cℓ+2i-1, cℓ+2i), i = 1, . . . , s, the manipulator can ensure that exactly one of these candidates has the maximum score, i.e., v can select an arbitrary truth assignment; (c) v can ensure that cm has the maximum score. We remark that constructing an election with these properties is not trivial; in particular, the constructions for Borda, Maximin and Copeland are very different. It follows that any beneficial manipulation corresponds to a satisfying assignment and vice versa. Thus, we obtain the following result.

Theorem 5.1 T ◦ F-MANIPULATION is NP-hard for F ∈ { Borda, Maximin, Copelandα, α ∈ [0, 1]}.

The tie-breaking rule T has the attractive property that to compute the winner, we only need to know the set of tied candidates S. Theorem 5.1 can be generalized to other families of scoring rules, including k-approval, where k is polynomially related to m (i.e., m = poly(k)), using a modified version of T which still has this property. However, the combination of any such tie-breaking rule and Plurality can be shown to be easy to manipulate. Therefore, to prove an analogue of Theorem 5.1 for Plurality, we use a tie-breaking rule that depends on the votes themselves, and not just on S.

Theorem 5.2 There exists a tie-breaking rule T ′ such that T ′ ◦ Plurality-MANIPULATION is NP-complete.

6 Conclusions and FutureWork

We have explored the complexity of manipulating many common voting rules under randomized tie-breaking as well as under arbitrary polynomial-time tie-breaking procedures. Our results for randomized tie-breaking are far from complete, and a natural research direction is to extend them to other voting rules, such as Copeland or Bucklin, as well as to the Maximin rule with general utilities.

Acknowledgments This research was supported by National Research Foundation (Singapore) under grant 2009-08 (Elkind), by NTU SUG (Elkind), by SINGA graduate fellowship (Obraztsova). and by the President of RF grant for leading scientific schools support NSh-5282.2010.1.