The Complexity of Safe Manipulation under Scoring Rules

1 Introduction

Voting is an important tool for preference aggregation in multi-agent systems [Ephrati and Rosenschein, 1997]. However, essentially all voting rules are vulnerable to manipulation, i.e., voters may have an incentive to misrepresent their preferences to get a more desirable outcome [Gibbard, 1973; Satterthwaite, 1975]. This problem becomes especially severe when we assume that manipulating voters can form coalitions in order to coordinate their actions.

To assess the potential impact of coalitional manipulation in the context of multi-agent systems, where both the number of voters and the number of alternatives can be large, one needs to know whether manipulators can easily compute their optimal strategies. For this reason, the algorithmic complexity of coalitional manipulation received considerable attention in the multi-agent research community (see [Faliszewski et al., 2008; 2010; Xia et al., 2009; 2010; Zuckerman et al., 2009]). Indeed, the complexity of coalitional manipulation under the Borda rule is commonly viewed as one of the most interesting open questions in the emerging area of computational social choice.

Now, standard models of manipulation presuppose perfect communication and coordination within the manipulating coalition. Such conditions would be difficult-if not impossible-to attain in reasonably large elections where there could be thousands of agents opting to manipulate. In light of this, [Slinko and White, 2008] have proposed a more plausible model, where the coalition consists of voters with

Mark C. Wilson

Dept. of Computer Science University of Auckland New Zealand

identical preferences, a single coalition member broadcasts a strategic vote, and every voter in the coalition has a choice between casting the proposed strategic vote or voting sincerely.

Since the original manipulator does not know how many followers he will have, manipulation in this sense can be risky: it may happen that, while the manipulation is useful when the number of followers is small, it may result in an undesirable candidate being elected when many coalition members opt to manipulate, or vice versa. Thus, the manipulator may want to identify a strategic vote that never produces an undesirable outcome, no matter how many coalition members choose to follow him. [Slinko and White, 2008] call such a vote a safe strategic vote. The main result of [Slinko and White, 2008] is that the Gibbard-Satterthwaite theorem can be extended to this notion of manipulation: every manipulable voting rule is safely manipulable. The probability of safe manipulation has been recently investigated by [Reyhani and Wilson, 2010].

Just as in the standard model of coalitional manipulation, the practical significance of this form of manipulation depends on whether a safe strategic vote can be computed efficiently. This problem was first studied by [Hazon and Elkind, 2010], who provided polynomial-time algorithms for finding a safe strategic vote, even with weighted voters, under the k-approval rule (where k may depend on the number of candidates-this includes the Plurality and Veto rules) and the Bucklin rule. For Borda, they have shown a coNPhardness result for weighted voters; however, the unweighted case was left as an open question.

In this paper, we continue the investigation of algorithmic complexity of safe strategic voting initiated by [Hazon and Elkind, 2010]. Our main result is a polynomial-time algorithm for finding a safe strategic vote under the Borda rule with unweighted voters. The Borda rule is perhaps the most prominent representative of a large class of voting rules known as scoring rules: recall that a scoring rule for an mcandidate election is described by a vector (α1, . . . , αm) with α1 ≥ . . . ≥ αm, where each candidate receives αi points from each voter that ranks him in position i. Thus, it is natural to ask whether our algorithmic results for Borda extend to other scoring rules. We answer this question in the affirmative, by identifying a large class of scoring rules for which we can find a safe strategic vote in polynomial time. In particular, this is the case for all top-heavy scoring rules, i.e., rules that satisfy α1 - α2 ≥ αi - αi+1 for all i = 2, . . . ,m1, as well as for all rules where the increments αi -αi+1 are all positive and take a small number of different values.

Another interesting class of scoring rules that is not captured by our original approach consists of rules for which the scoring vector consists of a constant number of "blocks". For such rules, we propose a polynomial-time algorithm for finding safe strategic votes that is based on a different idea. Though we have not (yet!) designed polynomial-time algorithms for safe manipulation under all scoring rules, we believe that our results contribute to the understanding of the computational complexity of safe strategic voting.

2 Preliminaries

An election E = (A, V ) is described by a set of alternatives (sometimes called candidates) A, |A| = m, and a set of voters V , |V | = n. Every voter i ∈ V is associated with a preference ordering Ri, which is a total order over A; we will also refer to a voter's preference ordering as his type. For instance, if A = {a, b, c, d}, a voter may rank c first, followed by b, followed by d, followed by a; we will abbreviate the type of this voter as cbda. The list of all voters' preference orderings R = (R1, . . . , Rn) is called the preference profile. A voting correspondence is a mapping F from the set of all preference profiles over A to the set 2A \{∅} of all non-empty subsets of A; the elements of the set F(R) are called the election winners. A voting correspondence F is called a voting rule if there is a unique winner for each preference profile, i.e., |F(R)| = 1 for any preference profile R. A voting correspondence is said to be anonymous if its output does not change when the entries of R are permuted.

A scoring rule Fα is a voting correspondence given by a score vector α = (α1, ..., αm) that satisfies α1 ≥ ... ≥ αm. Under Fα, each candidate a receives ∑i αisi points, where si is the number of voters ranking a in position i. The candidate(s) with the highest score are the election winners. The k-approval rule is the scoring rule with αi = 1 for i ≤ k, αi = 0 for i > k; here k may depend on m. The Borda rule is the scoring rule with the score vector (m-1, m-2, . . . , 0). Note that a scoring rule is defined for a fixed number of candidates m. Since we are interested in asymptotic complexity results, we will abuse notation and use the term "scoring rule" to refer to efficiently computable families of scoring rules, i.e., sets that contain a scoring rule for each value of m and admit an efficient algorithm that, given a value of m, computes the scoring rule corresponding to m. Note that both Borda and k-approval can be viewed as efficiently computable families of scoring rules.

The definitions in the previous paragraph assume that all voters have equal power. A more general setup allows for weighted voters. In a weighted election, we are given a vector w = (w1, . . . ,wn), where wi is the weight of the i-th voter; all weights wi are required to be positive integers given in binary. To determine the winner of a weighted election under a voting rule F, we replace a voter of weight wi with wi unweighted voters and apply F to the resulting profile.

To transform a voting correspondence into a voting rule. we need a tie-breaking rule, i.e., a mapping T : 2A → A

that given a set of tied alternatives S ⊆ A outputs a single alternative T (S) such that T (S) ∈ S. Clearly, if F is a voting correspondence, then the composition of T and F, i.e., the mapping T ◦F given by (T ◦F)(R) = T (F(R)), is a voting rule. A tie-breaking rule T is said to be lexicographic if there exists an ordering ≻ over A such that, for each set S ⊆ A, T(S) is the first element in S according to ≻.

Consider an election E = (A, V ) where the voters' preferences are given by a profile R, and a voting rule F. Fix a voter v of type R, and let M denote the set of all voters in V who also have type R. We are interested in situations where v announces a manipulative vote L ̸= R and a subset of voters in M may decide to vote L, while all the remaining voters vote truthfully. Given a set of voters X, we denote by R-X(L) the preference profile obtained from R by replacing the vote of every voter in X with L. Let w = F(R) be the election winner if everyone votes truthfully. We will say that an alternative a ∈ A is good if it is ranked above w in R; we say that a is bad if it is ranked below w in R. We denote the set of all good alternatives by G, and the set of all bad alternative by B.

The following definition is adapted from [Slinko and White, 2008; Hazon and Elkind, 2010].

Definition 1. Consider an election E = (A, V ) with a preference profile R, a voting rule F, a type R ∈ R, and the set M = {i ∈ V | Ri = R}. Let L be a preference order over A. Then

• L is safe for M if for any X ⊆ M we have F(R-X(L)) ∈ G ∪ {w}.
• L is strategic for M if there exists an X ⊆ M and a g ∈ G such that F(R-X(L)) = g.

A vote is said to be a safe strategic vote if it is both safe and strategic.

Example 1. Consider a Borda election with A = {a, b, c, d}, 5 voters of type bacd, 4 voters of type abcd, 4 voters of type dcab, 2 voters of type badc, 2 voters of type cdba, 1 voter of type bdac, 1 voter of type dacb and 1 voter of type dcba. Under truthful voting, b is first with 35 points, a is second with 33, c and d are tied for last with 26. Suppose that a voter of type abcd opts to manipulate, so G = {a}, B = {c, d}. Consider first the vote adcb. This vote is strategic because if the manipulating coalition is of size 2, b's score will fall to 31, below that of a, while d's score will only rise to 30, so the highest scoring alternative is a, which is in G. However, the vote is not safe: if the manipulating coalition is of size 4, then d will score 34 points and thus the election winner will be an alternative in B.

On the other hand, consider the vote acbd. This time, even if all voters of type abcd manipulate, c's score will only rise to 30, while b's will fall to 31, and the election winner will be a. Thus, the vote acbd is a safe strategic vote.

We will now define the algorithmic problem that is the focus of this work.

EXISTSAFE(F): given an election E = (A, V ) with a preference profile R, a type R, and the set M that consists of all voters of type R in R, does M have a safe strategic vote under a voting rule F?

3 Complexity of EXISTSAFE for Borda

In this section, we study the complexity of EXISTSAFE with unweighted voters under the Borda rule. Almost all of our preliminary results (Lemmas 1-5 and Propositions 1 and 2) hold for all scoring rules, so we state and prove them for an arbitrary fixed scoring rule F. We then present our main result of this section-a polynomial-time algorithm for EXISTSAFE(Borda). In the next section, we show how to extend our proof to a large class of scoring rules.

To simplify the presentation, throughout this section, we assume that ties are broken adversarially to the manipulator, i.e., the tie-breaking rule is lexicographic with respect to the ordering obtained by reversing the manipulator's preference ordering. However, all of our proofs can be adapted to work for arbitrary lexicographic tie-breaking rules; we will comment on this after presenting the main proof.

Throughout this section, we assume that a scoring rule F is fixed, and we are given an election (A, V ) with a preference profile R and a manipulating set M ⊆ V that consists of all voters with a certain type R. We set w = F(R), and let G and B be the candidates ranked above and below w in R, respectively. We will refer to the position of w in R as w's sincere position.

For any X ⊆ M, any a ∈ A and any vote L, we denote by SX(a, L) the score of a in F(R-X(L)); when X = ∅, the quantity SX(a, L) does not depend on L, so we omit L and write S∅(a). Note that the score SX(a, L) is well-defined even if L is a partial vote, i.e., if the positions of some alternatives in L are unknown, as long as the position of a itself is known. Let Lk denote the set of all votes that rank w in position k. We say that an alternative a ∈ A overtakes b ∈ A if a loses to b under truthful voting, but beats it when all voters in M vote L. A position k is said to be promising if there exists an L ∈ Lk such that SX(w, L) > SX(b, L) for all b ∈ B and all X ⊆ M. Observe that if k is a promising position, then there exists a safe vote with w ranked in position k. Further, w's sincere position is necessarily promising.

We start by establishing the existence of an interval of w's positions where strategic votes exist, and an interval where safe votes exist. We then show that if these intervals intersect, we are assured that either the lowest promising position or the highest non-promising position falls into that intersection.

Lemma 1. If there exists a safe strategic vote, then there exists a safe strategic vote in which every good alternative is ranked above every bad alternative.

Proof. Assume we have a safe strategic vote L with some b1 ∈ B ranked above some g1 ∈ G. Construct L′ by swapping b1 with g1. This does not decrease the score of g1, does not increase the score of b1, and does not change the score of any other alternative.

Consider a subset X ⊆ M. Since L is safe, the winner at R-X(L) is either w or some g ∈ G. Since SX(a, L′ ) ≥ SX(a, L) for all a ∈ G ∪ {w} and SX(b, L′ ) ≤ SX(b, L) for all b ∈ B, the winner at R-X(L′ ) is also either w or some g′ ∈ G, so vote L′ is also safe.

Further, since L is strategic, there is a subset Y ⊆ M such that the winner at R-Y (L) is some g ∈ G. Since SY (a, L′ ) ≥ SY (a, L) for all a ∈ G and SY (b, L′ ) ≤

SY (b, L) for all b ∈ B ∪ {w}, the winner at R-Y (L′ ) is also some g′ ∈ G. Thus, L′ is also strategic.

This swapping procedure can be iterated until we obtain a safe strategic vote in which every good alternative is ranked above every bad alternative.

Given this result, from now on we will assume that every vote we deal with has the good alternatives ranked above the bad alternatives.

Lemma 2. If k is a promising position, k - 1 is a promising position.

Proof. Since k is a promising position, there is a vote L ∈ Lk such that SX(w, L) > SX(b, L) for all X ⊆ M and all b ∈ B. Construct L′ from L by swapping w with the alternative directly above it. This does not decrease the score of w, and does not increase the score of any b ∈ B. Hence, we have SX (w, L′ ) > SX(b, L′ ) for all X ⊆ M and all b ∈ B. i.e., L′ is a witness that k - 1 is a promising position.

Lemma 3. If k is a promising position and there is no strategic vote in Lk, there is no strategic vote in Lk-1.

Proof. We prove the contrapositive. Suppose there is a strategic vote L ∈ Lk-1, i.e., there exists a set X ⊆ M and a candidate g ∈ G such that SX(g,L) > SX(a, L) for all a ∈ B ∪ {w}. Consider the vote L′ obtained from L by swapping w with the alternative directly below it. This does not increase the score of w and does not decrease the score of g, so we have SX(g,L′ ) > SX(w, L′ ). Further, since k is a promising position, we can reorder the bad alternatives in L′ (without changing the positions of w and g) so that the resulting vote L′′ satisfies SY (w, L′′ ) > SY (b, L′′ ) for all Y ⊆ M and all b ∈ B. Thus, substituting X = Y , we have SX(g, L′′ ) = SX(g, L′ ) > SX(w, L′ ) = SX(w, L′′ ) > SX (b, L′′ ) for all b ∈ B, so the vote L′′ is also strategic.

Lemma 4. If there is no safe vote in Lk, there is no safe vote in Lk+1.

Proof. We prove the contrapositive. Assume there exists a safe vote L ∈ Lk+1. Consider the alternative a ranked directly above w in L. If a ∈ G, w must be ranked at or above its sincere position, since by Lemma 1 every good alternative is ranked above every bad alternative. Since w's sincere position is promising, Lemma 2 implies that k is a promising position as well, so there must be a safe vote in Lk.

On the other hand, if a ∈ B, construct L′ ∈ Lk by swapping w with a. This swap does not increase the score of any b ∈ B and does not decrease the score of w or any g ∈ G. Therefore, if L ∈ Lk+1 is safe, so is L′ ∈ Lk.

Lemma 5. If k is not a promising position, and some L ∈ Lk is safe, L is also strategic.

Proof. Since k is not promising, there exists some manipulating coalition X ⊆ M such that for some b ∈ B it holds that SX(b, L) > SX(w, L) and hence w is not the winner at R-X(L). Since L is safe, the winner at R-X(L) must be some candidate g ∈ G. Therefore L is strategic.

Lemma 6. If k is a promising position, and Lk contains a vote L such that SX(g, L) > SX(w, L) for some g ∈ G and X ⊆ M, then Lk contains a safe strategic vote.

Proof. Since k is a promising position, we can reorder the bad alternatives in L without changing the positions of g and w so that the resulting vote L′ satisfies SY (w, L′ ) > SY (b, L′ ) for any b ∈ B and any Y ⊆ M, i.e., L′ is safe. Further, substituting X = Y , we obtain SX(g, L′ ) = SX(g,L) > SX(w, L) = SX(w, L′ ) > SX(b, L′ ) for any b ∈ B, so L′ is also strategic.

Proposition 1. Let k be the lowest promising position. If a safe strategic vote exists, then there exists one in Lk ∪ Lk+1.

Proof. We prove the contrapositive. Assume that there are no safe strategic votes in Lk ∪ Lk+1. By Lemma 6, Lk cannot contain a strategic vote, and hence by Lemma 3, there are no strategic votes in Li for any i ≤ k.

Further, by Lemma 5, any safe vote in Lk+1 is strategic. Hence, there can be no safe vote in Lk+1, so by Lemma 4, there are no safe votes in Lj for any j ≥ k+1. Thus, we have argued that if there are no safe strategic votes in Lk ∪ Lk+1, there are no safe strategic votes in Lj for any value of j.

The next lemma shows that, when considering the effects of a manipulation on a given pair of candidates, it is enough to check what happens when all voters in M choose to cast a manipulative vote.

Lemma 7. For any vote L and any candidates x, y ∈ A such that S∅(x) ≤ S∅(y) we have SM(x, L) > SM(y,L) if and only if SX(x, L) > SX(y, L) for some X ⊆ M.

Proof. The "only if" direction is obvious: we can take X = M. To prove the "if" direction, suppose that SX(x, L) > SX(y,L) for some X ⊆ M. Let γ and δ denote, respectively, the change in x's and y's score when one voter in M switches from R to L; we have SZ(x, L) = S∅(x, L) + γ|Z|, SZ(y,L) = S∅(y,L) + δ|Z| for any Z ⊆ M. Since we have S∅(x, L) ≤ S∅(y,L), it follows that γ > δ. Therefore, SM(x, L) = SX(x, L) + γ(|M| - |X|) > SX(y, L) + δ(|M| - |X|) = SM(y, L).

Proposition 2. Testing whether a given position k is promising is in P.

Proof. We know that w's sincere position is promising, so, by Lemma 2, if k ≤ |G| we can output "yes". If k > |G|, we construct a (partial) vote L as follows. We rank w in position k, and place the good alternatives in the top |G| positions in any order. Then we construct a bipartite graph (U, D), where U = B and the set D consists of positions in L unoccupied by the alternatives in G∪{w}. There is an edge from b ∈ B to a position p ∈ D if the partial vote L′ that ranks b in position p satisfies SM(w, L′ ) > SM(b, L′ ). Using Lemma 7, it is easy to check that k is a promising position if and only if (U, D) contains a perfect matching (which can be checked in polynomial time).

The following crucial lemma does not extend to general scoring rules if m ≥ 5 (counterexample omitted for space reasons).

Lemma 8. Under the Borda rule, if k is a promising position and there is no safe strategic vote in Lk, then for any vote L ∈ Lk+1 there is at most one g ∈ G such that SM(g, L) > SM (w, L).

Proof. Assume, for contradiction, that there is no safe strategic vote in Lk, but there exists a vote L ∈ Lk+1 and two good alternatives g1, g2 ∈ G such that SM(g, L) > SM(w, L) for g ∈ {g1, g2}. Since only one of g1 and g2 can be ranked in the top position in L, assume without loss of generality that g2 is ranked second or lower. Construct L′ from L by swapping g2 with the alternative right above it and then swapping w with the alternative right above it. Note that since SM(g2, L) > SM(w, L), g2 is ranked above w in L, and therefore the latter swap does not affect the position of g2. We have L′ ∈ Lk; further, we have SM(w, L′ ) = SM(w, L) + |M| and SM(g2, L′ ) = SM(g2, L) + |M|, because both w and g2 gain one point for every voter that opts to rank them one position higher. Thus, we have SM(g2, L′ ) = SM(g2, L) + |M| > SM(w, L) + |M| = SM(w, L′ ). Since k is a promising position, by Lemma 6 we can transform L′ into a safe strategic vote in Lk, a contradiction.

Theorem 1. EXISTSAFE(Borda) is in P.

Proof. Given Proposition 1, we only need to check votes in Lk and Lk+1, where k is the lowest promising position. First, we use the algorithm of Proposition 2 to find k. Then we try to construct a safe strategic vote in Lk. To this end, for each g ∈ G we construct a vote Lg that ranks g first, ranks w in position k and ranks all other candidates arbitrarily, and check whether SM (g, Lg ) > SM(w, Lg ). If this is the case for some g ∈ G, since k is promising, by Lemma 6 we can transform Lg into a safe strategic vote. If we have SM(g,Lg ) ≤ SM(w, Lg ) for all g ∈ G, then no g ∈ G can overtake w and hence no vote in Lk can be strategic.

Now, suppose that no safe strategic vote has been found in Lk. Then, by Lemma 8, if there is a safe strategic vote L ∈ Lk+1, then there is at most one alternative g such that SM(g, L) > SM(w, L). By Lemma 7, this implies that for any X ⊆ M and any g′ ∈ G \ {g} we have SX(g′ , L) ≤ SX(w, L). Since L is safe, this means that for any X ⊆ M and any b ∈ B it holds that SX(b, L) < max{SX(w, L), SX(g,L)}. Observe also that if we swap g with the alternative ranked in the top position in L (which, by Lemma 1, we can assume to be an alternative in G), the resulting vote will remain safe and strategic. Hence, if Lk+1 contains a safe strategic vote, then there exists some alternative g and a vote L ∈ Lk+1 such that L ranks g first and for any b ∈ B and any X ⊆ M we have SX(b, L) < max{SX(w, L), SX(g,L)}. Thus, to find a safe strategic vote in Lk+1, we proceed as follows. For each g ∈ G we construct a partial vote Lg that ranks g first, followed by other votes in G in an arbitrary order, and ranks w in position k +1 (note that since k+1 is not promising, the sincere position of w is k or higher, so |G| ≤ k - 1, i.e., after the alternatives in G are ranked, the position k + 1 is still unoccupied).

Then, as in the proof of Proposition 2, we construct a bipartite graph (U,D), where U = B and the set D consists of positions in L unoccupied by the alternatives in G ∪ {w}.

There is an edge from b ∈ B to a position p ∈ D if the partial vote L′ that ranks b in position p satisfies SX(b, L) < max{SX(w, L), SX(g, L)} for all X ⊆ M. The latter condition can be verified in polynomial time, since the Borda rule is anonymous and hence it suffices to check this condition for an arbitrary manipulating coalition of size s for s = 1, . . . , |M|. It is easy to see that Lk+1 contains a safe strategic vote if and only if (U, D) contains a perfect matching.

It remains to explain how to extend our algorithm to arbitrary lexicographic tie-breaking rules. This can be achieved by replacing each expression of the form "SX(a, L) > SX(b, L)" by "either (a) SX(a, L) > SX(b, L) or (b) SX(a, L) = SX(b, L) and a ≻ b", where ≻ is the given lexicographic order. Equivalently, assuming that ≻ orders the candidates as am ≻ . . . ≻ a1, we can set ε = 1/(m2 ) and modify the score of each candidate by setting S′X (ai, L) = SX(ai, L) + iε. Since we consider scoring rules with integer entries only, the modified scores of any two candidates are different, and S′X (a, L) > S′X (b, L) if and only if (a) SX(a, L) > SX(b, L) or (b) SX(a, L) = SX(b, L) and a ≻ b. We can now use the modified scores throughout the proof. This argument allows us to assume that ties never occur; the proofs in Section 4 make use of this assumption.

4 Other scoring rules

In this section, we describe polynomial-time algorithms for finding a safe manipulation for several classes of scoring rules. First, we present results that can be obtained by generalizing the arguments used for Borda. Then, we describe an algorithm for scoring rules with a constant number of different scores, which uses a different idea.

4.1 Extensions of Theorem 1

All results of Section 3 except Lemma 8 and Theorem 1 hold for all scoring rules. We will now show that we can prove an analogue of Lemma 8 for a large class of scoring rules, and, as a result, obtain polynomial-time algorithms for finding a safe strategic vote with respect to such rules.

We first introduce additional notation. Given a scoring rule Fα with α = (α1, . . . , αm), let Δαi = αi - αi+1 for i = 1, . . . ,m1, and set I (α) = {Δαi | i = 1, . . . ,m1}. Let Δmin =min{Δαi | i = 1, . . . ,m-1}, Δmax =max{Δαi | i = 1, . . . , m-1}. Set s(t) = ∑tj=1 Δαj , and define r(α) = min{t | s(t) ≥Δmax}.

Let k be the lowest promising position, and suppose that there is no safe strategic vote in Lk. Consider a vote L ∈ Lk+1, and let G∗ (L) = {g ∈ G | SM(g, L) > SM(w, L)}. By Lemma 7, for any alternative g′ ∈ G \ G∗ (L) and any X ⊆ M we have SX(g′ , L) ≤ SX(w, L), i.e., the alternatives in G\G∗ (L) never win. Thus we can move the alternatives in G∗ (L) into top |G∗ (L)| positions (note that since k is the lowest promising position, we have |G∗ (L)| < k): the resulting vote L′ is safe and strategic as long as L is. Therefore, we can limit our attention to the votes L ∈ Lk+1 that rank the alternatives in G∗ (L) in top |G∗ (L)| positions; we will say that any such vote is nice.

Lemma 9. Let k be the lowest promising position, and suppose that there is no safe strategic vote in Lk. Then any nice vote L ∈ Lk+1 satisfies |G∗ (L)| ≤ r(α).

Proof. Let r = r(α) and suppose for the sake of contradiction that |G∗ (L)| > r. Since L is nice, some alternative g is ranked first in L, and some alternative g′ is ranked in position r + 1 in L. We construct the vote L′ by swapping g and g′ in L, and then swapping w with the alternative right above it. The resulting vote L′ is in Lk. By our choice of r, we have s(r) ≥ Δαk. Further, since g′ ∈ G∗ (L), we get SM(g′ , L) > SM(w, L). Therefore, we have

Since k is a promising position, by Lemma 6 we can transform L′ into a safe strategic vote in Lk, a contradiction.

Now, we can modify the algorithm given in the proof of Theorem 1 as follows. Just as in that proof, we find the lowest promising position k and check if there is a safe strategic vote in Lk. If the answer is "no", we try to construct a safe strategic vote in Lk+1. Let r = min{r(α), |G|}. By Lemma 9, we only need to decide which alternatives to put in the top r positions; for any placement of good candidates in top r positions, we rank the remaining good candidates right below them, place w in position k + 1, and then use the bipartite graph-based algorithm to rank the bad candidates, as described in the proof of Theorem 1. There are at most (mr )r! = O(mr ) ways to fill the top r positions. Thus, we obtain the following result.

Theorem 2. EXISTSAFE(Fα) is in P for any scoring rule Fα with r(α) = O(1).

The condition of Theorem 2 is somewhat technical. However, it covers many interesting classes of scoring rules. One such example is the class of all top-heavy scoring rules, i.e., rules that satisfy Δα1 ≥ Δαj for all j, or, equivalently, r(α) = 1. Note that every convex scoring rule (one where Δαi ≥ Δαj when i ≤ j) is top-heavy.

Corollary 1. EXISTSAFE(Fα) is in P for any top-heavy scoring rule Fα.

We can extend Corollary 1 to the case where the score vector consists of "blocks", with entries in each block being equal. Formally, we say that a scoring rule Fα with the vector α = (α1 . . . , αm) is blockwise with respect to a vector β = (β1, . . . , βℓ) if α = (β1, . . . , β1, β2, . . . , β2, . . . , βℓ, . . . , βℓ) with β1 > . . . > βℓ. Let Δβj = βj - βj+1 for j = 1, . . . , ℓ - 1. If Fα is blockwise with respect to β, we say that it is blockwise top-heavy if Δβ1 ≥Δβj for all j.

Given a blockwise top-heavy rule Fα, let q be the size of the first block, i.e., q = |{αi | αi = β1}|. We have, for each i = 1, . . . , m-1, s(q) = ∑qj=1 Δαj = αq+1-αq = Δβ1 ≥ Δαi and hence r(α) ≤ q. This yields the following result.

Corollary 2. EXISTSAFE(Fα) is in P for any blockwise topheavy scoring rule Fα with first block of constant size.

Now, set ρ(α) = ⌈ Δmax Δmin ⌉ if Δmin > 0 and ρ(α) = +∞ otherwise. We have ∑ρ(α) j=1 Δαj ≥ ρ(α)Δmin ≥ Δmax. Thus, r(α) ≤ ρ(α), and we obtain the following result.

Corollary 3. EXISTSAFE(Fα) is in P for any scoring rule Fα such that ρ(α) = O(1).

4.2 Scoring rules with a constant number of blocks

Let R be the manipulator's true preference ordering. For j = 1, . . . , ℓ, let Aj be the set of candidates that obtain βj points fromR. Let ˆ ℓ =max{j | Aj ∩G ̸= ∅}. For j = 1, . . . , ˆ ℓ, let g∗ [j] be the candidate in Aj ∩G that has the highest score under truthful voting, i.e., g∗ [j] = argmaxa∈Aj∩G S∅(a) (recall that by the argument in the end of Section 3 we can assume that there are no ties). Set G∗ = {g∗ [j] | j = 1, . . . , ˆ ℓ}; clearly, |G∗ | ≤ ℓ. We will argue that to find a safe strategic vote with w in a non-promising position, it suffices to consider all possible placements of the candidates in G∗ in top |G∗ | positions.

Lemma 10. Consider two good alternatives g, g′ ∈ G∩Aj and a safe strategic vote L. Let L′ be the vote obtained from L by swapping g and g′ . If S∅(g) ≥ S∅(g′ ) and g′ is ranked above g in L, then L′ is also a safe strategic vote.

Proof. Since L′ ranks g higher than L does, we have SX (g, L′ ) ≥ SX(g, L) for any X ⊆ M. Now, suppose L ranks g′ in position i. Since S∅(g) ≥ S∅(g′ ), we have

Thus, for any X ⊆ M, if some a ∈ B ∪ {w} is beaten by g or g′ at R-X(L), then a is beaten by g at R-X(L′ ), i.e., L′ is a safe strategic vote.

By Lemma 10, when searching for a safe strategic vote, we may limit our attention to the votes that rank g∗ [j] above all other alternatives in Aj ∩G, for all j = 1, . . . , ˆ ℓ. Moreover, for any such vote L we have SX(g∗ [j] , L) ≥ SX(g, L) for any g ∈ G∩Aj and any X ⊆M, i.e., the ranking of alternatives in G \ G∗ is irrelevant to whether L is safe or not. Thus, given a safe strategic vote L, we can move the alternatives in G∗ to the top |G∗ | positions; the resulting vote L′ is also a safe strategic vote. Hence, when ranking the alternatives in G, it suffices to consider all possible assignments of the alternatives in G∗ to the top |G∗ | positions, i.e., at most ℓ! possibilities. Now, substituting G∗ for G∗ (L) in the proof of Theorem 2, we obtain the following result.

Theorem 3. EXISTSAFE(Fα) is in P for any scoring rule Fα that is blockwise with respect to a vector (β1, . . . , βℓ) with ℓ = O(1).

5 Conclusions and FutureWork

We have demonstrated that for many scoring rules, including the classic Borda rule, finding a safe strategic vote is easy. An obvious question is whether these results extend to all scoring rules (our proofs here do not), or whether safe manipulation is hard for some such rules. Other natural research directions include developing polynomial-time algorithms for EXISTSAFE under other common rules such as Copeland and Maximin.

In contrast with the results of [Hazon and Elkind, 2010], our results apply to unweighted voters only. It is tempting to conjecture that some of our proofs could be extended to weighted voters: for instance, the scoring rules considered in Theorem 3 can be viewed as a rather modest extension of kapproval and therefore one might expect that Theorem 3 holds for weighted voters as well. However, the proof of Theorem 8 in [Hazon and Elkind, 2010] suggests that this is unlikely: the construction in that proof essentially shows that both finding a safe strategic vote and checking if a given vote is safe is hard for the scoring rule given by the vector (4, 3, 2, 1, 0, . . . , 0). Identifying scoring rules for which safe manipulation is easy even with weighted voters is an interesting problem as well.

Acknowledgements Lan Yu and Edith Elkind were supported by NRF Singapore under grant NRF RF2009-08 and NTU start-up grant.