The Nonmanipulative Vote-Deficits of Voting Rules

Abstract

We introduce a new parameter which we call the nonmanipulative vote-deficit (NMVD) for single-winner voting rules. In particular, the NMVD of a voting rule at an election is the minimum number of votes needed to be added to transform this election into a nonmanipulable one yet without changing the winner. A voting rule has a bounded NMVD if the NMVDs of this rule at all elections are bounded from above by a constant. We show that the prevalent voting rules Borda, Plurality with Runoff, and Maximin have bounded NMVDs. In addition, we show that the NMVD of r-Approval, r-Veto, and Bucklin at every election can be bounded by a function of the number of candidates. For Copeland$^{\alpha }$, though that in general the NMVDs at elections cannot be bounded by a function of the number of candidates, we show that many special elections are still expected to have small NMVDs. Many of our results are tight.

1 Introduction

We consider single-winner voting where every voter holds a linear preference over a given set of candidates, and a voting rule is applied to select one candidate as the winner. An election is a tuple consisting of a set of candidates and a multiset of preferences (votes) over the candidates. We put forward the notion of nonmanipulative vote-deficit (NMVD). In particular, we define the NMVD of a voting rule at an election as the minimum number of votes needed to be added so that

• (1) the resulting election yields the same winner as the original one; and

• (2) it is impossible to change the preference of any one voter in the election to improve the result in favor of the voter.

A voting rule has a bounded NMVD if the NMVDs of this rule at all elections are bounded from above by a constant.

Our notion of NMVD is related to the classic problem Constructive/Destructive Coalition Manipulation (CCM/DCM) which has been extensively and intensively studied in the literature [1, 4, 6, 16, 24,25,26]. Recall that in the CCM (resp. DCM) problem, we are given an election and an integer k (the number of manipulators), and the question is whether we can add k new votes (cast by the manipulators) so that a distinguished candidate wins (resp. does not win) the election. Instead of changing the winner in a particular way, our notion is concerned with enhancing the winning status of the current winner by adding the minimum number of votes, assuming that everyone is self-interested and may manipulate the election as long as doing so makes herself better off.

The NMVD of a voting rule at an election is related to the margin of victory of the rule, which is defined as the minimum number of votes needed to be changed in order to change the winner (who is the new winner does not matter) [8, 14, 23]. It is easy to see that the margin of victory of a voting rule at an election is at least 2 if and only if the NMVD of this rule at the election is 0, and the margin of victory of a voting rule at an election is 1 if and only if the NMVD of this rule at the election is at least 1. It should be pointed out that the problem of computing margin of victory has been also studied under the name Destructive Bribery (see [11] for further details on Destructive Bribery).

NMVD is also related to the renowned Gibbard-Satterthwaite (G-S) theorem [12, 20], which implies that every nondictorial (deterministic) and onto voting rule is manipulable at some election, i.e., for every voting rule there exists at least one election such that at least one voter can benefit from misreporting her true preference under this rule. Since the publication of this fundamental result, much effort has been made to circumvent the G-S theorem, including the adoption of randomized rules, the restriction of preference domains, the establishment of the complexity barrier against manipulations, etc. [3,4,5, 7, 13, 17, 19]. Our notion more or less provides a different approach to prohibiting manipulations via the operation of adding dummy votes.

Our Contributions. We show that several commonly used voting rules have their NMVDs bounded by two. Moreover, for many voting rules, a constant number of votes satisfying the two conditions given above can be constructed without knowing the exact votes. What we need to know is merely the candidate set and who is the current winner, or head-to-head comparisons among candidates, or the majority graph of the election, depending on which rules are considered and which bounds are used.

Motivated by the fact that in many real-world applications the number of candidates is often small, for voting rules whose NMVDs are not bounded, we also investigate their NMVDs in this special case and obtain many interesting results.

For most of the upper bound results, we also show their tightness by providing concrete elections at which the NMVD of a voting rule matches these bounds.

Due to space limitations, proofs of several theorems (labeled by $\star$) are omitted.

2 Preliminaries

For an integer $i>0$, let [i] denote the set of all positive integers not greater than i.

An election is a tuple (C, V) where C is a set of candidates and V is a multiset of votes. Each vote $\succ \in V$ is defined as a linear order over C, indicating the preference of the vote where a candidate a is preferred to another candidate b if a is ordered before b, i.e., $a\succ b$. Sometimes we omit the notation of a vote if we are only interested in the preference. For instance, when we say a vote with the preference $a~b~c$ we mean a vote who prefers a to b to c. The position of a candidate in a vote is the number of candidates ordered before this candidate plus one. A voting rule $\varphi$ maps each nonempty election (C, V) to a candidate $\varphi (C, V)\in C$ which is called the winner. For an election (C, V) and two candidates a and b in C, let $n_{(C, V)}(a, b)$ be the number of votes preferring a to b. We drop (C, V) from the notation when it is clear which election is considered. We say that a beats b if $n(a,b)>n(b,a)$, and a ties b if $n(a, b)=n(b, a)$. We consider the following voting rules.

Table 1. Some important positional scoring rules. For r-Approval and r-Veto we have that $0<r<m$. 1-Approval is also referred to as Plurality in the literature.

• Positional scoring rules. A positional scoring rule is characterized by a function mapping a nonnegative integer m to a vector $\langle \beta _1, \beta _2,\dots ,\beta _m\rangle$ of m rational numbers such that $\beta _i\ge \beta _{i+1}$ for each $i\in [m-1]$. Here, m is considered as the number of candidates. Each vote gives $\beta _i$ points to the candidate in the i-th position. The winner is a candidate with the maximum total score. Table 1 summarizes some important positional scoring rules.

• Plurality with runoff (PluRun). This rule has two stages. First, all candidates except the first and the second candidates with the maximum Plurality score(s) are eliminated. (We may need some tie-handling rule to select exactly two candidates in this stage) In the second stage, between the two candidates surviving the first stage, the one who is preferred by a majority of votes is selected as the winner. (We may also need to break ties in this stage if the two candidates are tied)

• Maximin. The Maximin score of a candidate c is defined as $\min _{c'\in C\setminus \{c\}} n(c, c')$. The winner is a candidate with the maximum score.

• Copeland $^{\alpha }$ ($0\le \alpha \le 1$). For a candidate $c\in C$, let $n^{\text {B}}(c)=|\{c'\in C\setminus \{c\}: n(c,c')>n(c',c)\}|$ and $n^{\text {T}}(c)=|\{c'\in C\setminus \{c\}: n(c,c')=n(c', c)\}|$. The Copeland$^{\alpha }$ score of c is $n^{\text {B}}(c)+\alpha \cdot n^{\text {T}}(c)$. The winner is a candidate with the maximum score.

• Bucklin. The Bucklin score of a candidate $c\in C$ is defined as the minimum integer i such that a majority of votes rank c in the top-i positions. A candidate with the minimum score is the winner.

In the above descriptions, when several candidates have the same maximum score (for all except PluRun and Bucklin) or have the minimum score (for Bucklin), a particular tie-breaking rule is used to determine the winner. In this paper, unless stated otherwise, ties are broken by a predefined order $\lhd$ over the candidates. This is one of the most important tie-breaking rules studied in the literature (see, e.g., [9]). However, many of our results also hold no matter which tie-breaking rules are used.

Manipulation. Let (C, V) be an election and $w=\varphi (C, V)$ be the winner of (C, V) with respect to a voting rule $\varphi$. We say that a vote $\succ \in V$ is manipulable (or is a manipulative vote) at (C, V) with respect to $\varphi$ if there exists a candidate $c\in C\setminus \{w\}$ and a linear order $\succ '$ over C such that $c\succ w$ and c becomes the winner under $\varphi$ if $\succ$ is replaced with $\succ '$ in V. More precisely, we call $\succ$ a c-manipulator at (C, V) with respect to $\varphi$.

For an election $E=(C, V)$ and a manipulative vote $\succ \in V$, let $\mathsf{{C}}_{\varphi }(\succ , E)$ be the set of candidates $c\in C$ such that $\succ$ is a c-manipulator at E with respect to $\varphi$. For a nonmanipulative vote $\succ$, we define $\mathsf{{C}}_{\varphi }(\succ , E)=\emptyset$. Let $\mathsf{{C}}_{\varphi }(E)=\bigcup _{\succ \in V}\mathsf{{C}}_{\varphi }(\succ , E)$.¹

Nonmanipulative Vote-Deficit. For an election (C, V) and a voting rule $\varphi$, the NMVD of $\varphi$ at (C, V), denoted $\textsf {NMVD}_{(C, V)}(\varphi )$, is defined as the minimum integer $\ell$ such that there exists a multiset U of $\ell$ votes over C such that  $\varphi (C, V)=\varphi (C, V\cup U)$ and no vote in V is manipulable at $(C, V\cup U)$. In particular, we say that the NMVD of $\varphi$ is bounded if there exists a constant t such that for all elections (C, V) it holds that $\textsf {NMVD}_{(C, V)}(\varphi )\le t$.

3 NMVDs in General

In this section, we study the NMVDs of many well-studied voting rules in the general case. Our main results are summarized in Table 2.

First, it is easy to check that the NMVD of PluRun is at most six no matter which tie-breaking rule is used in the first stage. Suppose that w and b are the two candidates surviving the first stage. Then, after adding three votes ranking b in the top, and adding three votes ranking w in the top, the winner remains unchanged and, moreover no manipulative vote exists.

Table 2. The upper bounds of NMVDs of many voting rules. Here, m and n are the numbers of candidates and votes, respectively. Results marked by $\checkmark$ hold regardless of the tie-breaking rules, and marked by $\heartsuit$ mean that the bounds are tight.

Observation 1 . The NMVD of PluRun is bounded by six and, moreover, this holds no matter which tie-breaking rule is used in the first stage.

The result of the above observation is tight, in the sense that there exist tie-breaking rules and elections at which the NMVD of PluRun is exactly six, as illustrated by the following example.

Example 1

Consider an election with three candidates a, b, w, and with 30 votes defined as follows (number of votes: preferences):

In the first stage, ties are broken so that (1) when all candidates have the same highest Plurality score, b and w survive the first stage; (2) when w has the unique highest Plurality score, and a and b have the same Plurality score, a is the one who survives the first stage with w; (3) when a or b has the highest Plurality score and the other two have the same Plurality score, a and b survive the first stage. In the second stage, ties are broken so that when w ties b, w is the winner. One can check that the NMVD of PluRun at this election is six.

If we use a fixed linear order to break ties in the first stage, the NMVD of PluRun decreases to four.

Theorem 1

The NMVD of PluRun is at most four if in the first stage a predefined linear order is used to break ties.

The result of the above lemma is also tight, which can be illustrated by an election obtained from the one in Example 1 by adding one more vote with the preference $w~b~a$ and one more vote with the preference $b~a~w$, and the tie-breaking order is $a\lhd b\lhd w$ for the first stage. Now we study the NMVD of Borda.

Theorem 2

The NMVD of Borda is bounded by two for all tie-breaking rules.

Proof

Let (C, V) be an election with $w\in C$ being its Borda winner. Additionally, let $(c_1,c_2,\dots , c_{m-1})$ be any arbitrary but fixed order of $C\setminus \{w\}$. Let U be a set consisting of two votes with respectively the preferences $w~c_1~c_2~\cdots ~c_{m-1}$ and $w~c_{m-1}~c_{m-2}~\cdots ~c_1$. The addition of these two votes increases the score gap between w and every other candidate by exactly m. We claim that in the election $(C, V\cup U)$ no vote in V is manipulable. Assume for contradiction that there is a c-manipulator in V for some $c\in C \setminus \{w\}$. Recall that c is ranked before w in this vote. Hence, changing this vote can only decrease the score gap between w and c by at most $m-2$, implying that c has Borda score smaller than that of w no matter how this vote is changed, a contradiction.    $\square$

The upper bound of NMVD for Borda in Theorem 2 is tight, in the sense that no matter which tie-breaking rules are used, there are elections at which the NMVD of Borda is exactly two, as shown in the following example.

Example 2

Consider an election (C, V) where $C=\{c_1, c_2, c_3, c_4\}$. We have the following votes in V. In particular, for each $c_i\in C$, where $i\in [4]$, there are 12 votes in V as follows ($(c_x, c_y, c_z)$ is the order over $C\setminus \{c_i\}$ such that $x<y<z$):

In total, V consists of 48 votes. Obviously, all candidates have the same Borda score 72. Without loss of generality, assume that $c_i$ for some $i\in [4]$ is selected as the Borda winner according to a tie-breaking rule. It is easy to see that there is at least one manipulator in this election. For instance, the vote with the preference $c_x~c_y~c_i~c_z$ could be changed into $c_y~c_x~c_i~c_z$ to make the candidate $c_y$ the winner. Hence, to preclude manipulation we need to add at least one additional vote. However, we show that adding one vote does not do the job. First, as we request that the original winner should remain as the winner after adding additional votes in our model, the added vote must rank $c_i$ in the top. Without loss of generality, assume that the candidate in the second position of the added vote is $c_x$. Then, a vote with the preference $c_z~c_x~c_i~c_y$ is a manipulator, because by changing it into $c_x~c_z~c_y~c_i$, the candidate $c_x$ becomes the Borda winner.

Notice that to find the two votes in the proof of Theorem 2, we need only to know the candidate set C and the current winner. Now we study r-Approval.

Theorem 3

For $\varphi$ being r-Approval, NMVD of $\varphi$ at every election $E=(C, V)$ is bounded by $\left\lceil \frac{|\mathsf{{C}}_{\varphi }(E)|}{m-r}\right\rceil \le \left\lceil \frac{m-1}{m-r}\right\rceil$, where $m=|C|$.

Proof

Let $\lhd$ be the predefined tie-breaking order for E. Let w be the current r-Approval winner of E with respect to $\varphi$. Let $b=\left\lceil \frac{|\mathsf{{C}}_{\varphi }(E)|}{m-r}\right\rceil$. We construct b votes as follows. In particular, we partition $\mathsf{{C}}_{\varphi }(E)$ into b subsets denoted by $C(w,1), C(w,2),\dots , C(w, b)$ such that every subset contains at most $m-r$ candidates. Then, we create b votes where the i-th vote ranks w in the top, and ranks all candidates in C(w, i) and any arbitrary $m-r-|C(w,i)|$ candidates in $C\setminus (C(w, i)\cup \{w\})$ in the last $m-r$ positions. The relative orders among candidates that are not specified do not matter. Let $E'$ be the election obtained from E by adding the above votes. Apparently, w remains as the winner in $E'$. In the following, we show that none of V is a manipulative vote at $E'$.

For the sake of contradiction, assume that there is a c-manipulator $\succ \in V$ where $c\in C\setminus \{w\}$ in $E'$. Observe that, when ties are broken by a predefined linear order over the candidates, if a vote is not a c-manipulator in E, it cannot be a c-manipulator in $E'$ too. In other words, it holds that $\mathsf{{C}}_{\varphi }(E')\subseteq \mathsf{{C}}_{\varphi }(E)$. As a consequence, c must be from $\mathsf{{C}}_{\varphi }(E)$. Then, note that all added votes approve w but at least one of them does not approve c (the vote corresponding to C(w, i) such that $c\in C(w, i)$). Therefore, adding the above b votes increases the score gap between w and c by at least one. Observe also that because $\succ$ is a c-manipulator, $c\succ w$ holds and, moreover, either both w and c are ranked in the top-r positions, or both are ranked in the last $m-r$ positions in $\succ$. Hence, changing $\succ$ decreases the score gap between w and c by at most one. The proof proceeds by distinguishing between two cases.

Case 1. Candidates c and w have the same r-Approval score in E.

In this case, as w is the winner in E, it holds that $w\lhd c$. By the above discussion, w receives at least one more point than c in $E'$. However, as changing $\succ$ only decreases the score gap between w and c by at most one, no matter how $\succ$ is changed, c has at most the same score as w in $E'$. Given $w\lhd c$, we know that $\succ$ cannot be a c-manipulator in $E'$, a contradiction.

Case 2. The winner w has one more point than that of c in E.

In this case, w has at least two more points than c in the new election $E'$. Changing $\succ$ only decreases the score gap between w and c by at most one, as discussed above. Therefore, no matter how $\succ$ is changed, c has at least one fewer point than w in $E'$, contradicting that $\succ$ is a c-manipulator in $E'$ too.    $\square$

In the proof of Theorem 3, we can replace $\mathsf{{C}}_{\varphi }(E)$ by $C\setminus \{w\}$ to get the bound $\left\lceil \frac{m-1}{m-r}\right\rceil$. An advantage of using $C\setminus \{w\}$ is that in this case, to construct the desired added votes, we need only to know the current winner other than calculating $\mathsf{{C}}_{\varphi }(E)$, which needs the definition of all votes. Theorem 3 also shows that the NMVD of r-Approval is bounded for all constants r. Additionally, as r-Veto is exactly $(m-r)$-Approval, Theorem 3 also offers us the following result.

Theorem 4

For $\varphi$ being r-Veto, the NMVD of $\varphi$ at an election $E=(C, V)$ is at most $\left\lceil \frac{|\mathsf{{C}}_{\varphi }(E)|}{r}\right\rceil \le \left\lceil \frac{m-1}{r}\right\rceil$, where $m=|C|$.

Now we consider Maximin and Copeland$^{\alpha }$. Unlike other rules studied in the paper, Maximin and Copeland$^{\alpha }$ are Condorcet-consistent². We show that the NMVDs of these rules differ largely—Maximin has a bounded NMVD while Copeland$^{\alpha }$ does not.

Theorem 5

($\star$). The NMVD of Maximin is bounded by three.

We omit the proof of Theorem 5 because it relies on several lemmas on certain special directed graphs whose proofs take some space. However, we would like to point out that to construct the three votes needed to be added, we need to know not only the original winner but also the head-to-head comparisons among all candidates. If we are only aware of the original winner, can we still prevent manipulation by adding a constant number of votes? The following theorem answers the question.

Theorem 6

($\star$). Let (C, V) be an election. If V is hidden but we know the Maximin winner of (C, V), we can add four votes to prevent manipulation without changing the winner.

Furthermore, if we add two more votes, we could even prohibit manipulation without minding the tie-breaking rules.

Theorem 7

($\star$). The NMVD of Maximin is bounded by six for all tie-breaking rules.

Additionally, we would like to show by the following example that the upper bound given in Theorem 5 is tight.

Example 3

Let us consider an election with four candidates a, b, c, and w, and with the following votes (the head-to-head comparisons among the candidates are summarized in the table on the right side, where each entry indexed by a row candidate x and a column candidate y is n(x, y)):

In the tie-breaking order, w is ranked in the first place. Hence, w is the Maximin winner. Clearly, there are manipulators in the election. For instance, if one vote with the preference $b~a~w~c$ shifts a one position up, a becomes the Maximin winner. We show that the NMVD of Maximin at this election cannot be smaller than 3. For the sake of contradiction, assume that we can add t votes where $t\in [2]$ so that w remains the winner, and there are no manipulators after adding the vote(s). Observe first that we may assume that w is ranked in the top in the added vote(s), and hence the Maximin score of w in the new election is $6+t$. Let $x\in \{a, b, c\}$ be a candidate that is in the second place of at least one of the added vote(s). Therefore, in the new election, x has Maximin score at least 7. If $x=a$ (resp. $x=b$, $x=c$), one vote with the preference $b~a~w~c$ (resp. $c~b~w~a$, $a~c~w~b$) can improve the result in its favor by changing it into $a~b~c~w$ (resp. $b~c~a~w$, $c~a~b~w$). Precisely, after the change, the Maximin score of w decreases from $6+t$ to $5+t\le 7$, but the Maximin score of x increases to at least 8, making x the new winner, a contradiction.

Now we study Copeland$^{\alpha }$.

Theorem 8

($\star$). Regardless of tie-breaking rules, the NMVD of Copeland$^{\alpha }$ at an election (C, V) is bounded by $n+3-2\cdot min_{c\in C\setminus \{w\}}n(w,c)\le n+1$, where n is the number of votes and w is the Copeland$^{\alpha }$ winner of (C, V).

In the next section, we shall see that there are elections with only three candidates at which the NMVD of Copeland$^{\alpha }$ is not bounded by any constant.

Now we consider the NMVD of Bucklin. A trivial upper bound is $n+1$, because after adding $n+1$ votes ranking the current winner w in the top, the Bucklin score of w is one and this holds even if some original vote is changed. In the following, we give a bound with respect to the number of candidates. First, we have the following lemma regarding the Bucklin score of Bucklin winners.

Lemma 1

For every election (C, V) with $m>0$ candidates, the Bucklin score of the Bucklin winner is at most $\left\lceil \frac{m+1}{2} \right\rceil$.

Proof

For each $c\in C$ and $i\in [m]$, let $n_{c}^{i}$ be the number of votes in V ranking c in the i-th position, and let $n_{c}^{\le i}=\sum _{j=1}^in_{c}^{j}$ be the number of votes ranking c in the top-i positions. Clearly, for each $i\in [m]$, it holds that

$$\begin{aligned} \sum _{c\in C} n_{c}^{i}=n. \end{aligned}$$

(1)

Let $t=\left\lceil \frac{m+1}{2} \right\rceil$. For the sake of contradiction, assume that the Bucklin score of the winner is larger than t. Then, we have $n_{c}^{\le t}\le n/2$ for every candidate $c\in C$. It follows that $\sum _{c\in C} n_{c}^{\le t}\le \frac{n\cdot m}{2}$. However, due to Eq. (1), we also have

$$\begin{aligned} \sum _{c\in C} n_{c}^{\le t}=\sum _{c\in C}\sum _{i=1}^t n_{c}^{i}=\sum _{i=1}^t\sum _{c\in C} n_{c}^{i}=n\cdot t>\frac{n\cdot m}{2}, \end{aligned}$$

a contradiction.    $\square$

Based on Lemma 1, we can prove the following theorem.

Theorem 9

Let (C, V) be an election with $m>0$ candidates and $n>0$ votes such that the Bucklin winner has score at most $\left\lceil m/2 \right\rceil$. Then, the NMVD of Bucklin at (C, V) is bounded by $2(m-1)$ if n is even and by $m-1$ if n is odd.

Proof

Let $C=\{c_1, c_2, \dots , c_m\}$. We prove the theorem by distinguishing the following cases. Without loss of generality, let us assume that $w=c_m$ is the Bucklin winner of (C, V). Moreover, let $x\le \left\lceil \frac{m}{2}\right\rceil$ denote the Bucklin score of w. Finally, let A (resp. B) denote the set of candidates ranking before (resp. after) w in the tie-breaking order.

Case 1. $n=2k+1$ and $m=2t$ for some k and t.

In this case, for each integer $i\in [2t-1]$ we add one vote with the preference $w~c_{i} ~c_{i+1} ~\cdots ~c_{2t-1}~c_1~\cdots ~c_{i-1}$. Hence, we add in total $2t-1$ votes such that each candidate $c_i\in C\setminus \{w\}$ is ranked in the top-x positions at most $t-1$ times. Let $E'$ denote the new election after adding these votes. Note that for every $c\in A$, at most k votes in V rank c in the top-x positions. Therefore, at most $k+t-1$ votes rank c in the top-x positions in the new election $E'$. In this case, even if some vote is changed there can be at most $k+t$ votes ranking c in the top-x positions, implying that there exist no c-manipulators in $E'$ for any $c\in A$. Analogously, we can show that there is no c-manipulator for any $c\in B$.

Case 2. $n=2k$ and $m=2t$ for some k and t.

In this case, for each $i\in [2t-1]$ we add two votes with the same preference as in the first case, and analogously we can show that there are no c-manipulators for any $c\in C\setminus \{w\}$ after adding these $2(2t-1)$ votes.

Case 3. $n=2k+1$ and $m=2t+1$ for some k and t.

If the Bucklin score of w is at most t, the proof is analogous to the above cases. So, let us assume that $x=t+1$. If (C, V) is not manipulable, we don’t need to add any vote. Otherwise, V contains at least one vote which ranks w in the last $m-t-1$ positions. Hence, the 2t candidates in $C\setminus \{w\}$ occupy at least $n\cdot t+1$ top-$(t+1)$ positions of votes in V, implying that there exists at least one candidate $c\in C\setminus \{w\}$ whose Bucklin score is $t+1$ too. Moreover, c must be ranked after w in the tie-breaking order. Then, we add $2t-1$ votes so that (1) w is ranked in the top, and c is ranked in the $(t+1)$-th positions in all these votes; and (2) every candidate in $C\setminus \{c, w\}$ is ranked in the top-t positions at most $t-1$ times. Such votes clearly exist (they can be constructed in a way similar to the one in Case 1). Analogous to Case 1, it can be shown that there are no manipulators after adding these votes.

Case 4. $n=2k$ and $m=2t+1$ for some k and t.

In this case, after adding $4t-2$ votes where w is ranked in the top, some candidate $c\ne w$ who has Bucklin score $t+1$ is ranked in the $(t+1)$-th positions, and every other candidate is ranked in the top-t positions at most $2t-2$ times, there are no manipulators.    $\square$

Now we consider the case where the Bucklin winner w has score exactly $\left\lceil \frac{m+1}{2}\right\rceil$. Notice that when m is odd, we have $\left\lceil \frac{m}{2}\right\rceil =\left\lceil \frac{m+1}{2}\right\rceil$. Hence, we need only to consider the case where m is even. We have the following result.

Theorem 10

($\star$). Let (C, V) be an election of m candidates and n votes such that $m=2t>0$ is even and the Bucklin winner w has score $t+1$. Then, it holds that

• 1. |V| is even; and

• 2. the NMVD of Bucklin at (C, V) is at most $2(m-2)$.

Due to Lemma 1, Theorems 9 and 10, and the trivial bound $n+1$, we have the following corollary.

Corollary 1

The NMVD of Bucklin at every election with m candidates and n votes is at most $\min \{n+1, 2(m-1)\}$.

4 NMVD with a Small Candidate Set

In many real-world applications, the number of candidates is a small constant (see, e.g., [15]). Therefore, it makes much sense to study the NMVDs of voting rules at elections with only a few candidates. This is the focus of this section. For Borda, Maximin, and PluRun, their NMVDs are bounded, regardless of the number of candidates and tie-breaking rules (see Table 2). Due to Theorems 3 and 4, and Corollary 1, if m is a constant, r-Approval, r-Veto, and Bucklin also have constant bounded NMVDs. So, the most interesting rules in this section are Copeland$^{\alpha }$ where $\alpha \in [0, 1]$.

Table 3. Upper bounds of the NMVDs of Copeland$^{\alpha }$. Here, n denotes the number of votes. “odd” and “even” are with respect to n.

Table 4. Upper bounds of the NMVDs of Copeland$^{\alpha }$ at every election with n votes whose majority graph without the current winner is $\ell$-inducible. Results in a row labeled with $\heartsuit$ hold only when the majority graph without the current winner is a tournament.

One may wonder whether the NMVD of Copeland$^{\alpha }$ can be bounded by a constant too, or at least some function of m. Our answers are somewhat interesting. For Copeland$^1$, the answer is “Yes”. In particular, we obtain a bound $\gamma \cdot \frac{m}{\log m}$, where $\gamma$ is a constant. However, for Copeland$^{\alpha }$ where $\alpha \in [0, 1)$, our answer is in the negative: even when there are only three or four candidates, the NMVD of Copeland$^{\alpha }$ cannot be bounded by a constant. However, if we consider only elections without ties in head-to-head comparisons (e.g., when the number of votes is odd), we again have a positive answer. Our main results in this section are summarized in Tables 3 and 4.

The majority graph of an election $E=(C, V)$ (or simply V), denoted $G_{E}$, is a digraph with C being the vertex set, and there is an arc from $c\in C$ to $c'\in C$ if and only if c beats $c'$ in E. A tournament is a digraph such that between every pair of candidates there exists exactly one arc. A digraph G with vertex set C is $\ell$-inducible if there exists a multiset V of $\ell$ linear orders over C such that the majority graph of (C, V) is G. In particular, the minimum integer $\ell$ such that G is $\ell$-inducible is called the dimension of G. For a digraph G and a subset S of vertices of G, G[S] is the subgraph of G induced by S. The following lemma is due to [10].

Lemma 2

There exists a constant $\gamma$ such that every digraph with m vertices is $\gamma \cdot \frac{m}{\log m}$-inducible.

4.1 Copeland$^1$

In this section, we study Copeland$^1$. Our main result is as follows.

Theorem 11

Let $E=(C, V)$ be an election and $w\in C$ the Copeland$^1$ winner of E. If the majority graph of E without w (i.e., $G_{E}[C\setminus \{w\}]$) is $\ell$-inducible, then the NMVD of Copeland$^1$ at E is at most $\max \{\ell , 2\}$ if n is even, and is at most $2\ell$ if n is odd.

Proof

Let T be the majority graph of E without w. If $\ell =0$, all candidates are tied in head-to-head comparisons and, moreover, w is the first candidate in the tie-breaking order. In this case, it is easy to check that after adding two votes ranking w in the top, there does not exist any manipulator.

For $\ell \ge 1$, let $\succ _1, \dots , \succ _{\ell }$ be $\ell$ linear orders over $C\setminus \{w\}$ whose majority graph is T. If n is even, say $n=2k$ for some integer $k>0$, and $\ell \ge 2$, we add $\ell$ votes obtained from $\succ _1, \dots , \succ _{\ell }$ by inserting w in the top. Let $E'$ be the new election. Clearly, the score of w in $E'$ is at least that in E and, moreover, in the new election $E'$ the score of w does not decrease even if one vote in V is changed. We claim that the score of every candidate $a\in C\setminus \{w\}$ in $E'$ is at most that in E, even if one vote in V is changed. To this end, it suffices to show that every candidate $b\in C\setminus \{a\}$ who beats a in E still beats a in the new election $E'$ even after some vote in V is changed. If b beats a in E, at least $k+1$ votes in V prefer b to a. In the above added votes, there are at least $\left\lceil \frac{\ell +1}{2}\right\rceil$ votes preferring b to a. It follows that in the new election $E'$, there are at least $k+1+\left\lceil \frac{\ell +1}{2}\right\rceil \ge \left\lceil \frac{2k+\ell }{2}\right\rceil +1$ votes who prefer b to a. Then, given that $\ell \ge 2$, even if some vote is changed, there are still a majority of votes preferring b to a.

For all the other remaining cases (i.e., the case where n is even and $\ell =1$, and the case where n is odd), we add one more copy of the $\ell$ votes added in the above case. Similarly, we can show that after adding these votes there are no manipulators.    $\square$

The above theorem together with Lemma 2 directly give us the following corollary.

Corollary 2

The NMVDs of Copeland$^1$ at elections with m candidates are bounded by $\gamma \cdot \frac{m}{\log m}$, where $\gamma$ is a constant.

For tournaments of small sizes, Bachmeier et al. [2] studied the following lemma.

Lemma 3

All tournaments of up to 7 and 10 vertices are respectively 3-inducible and 5-inducible.

The largest integer i such that all tournaments of up to i vertices are 5-inducible is still unknown in the literature. Due to Theorem 11, Lemma 3, and the fact that all tournaments of up to two vertices are 1-inducible, we have the following corollary.

Corollary 3

Let (C, V) be an election with $m\le 11$ candidates and n votes. The NMVD of Copeland$^1$ at (C, V) is bounded by 10 if n is odd, and bounded by 5 if n is even. In addition, if $m\le 8$, it is bounded by 6 if n is odd and by 3 if n is even. Moreover, if $m=3$, it is bounded by 2.

4.2 Copeland$^{\alpha <1}$ with at Most Four Candidates

Now we study NMVD of Copeland$^{\alpha }$ where $\alpha \in [0, 1)$. Somewhat surprisingly, even when there are only three candidates, the NMVD of Copeland$^0$ cannot be bounded by a constant, standing in a sharp contrast to Copeland$^1$.

Theorem 12

($\star$). Let (C, V) be an election with three candidates and let $n=|V|>0$. Then, the NMVD of Copeland$^{\alpha }$ where $\alpha \in [0, 1)$ at (C, V) is bounded by

$$\begin{aligned} {\left\{ \begin{array}{ll} n-1 &{}\text {if}~n~\text {is even and}~\alpha =0,\\ 2 &{} otherwise.\\ \end{array}\right. } \end{aligned}$$

For Copeland$^{\alpha }$ where $\alpha \in (0, 1)$, we can also show that if we just have one more candidate, the NMVD cannot be bounded by a constant anymore if the number of votes is even, as shown in the following example.

Example 4

Consider an election with four candidates w, a, b, c, and with 2k votes as follows. Here, k can be any integer greater than three. In the digraph on the right side, the weight of an arc from x to y is n(x, y).

The tie-breaking order is $a\,\lhd \,b\,\lhd \,c\lhd \,w$. One can check that we cannot preclude manipulation without changing the winner by adding less than $2k-2$ votes.

4.3 Copeland$^{\alpha <1}$ with $\ell$-Inducible Majority Graphs

A major reason why the NMVD of Copeland$^{\alpha }$, $\alpha \in [0, 1)$, is not bounded in several theorems studied so far is that there are ties in head-to-head comparisons among nonwinning candidates. This motivates us to study elections without such ties. Consider an election (C, V) whose majority graph restricted to $C\setminus \{w\}$ is an $\ell$-inducible tournament T, where $\ell \ge 2$, and w is the current winner. If we add $\ell$ votes ranking w in the top and whose induced majority graph restricted to $C\setminus \{w\}$ is T, the comparisons between candidates are enhanced, in the sense that changing one vote in V is unable to reverse any arc among candidates in $C\setminus \{w\}$ but may make some arcs be removed. However, as in Copeland$^0$, two tied candidates do not get any point from their comparison, changing one vote does not increase the scores of candidates in $C\setminus \{w\}$. This observation leads to the following theorem.

Theorem 13

Let $E=(C, V)$ be an election and w the Copeland$^0$ winner of E. If the majority graph of E without w is an $\ell$-inducible tournament, then the NMVD of Copeland$^0$ at E is at most $\ell$ if $\ell \ge 2$ or $|V|$ is even, and is at most 2 otherwise.

Proof

Let T denote the majority graph of E restricted to $C\setminus \{w\}$, which is $\ell$-inducible. Let $U=\{\succ _1,\dots , \succ _{\ell }\}$ be a multiset of $\ell$ votes over $C\setminus \{w\}$ such that majority graph of $(C\setminus \{w\}, U)$ is exactly T.

We consider first the case where $\ell \ge 2$ or $|V|$ is even. In this case, we add to the election $\ell$ votes obtained from $\succ _1, \dots , \succ _{\ell }$ by inserting w into the top position. After adding these votes, the majority graph of the election restricted to $C\setminus \{w\}$ is still T. As every added vote ranks w above other candidates, one can check that if a candidate a is beaten by w in advance, then a is still beaten by w after adding the above votes, even if one vote in V is changed. Hence, the score of w in the new election remains at least the same as that in the original election. Moreover, if there is an arc from a candidate $a\in C\setminus \{w\}$ to another candidate $b\in C\setminus \{w\}$ in T, then, after adding the above votes a beats b by at least

$$\begin{aligned} \left\lceil \frac{n+1}{2}\right\rceil +\left\lceil \frac{\ell +1}{2}\right\rceil \ge \left\lceil \frac{n+\ell }{2}\right\rceil +1. \end{aligned}$$

This implies that when one vote in V is changed, a either still beats b or ties with b. So, the change of any vote does not increase the score of a. As this holds for every candidate $a\in C\setminus \{w\}$, we can conclude that changing one vote in V does not prevent w from winning.

For the case where $\ell =1$ and $|V|$ is odd, the above argument does not hold, because in this case if a candidate a is beaten by w in advance, then after adding one vote, it may be that w ties a if some vote in V is changed. However, if we add two votes obtained from $\succ _1$ by inserting w in the first place, w remains as the winner and there is no manipulator in V.    $\square$

Theorem 13 and Lemma 3 yield the following result.

Corollary 4

The NMVD of Copeland$^0$ at every election with m candidates and an odd number of votes is at most 3 if $m\le 8$ and is at most 5 if $m\le 11$. Moreover, the bound is tight for every m such that $4\le m\le 8$.

Similar to Theorem 13, for Copeland$^{\alpha }$, $\alpha \in (0, 1)$, we obtain the following result.

Theorem 14

($\star$). Let $E=(C, V)$ be an election, and let w be the Copeland$^{\alpha }$ winner of E where $\alpha \in (0, 1)$. If the majority graph of E restricted to $C\setminus \{w\}$ is an $\ell$-inducible tournament, then the NMVD of Copeland$^{\alpha }$ at E is at most $2\ell$.

Theorem 14 and Lemma 3 yield the following result.

Corollary 5

The NMVD of Copeland$^{\alpha }$ where $\alpha \in (0, 1)$ at every election (C, V) with an odd number of votes is at most 6 if $|C|\le 8$ and is at most 10 if $|C|\le 11$.

For elections with four candidates, we can improve the bound by one.

Theorem 15

($\star$). The NMVD of Copeland$^{\alpha }$ where $\alpha \in (0, 1)$ at every election (C, V) with four candidates is at most 5 if |V| is odd.

We would like to remark that Theorems 11, 13, and 14 suggest using the notion of dimension of digraphs to find the votes whose addition precludes election manipulation. Unfortunately, calculating the dimension of a digraph seems to be a time-consuming task. To the best of our knowledge, the complexity of this problem in general still remains open so far. But for the case where there are only a few candidates, calculating the dimension can be done in an acceptable time. We refer to [2] for a more detailed discussion on this issue.

5 Future Research

It is interesting to study the NMVDs of many other voting rules such as the ranked pairs, Schulze’s, Baldwin’s, etc. In addition, one can investigate the NMVDs of voting rules at elections with a bit larger but still a constant number of candidates. Finally, it is intriguing to investigate our notion in the more general setting where we allow multiple manipulators to form coalitions and coordinate their actions.