Measuring majority power and veto power of voting rules

Abstract

We study voting rules with respect to how they allow or limit a majority from dominating minorities: whether a voting rule makes a majority powerful and whether minorities can veto the candidates they do not prefer. For a given voting rule, the minimal share of voters that guarantees a victory to one of the majority’s most preferred candidates is the measure of majority power; and the minimal share of voters that allows the minority to veto each of their least preferred candidates is the measure of veto power. We find tight bounds on such minimal shares for voting rules that are popular in the literature and used in real elections. We order the rules according to majority power and veto power. Instant-runoff voting has both the highest majority power and the highest veto power; plurality rule has the lowest. In general, the greater is the majority power of a voting rule, the greater its veto power. The three exceptions are: voting with proportional veto power, Black’s rule and Borda’s rule, which have relatively weak majority power and strong veto power, thus providing minority protection. Our results can shed light on how voting rules provide different incentives for voter participation and candidate nomination.

1 Introduction

Majority tyranny has been a buzzword for centuries and can be traced back to ancient Greek ochlocracy—mob rule. A more modern yet classical reference is the work of James Madison:

If a majority be united by a common interest, the rights of the minority will be insecure. (Federalist 51.)

In this paper we propose a simple way of measuring the robustness of a voting rule to majority tyranny or, put differently, majority power, that is, the extent to which a rule allows a majority to dictate the outcome of an election regardless of the minority’s opinion and voting strategy.

Consider the illustrative example presented in Table 1. Let there be five candidates: Bernie, Donald, Hillary, John and Ted, and let the voters have one of five rankings of the candidates, with the top row giving the shares of the candidates’ supporters in the voting population. Here, as also throughout the paper, the total number of voters is arbitrary.

Table 1 Preference profile

Let us look at the voters in the last three columns in Table 1. Those voters constitute a mutual majority of 57% as they prefer the same subset of three candidates (Bernie, John and Ted) over all other candidates. Depending on the voting rule, that 57% may be enough to guarantee that one of these three candidates will win. For example, it is enough for instant-runoff voting. According to that rule, from each ballot we delete iteratively the candidate with the fewest top positions. John is deleted first, followed by Bernie, then Donald, then Hillary, and the winner is Ted.¹ In contrast, plurality rule makes Hillary the winner, and plurality with runoff deletes each candidate except for the two with the most top positions (Donald and Hillary), thus making Donald the winner.

Formally, a voting rule satisfies the (q, k)-majority criterion if whenever a group of the k candidates get top k positions among a qualified mutual majority of more than q voters, then the rule must select one of the k candidates. For a given voting rule, the (q, k)-majority criterion measures the majority’s power: the lower is the quota q, the more the rule empowers the majority.

The (q, k)-majority criterion subsumes few criteria known in the literature. The majority criterion requires that a candidate top-ranked by more than half of the voters is declared the winner. That criterion is equivalent to the (q, k)-majority criterion with $k=1$ and a fixed quota $q=1/2$. When we consider a mutual majority that top-ranks some k candidates, then the mutual majority criterion requires that one of those k candidates wins. That criterion is equivalent to the (q, k)-majority criterion with an arbitrary k and a fixed quota $q=1/2$.

The previous literature studied majority power by partitioning the voting rules into three categories: (1) rules that do not satisfy the majority criterion, (2) rules that satisfy the majority criterion but not the mutual majority criterion, and (3) rules that satisfy the mutual majority criterion (see Fig. 1).

Category (1) delivers the smallest majority power as those rules do not guarantee a majority that its $k = 1$ top candidate wins. Category (1) includes the proportional veto core (Moulin 1981, 1982, 1983) and positional scoring rules like Borda’s (Baharad and Nitzan 2002; Nitzan 2009). In contrast, category (3) delivers the most majority power, as even a simple majority ($q\ge 1/2$) is enough to elect one of its top-ranked candidates; a review of the results can be found, for example, in Tideman (2006). However, those criteria are black-or-white and do not allow a finer analysis of majority power. Our quantitative criteria fill that gap.

Among all voting rules of interest, the most important are, perhaps, plurality and plurality with runoff. Together with the instant-runoff those voting rules are most widespread in political elections around the world.² Interestingly, the three voting rules are comparable in terms of majority power in an arbitrary setting. Instant-runoff voting makes the majority extremely powerful and has a constant quota $q=1/2$, thereby satisfying the mutual majority criterion. We show that the plurality with runoff rule makes the majority less powerful, $q=\max \{k/(k+2),1/2\}$, while, of the three rules, with $q=k/(k+1)$, plurality rule empowers the majority the least.

In our example presented in Table 1, $k=3$ and, thus, in order to guarantee a victory to one of the three preferred candidates, the share of supporting voters must be more than 60% under the plurality with runoff rule and more than 75% under plurality rule. In the example, however, the top-three’s share is only 57%, which is not enough to guarantee a victory for either John, Bernie or Ted under those two voting rules.

As an additional simple illustration of the quotas, consider how the three voting rules give different incentives for candidate nomination. A leading party (or a coalition) that has the support of at least half the voters decides whether to nominate two candidates in a general election or run primaries and nominate a single candidate. Under the plurality with runoff rule, the party is safe to forgo primaries and nominate both candidates.³ Under instant-runoff voting, that also is the case; moreover, the party (or coalition) safely can nominate more than two candidates. But under plurality rule, unless the party has the support of at least two-thirds of the voters, it has to hold primaries and can nominate only a single candidate.

Fig. 1

Majority power and veto power: partial comparison of voting rules. Notes: Black dots represent voting rules. Arrows go from rules that have less majority power and less veto power to the rules that have more power in an arbitrary setting. The exact positioning of the rules is based on authors’ interpretation of Tables 3, 4, 5 and 6 for different settings. Simpson’s rule and Young’s rule always have the same majority and veto powers

The summary of our main results (see Theorem 1 to 11) is presented in Fig. 1. We focus on the voting rules that are popular in the literature and do not satisfy the mutual majority criterion, finding the minimal size of the qualified mutual majority q for each of the rules. In Fig. 1 the voting rules are ranked in ascending order of majority power: each arrow goes from a rule with a larger minimal quota to a rule with a smaller minimal quota.⁴ Interestingly, while for a small number of preferred candidates k we get only a partial order, as shown in Fig 1; whenever $k>4$ and the total number of candidates m is arbitrary, we get a complete majority power ordering over the rules (see the x-axis in Fig. 1 and Table 3 for details).

Our analysis allows us to ask a question that is dual to majority power – the question of veto power. Imagine a group of voters that dislikes a group of l candidates and assigns them the lowest ranks in an arbitrary order. In our example presented in Table 1, we have two such groups: 58% of voters dislike Hillary ($l=1$), while 57% of voters dislike Hillary and Donald ($l=2$). The question is: are the groups large enough to prevent each of these l candidates from winning?

Formally, a voting rule satisfies the (q, l)-veto criterion if any group of a size larger than q always can veto each of the l candidates. For a given voting rule, the (q, l)-veto criterion measures the group’s veto power: the lower is the quota q, the higher is its veto power.

The veto criterion generalizes the majority loser criterion known in the literature. The majority loser criterion requires that when more than half the voters assign the same candidate the lowest rank, then that candidate does not win. The criterion is equivalent to the (q, l)-veto criterion with $l=1$ and $q=1/2$.

Based on the (q, l)-veto criterion, we get the same partial ordering as in the case of the (q, k)-majority criterion (Fig. 1). For example, instant-runoff voting yields the most veto power, plurality rule yields the least, and the veto power of plurality with runoff is between those extremes. That is not surprising owing to duality: for a given number of candidates m, a group that vetoes its l least-preferred candidates at the same time guarantees that one of its $k=m-l$ most preferred candidates wins.⁵

However, when we consider the (q, l)-veto criterion for an arbitrary total number of candidates m, then the order of the voting rules differs from the order for the (q, k)-majority criterion. Whenever $l>2$ the complete order based on veto power is presented in Table 5 and shown on the y-axis in Fig. 1.

Based on our two criteria, instant-runoff voting is the most powerful rule both from the majority power viewpoint and the veto power viewpoint. Since votes are transferable, a simple majority of voters who like the same candidates can ensure that one of those candidates wins. Similarly, if a simple majority dislikes the same candidates, then none of those candidates wins. Thus, instant-runoff voting protects simple majorities. At the other extreme, plurality rule appears to have relatively low levels of majority power and veto power.

Perhaps surprisingly, the tradeoff between majority power and veto power contains three exceptions. Among all voting rules, the proportional veto core,⁶Black’s rule,⁷ and the Borda rule provide a balanced combination of properties: relatively weak majority power and strong veto power. Thus, the three rules are best at protecting minorities. In Sect. 4 we discuss why these three rules are exceptional in our framework.

Throughout the paper we ignore strategic issues and treat the set of candidates, the set of voters, and their preferences as fixed.⁸ Nevertheless, our two criteria and the results have another interpretation: they can shed light on how voting rules differ in their incentives for voter participation. Consider an election for which a mutual majority of size q top-ranks some k candidates. If the minimal quota of a given rule is less than q, then minorities cannot do much. At most, minorities can influence which of the top-ranked k candidates is selected,⁹, but any other candidate has zero chance of winning regardless of the minority vote. That scenario can discourage minorities from participating, thereby making the relative size of the mutual majority larger and minorities smaller and weaker, causing positive feedback.

In contrast, when the minimal quota is larger than q, then minorities have more influence on the election and, hence, have stronger incentives to participate. If that causes more minorities to show up at the polls, then their relative size increases, again causing positive feedback.

A similar voter-turnout argument can be deduced from the veto criterion. For instance, in a given election let the ruling party nominate l candidates (when $l=1$ that candidate can be the incumbent), and let the opposition nominate its own candidates. The opposition’s supporters do not necessarily agree on their most preferred candidate, but they agree that the nominees of the ruling party are worse. Then, a voting rule with weak veto power (i.e., high minimal quota) discourages opposition supporters from participating, while a rule with strong veto power (i.e., low minimal quota) provides greater incentives to participate.

The two participation arguments have opposite implications. The veto power argument predicts that voting rules with low quotas encourage the participation of opposition supporters who dislike the same candidates, while the majority power argument suggests that such rules discourage minorities from struggling to assemble a mutual majority.

As an example, consider the case of instant-runoff voting. The common opinion of the social choice literature is that instant-runoff voting promotes participation. Indeed, when minorities face a larger group of voters with a single preferred candidate, then instant-runoffs allow minorities to transfer their votes instead of wasting them (Tideman 1995; Zwicker 2016). However, if minorities face a mutual majority having more than one preferred candidate, then the instant-runoff works in favor of that majority.

Overall, we abstain from normative judgments and cannot say which voting rule is best based on the two criteria that we propose. The two criteria are instruments that should be used at the discretion of a mechanism designer, as such decisions always involve tradeoffs. We arrive at some of those tradeoffs when we study the compatibility of the (q, k)-majority criterion (and the (q, l)-veto criterion) with other axioms; those results are presented in Sect. 3.4.

The paper proceeds as follows. Section 2 presents the model and the definitions of the voting rules. In Sect. 3, we analyze our two criteria for the voting rules considered and the relevant tradeoffs. A non-technical reader who understands the two criteria may skip those two sections safely, only taking a look at Tables 3, 4, 5 and 6, and proceed to Sect. 4 which concludes with a discussion of the results and the open questions. The proofs are presented in the Online Appendix.

2 Model

2.1 Voting problem

This subsection introduces the standard voting problem and the main criteria for voting rules.

Consider a voting problem wherein $n \ge 1$ voters $I=\{1,\ldots , n\}$ select one winner among $m\ge 1$ candidates (alternatives) $A=\{ a_1, \ldots , a_m\}$. Let L(A) be the set of linear orders (complete, transitive, and antisymmetric binary relations) on the set of candidates A.

Each voter $i \in I$ is endowed with a preference relation$\succ _i \in L(A)$. (Voter i prefers a to b when $a\succ _i b$.)

The preference relation $\succ _i$ corresponds to a unique ranking bijection $R_i : A \rightarrow \{1,\ldots , m\}$, such that $R_i^a$ is the relative rank that voter i gives to candidate a,

$$\begin{aligned} R_i^a = |\{ b\in A : b\succ _i a \}| + 1, \quad a\in A, \quad i\in \{1,\ldots , n\}. \end{aligned}$$

The collection of individuals’ preferences $\succ$ = $(\succ _1, \ldots ,\succ _n)$$\in {L(A)}^n$ as well as the corresponding ranks $(R_1, \ldots , R_n)$ are referred to as the preference profile. (There exist m! different linear orders and $(m!)^{n}$ different profiles.)

Example 1

Table 2 provides an example of a preference profile for $n=100$ voters over $m=4$ candidates. Here, voters are assumed to be anonymous, which allows us to group voters with the same individual preferences. Each column represents some group of voters, with the number of voters in the group shown in the top row; the candidates are listed below (starting from the most preferred candidate) according to the preference of the group.

Table 2 Preference profile, tournament matrix, and positional matrix

Given a preference profile, we determine a function h(a, b) as the number of voters that prefer candidate a over candidate b,

$$\begin{aligned} h(a,b) = | \{ i : a \succ _i b, \quad 1 \le i \le n \} |, \quad a,b\in A, \quad a\ne b. \end{aligned}$$

Matrix h with elements h(a, b) is called a tournament matrix. (Note that $h(a,b)=n-h(b,a)$ for each $a\ne b$.)

Table 2 provides the tournament matrix for the profile in Example 1.

We say that candidate awins in a pairwise comparison to candidate b, if $h(a,b)>n/2$.

For some subset $B\subseteq A$, a candidate is called a Condorcet winner (de Condorcet 1785),¹⁰ if he/she wins in pairwise comparison with each candidate in the subset. Thus, the set of Condorcet winners is

$$\begin{aligned} CW(B)=\{b\in B : h(b,a) > n/2 \quad \text{ for } \text{ each } \quad a\in B\setminus b \}, \quad B\subseteq A. \end{aligned}$$

It is easy to see that the set of Condorcet winners CW is either a singleton or empty.

For the preference profile in Table 2, candidate a is the Condorcet winner.

Similarly, we say that candidate aweakly wins in a pairwise comparison to candidate b, if $h(a,b) \ge n/2$. For some subset $B\subseteq A$, a candidate is called a weak Condorcet winner if he/she wins weakly in a pairwise comparison with each candidate in the subset.

Let a positional vector of candidate a be vector $n(a) = (n_1(a),\ldots , n_m(a))$, where $n_l(a)$ is the number of voters for whom candidate a has rank l in individual preferences,

$$\begin{aligned} n_l(a) = |\{ i : R_i^a = l, \quad 1 \le i \le n \}|, \quad a\in A, \quad l\in \{1,\ldots , m\}. \end{aligned}$$

The definition implies that each positional vector has non-negative elements, $n_l(a)\ge 0$ for each l, and the sum of elements is equal to the number of voters $\sum \nolimits _{l=1}^m {n_l(a) = n}$.

Candidate a is called a majority winner, if $n_1(a)>n/2$. Similarly, candidate a is called a majority loser if $n_m(a)>n/2$.

A collection of positional vectors for all candidates is called a positional matrix$n(\succ ) = (n(a_1), \ldots , n(a_m))$.

Table 2 provides the positional matrix for the profile in Example 1.

A mapping $C(B,{\succ })$ that to each nonempty subset $B\subseteq A$ and each preference profile $\succ$ gives a choice set is called a voting rule (or social choice rule),¹¹

$$\begin{aligned} C : 2^A \setminus \emptyset \times L(A)^n \rightarrow 2^A, \end{aligned}$$

where $C(B,\succ )\subseteq B$ for any B; and $C(B,\succ ) = C(B,\succ ')$, whenever preference profiles $\succ , \succ '$ coincide on B.

A rule is called universal if $C(B,\succ )\ne \emptyset$ for any nonempty B and any profile $\succ$. For instance, the Condorcet rule $CW(B,\succ )$ is not universal.

Let us define the criteria that are critical for the results of the paper and the voting rules considered below.¹²

Majority criterion For each preference profile, if some candidate a is top-ranked by more than half the voters ($n_1(a)>n/2$) then the choice set coincides with that candidate.

Mutual majority criterion¹³ For each preference profile, if more than half the voters give to some k candidates ($B = \{b_1,\ldots , b_{k}\}$, $1\le k < m$) top k ranks in an arbitrary order then the choice set is included in B.

Majority loser criterion¹⁴ For each preference profile, if some candidate a is bottom-ranked by more than half the voters ($n_m(a)>n/2$) then the choice set excludes that candidate.

For any fixed quota $q\in (0,1)$ and any fixed number of preferred candidates k among the total of m candidates, we define the next criteria.

(q, k, m)-majority criterion¹⁵ For each preference profile with a total of m candidates, if a share of voters exceeding q gives to some k candidates ($B = \{b_1,\ldots , b_{k}\}$, $1\le k < m$) top k ranks in an arbitrary order then the choice set is included in B.

For a given q, k, we say that a rule satisfies the (q, k)-majority criterion if it satisfies the (q, k, m)-majority criterion for each m.

For a given q, we say that a rule satisfies the q-mutual majority criterion if it satisfies the (q, k)-majority criterion for each k.

For universal voting rules, it also is apparent from the definitions that the mutual majority criterion implies the majority criterion; for any k, m and any $q'\ge q$, the (q, k, m)-majority criterion implies the ($q',k,m$)-majority criterion; the majority criterion is equivalent to the (1 / 2, 1)-majority criterion; the mutual majority criterion is equivalent to the (1 / 2, k)-majority criterion with arbitrary k; the majority loser criterion is equivalent to the ($1/2,m-1,m$)-majority criterion.¹⁶

2.2 Voting rules

This subsection presents the definitions of the voting rules that satisfy the majority criterion but do not satisfy the mutual majority criterion. We also consider monotonic scoring rules that generally do not satisfy the majority criterion.

Under the plurality voting rule, the candidate who receives the most top positions is declared the winner,

$$\begin{aligned} \mathrm {Pl}(A,\succ ) = \{a\in A : n_1(a)\ge n_1(b) \quad \text{ for } \text{ each } \quad b\in A\setminus a \}. \end{aligned}$$

The plurality with runoff (RV) voting rule proceeds in two rounds: first, the two candidates with the most top positions are determined, the winner then is chosen between the two using the simple majority rule.

According to Simpson’s rule (1969), or the maximin voting rule (see also Young 1977), each candidate receives a score equal to the minimal number of votes that he/she receives compared to any other candidate,

$$\begin{aligned} Si(a) = \min _{b\in A\setminus \{ a \}} {h(a,b)}, \end{aligned}$$

and the winner is the candidate with the most score.

The Young score of candidate a is defined as the smallest number $n'$ such that a set of $n'$ voters exists so that a is a weak Condorcet winner when those $n'$ voters are removed from the election (Young 1977; Caragiannis et al. 2016). All candidates with the lowest Young score in a given election are its Young winner(s).

According to the Condorcet least-reversal rule (CLR) (aka the simplified Dodgson rule, see Tideman 2006), the winner is, informally, the candidate $a\in A$ who needs the least number of reversals in pairwise comparisons in order to become a Condorcet winner. Formally, the winner d minimizes the following sum of losing margins relative to each candidate c:

$$\begin{aligned} p^{CLR}_d=\sum \limits _{c\in A\setminus d}{\max \left\{ \frac{n}{2} - h(d,c), 0\right\} }. \end{aligned}$$

(1)

The Dodgson score of candidate a is the smallest number of sequential exchanges of adjacent candidates in preference orders such that after those exchanges a is a Condorcet winner (Dodgson 1876; McLean and Urken 1995; Caragiannis et al. 2016). All candidates with the smallest Dodgson scores are the Dodgson winner(s).

A proportional veto core is defined as follows (Moulin 1981, 1983). For a given profile with n voters and m candidates, a candidate a is not stable if some coalition of t voters blocks him. Blocking means that a subset B of candidates exists such that each of the t voters prefers each candidate $b\in B$ over candidate a and B is large enough, $|A\setminus B| < m\cdot t/n$.

The proportional veto core consists of all stable candidates.

Under the Borda rule (de Borda 1781; McLean and Urken 1995), the first-best candidate in an individual’s preference order gets $m-1$ points, the second-best candidate gets $m-2$, ..., the last gets 0 points.

The total Borda score can be calculated using the positional vector n(a) as follows:

$$\begin{aligned} Bo(a)=\sum \limits _{i=1}^m{n_i(a)(m-i)}, \quad a\in A. \end{aligned}$$

(2)

The candidate with the highest total score wins. The score also can be calculated using the tournament matrix:

$$\begin{aligned} Bo(a)= \sum _{b\in A\setminus \{ a \}} {h(a,b)}, \quad a\in A. \end{aligned}$$

(3)

Black’s rule (1958) selects a Condorcet winner. If a Condorcet winner does not exist, then the candidate with the highest Borda score (3) is selected.

In a non-generalized scoring rule each of m candidates is assigned a score from $s_1, \ldots , s_m$ for a corresponding position in a voter’s individual preference order and then the scores are summed up over all voters.¹⁷ In the paper, we consider monotonic scoring rules in which $s_1 > s_m$ and $s_1 \ge s_2 \ge \ldots \ge s_m$. The plurality rule and the Borda rule are monotonic scoring rules with the scores $s_1=1, s_2 = \cdots = s_{m} = 0$ and $s_1 = m-1, s_2 = m-2, \ldots s_m = 0$, respectively.

Inverse plurality rule (alternatively, anti-plurality rule or negative voting) is a monotonic scoring rule with the scores $s_1 = \cdots = s_{m-1} = 1, s_m =0$.

If the difference in scores is positive and nondecreasing from position m to position 1, that is, $0<s_{m-1}-s_m \le s_{m-2}-s_{m-1}\le \ldots \le s_1-s_2$, then a rule will be called a convex scoring rule. For instance, the Borda rule is a convex scoring rule.

Our last rule is based on truncated Borda scores defined as follows. For some positional vector n(a) and some real number $t\in (0,+\infty )$, the truncated Borda score (Fishburn 1974) is

$$\begin{aligned} B_t(a) = t \cdot n_1(a) {+} (t{-}1) n_2(a) {+} \cdots {+} (t {-} \lfloor {t}\rfloor ) n_{\lfloor {t}\rfloor +1}(a), \quad t\in (0{,}{+}\infty ), \end{aligned}$$

where for $i>m$ we put $n_i(a)=0$. The definition implies that $B_{m-1}(a)=Bo(a)$.

Now we can define a modification of a standard median voting rule (Sertel and Yılmaz 1999), namely the convex median voting rule (CM) (Kondratev 2018). Instead of the standard sequence $n_1(a),n_1(a) + n_2(a),n_1(a) + n_2(a) + n_3(a), \ldots$ we use the truncated Borda scores. If $n_1(a)>n/2$ for some candidate a, then that candidate is the winner. Otherwise, for each candidate a define the score of the convex median using the following formula:

$$\begin{aligned} \mathrm {CM}(a) = \max \left\{ t\ge 1: \frac{B_t(a)}{t} \le \frac{n}{2} \right\} , \end{aligned}$$

and the winner is the candidate with the lowest value of the convex median.

We complete this section with one more desirable criterion.

Second-order positional dominance (2-PD) (Stein et al. 1994). Whenever candidate a obtains a higher score than candidate b for all convex scoring rules then candidate b is not included in the choice set.

3 Results

3.1 Majority-consistent voting rules

This subsection considers the voting rules that satisfy the majority criterion. They thus satisfy the (q, k)-majority criterion with $k=1$ and any $q\ge 1/2$, but do not satisfy the mutual majority criterion.¹⁸ In the case of only two candidates, each rule satisfying the majority criterion coincides with simple majority rule wherein the winner is the candidate that gets at least half the votes.¹⁹ In what follows we consider the case of $m>2$ candidates.

For the voting rules considered, below we find necessary and sufficient conditions under which the (q, k, m)-majority criterion is satisfied. First, we determine the tight bounds for plurality rule, Simpson’s rule, Young’s rule and Condorcet least-reversal rule.

Theorem 1

For each$m > k\ge 1$, plurality rule satisfies (q, k, m)-majority criterion if and only if$q\ge k/(k+1)$.

Theorem 2

For each$m>k>1$, Simpson’s rule satisfies the (q, k, m)-majority criterion if and only if$q\ge (k-1)/k$.²⁰

Theorem 3

For each$m>k>1$, Young’s rule satisfies the (q, k, m)-majority criterion if and only if$q\ge (k-1)/k$.

Theorem 4

For each$m>k\ge 2$and for each evenk, Condorcet least-reversal rule satisfies the (q, k, m)-majority criterion if and only if$q\ge (5k-2)/(8k)$; for each$m>k\ge 1$and for each oddk, the rule satisfies the criterion if and only if$q\ge (5k^2-2k+1)/(8k^2)$.²¹

A few peculiarities can be observed regarding the above results. For plurality rule, Simpson’s rule, Young’s rule, and Condorcet least-reversal rule, the minimal size of the qualified mutual majority q(k, m) depends on the number of preferred candidates k but does not depend on the total number of candidates m. Theorem 4 shows that the Condorcet least-reversal rule is, perhaps surprisingly, very close to satisfying the mutual majority criterion because it satisfies the 5 / 8-mutual majority criterion. At the other extreme, plurality rule gives the highest non-trivial minimal quota for a given $k>1$ among all studied voting rules.

Interestingly, both Simpson’s rule and Young’s rule have the same minimal quota q for every number of preferred candidates k and every total number of candidates m. This is the only such coincidence among all of the rules that we consider.

Next, we determine the tight bounds for the plurality with runoff and Black’s rules.

Theorem 5

For each$m-1 = k \ge 1$, the plurality with runoff rule satisfies the (q, k, m)-majority criterion if and only if$q\ge 1/2$; for each$m-1> k >1$, the rule satisfies the criterion if and only if$q \ge k/(k+2)$.

Theorem 6

For each$m>k>1$, Black’s rule satisfies the (q, k, m)-majority criterion if and only if$q\ge (2m-k-1)/(2m)$.

Theorem 6 actually finds the tight bound of quota for the Borda rule. In particular, when $k=1$, the quota equals $q=(m-1)/m$; it also was calculated by Baharad and Nitzan (2002) and Nitzan (2009).

Theorem 7

For each$m>2k$, the convex median voting rule satisfies the (q, k, m)-majority criterion if and only if$q\ge (3k-1)/(4k)$; for each$m=k+1$ – if and only if$q\ge 1/2$; for each$2k\ge m > k+1$, the tight boundqsatisfies the inequality$\frac{1}{2}< q < \frac{3k-1}{4k}$and also the equation

$$\begin{aligned} 4k(m-k-1)q^2 + (5k^2+5k-2mk-m^2+m)q + m(m-1-2k) = 0. \end{aligned}$$

(4)

Let us briefly motivate the results for the convex median voting rule. The Borda rule satisfies second-order positional dominance (2-PD), but it fails the majority criterion. The convex median voting rule was proposed by Kondratev (2018) as a rule that satisfies both 2-PD and the majority criterion. Theorem 7 shows that the rule is much closer to satisfying the stronger criterion of the mutual majority because it satisfies the 3 / 4-mutual majority criterion.

For Dodgson’s rule, below we find sufficient conditions. Necessary and sufficient conditions remain an open question.

Theorem 8

For$m>k\ge 1$, Dodgson’s rule satisfies the (q, k, m)-majority criterion with$q\ge k/(k+1)$; the rule fails the criterion with$q<(5k-2)/(8k)$when$k\ge 2$is even, and$q <(5k^2-2k+1)/(8k^2)$when$k\ge 1$is odd.

Table 3 Measuring majority power: for a given k, the minimal quota q such that (q, k)-majority criterion is satisfied

The summary of the results from this subsection (Theorem 1 to 7) is presented in Fig. 1. When the total number of candidates m and the number of preferred candidates k are not specified, we can order the voting rules with respect to majority power only partially. The minimal size of the qualified mutual majority q(k, m) increases weakly along the arrows.

Using the (q, k)-majority criterion we get a complete order of the voting rules, as is shown in Table 3. The voting rules are ordered based on the quota q from those with the most majority power to those with the least whenever the number of preferred candidates $k>4$. When $k=1$, the quota for majority-consistent rules equals 0.5. (The proportional veto core, the Borda rule and the inverse plurality rule do not satisfy the majority criterion and have quota 1.) As k increases and the mutual majority’s preferences over the preferred candidates might become more diverse, the minimal quota q also increases weakly. The rate of increase varies among the rules and for a small $k\in \{2,3,4\}$ the order of the rules varies as well.

3.2 Majority-inconsistent voting rules

In this subsection we present the results of the proportional veto core and scoring voting rules.

Theorem 9

For each$m > k\ge 1$, the proportional veto core satisfies the (q, k, m)-majority criterion if and only if$q\ge (m-k)/m$.

That result is not surprising because forcing the selection of one of the k most preferred candidates is equivalent to the vetoing of $m-k$ least preferred candidates. Hence, any voting rule that selects from the proportional veto core also satisfies Theorem 9.²²

Also, this subsection generalizes Theorem 1 for plurality rule ($s_1=1, s_2=\cdots = s_m = 0$) and Theorem 6 for the Borda rule ($s_i=m-i, \; i=1,\ldots ,m$).

Theorem 10

For each$m>k\ge 1$, a monotonic scoring rule satisfies the (q, k, m)-majority criterion if and only if the quotaqsatisfies the next inequality

$$\begin{aligned} q \ge \frac{s_1 - \frac{1}{k} \sum \nolimits _{i=1}^k{s_{m-i+1}}}{s_1- \frac{1}{k} \sum \nolimits _{i=1}^k{s_{m-i+1}} + \frac{1}{k} \sum \nolimits _{i=1}^k{s_i} - s_{k+1}}. \end{aligned}$$

(5)

For each$m>1$, a monotonic scoring rule satisfies the majority loser criterion²³if and only if the next inequality holds

$$\begin{aligned} s_1-\frac{s_2+\cdots +s_m}{m-1}\le \frac{s_1+\cdots +s_{m-1}}{m-1}-s_m. \end{aligned}$$

(6)

When $k=1$, the inequality (5) is²⁴

$$\begin{aligned} q \ge \frac{s_1-s_m}{s_1-s_m+s_1-s_2}, \end{aligned}$$

also calculated by Baharad and Nitzan (2002) and Nitzan (2009).

When $k=1$ and $q=1/2$, we have the inequality $s_m\ge s_2$. Thus, for each $m>1$, a monotonic scoring rule satisfies the majority criterion if and only if the rule is equivalent to plurality rule ($s_1>s_2=\cdots = s_m$). That result also was established by Lepelley (1992) and Sanver (2002).

When $m=3$, the inequality (6) was established, for example, by Diss et al. (2018).

For the inverse plurality rule ($s_1=\cdots =s_{m-1}=1, s_m=0$), Theorem 10 implies the next statement directly.

Theorem 11

For each$m-1>k\ge 1$and for each$q<1$, the inverse plurality rule fails the (q, k, m)-majority criterion; for each$m-1=k\ge 1$, the rule satisfies the (q, k, m)-majority criterion if and only if$q\ge 1/m$.

Note that for the inverse plurality rule and the proportional veto core, the minimal quota q may be below one-half. For the inverse plurality rule, that occurs whenever the number of preferred candidates k equals the total number of candidates m minus one, which is the same as saying that one candidate is vetoed by the mutual majority. We present the analysis of veto power in the next subsection.

Table 4 Minimal quota q such that the (q, k, m)-majority criterion is satisfied

Theorems 9 and 10 extend the class of voting rules that we can compare using the minimal quota q, yet the comparison should be made for a specific number of candidates m (as for most monotonic scoring rules, the (q, k)-majority criterion gives the same tight quota $q=1$). Thus, we have to use the (q, k, m)-majority criterion. Table 4 presents this comparison for the majority-consistent voting rules that we considered earlier, the proportional veto core, the Borda rule, and the inverse plurality rule when the total number of candidates $m=3,4$.

We see that for the majority-consistent voting rules (except plurality rule), when m, k are small, most of the values of the minimal quota q are equal to 0.5. Interestingly, whenever $m\le 4$ (Table 4) or $k\le 2$ (Table 3), the plurality with runoff rule has exactly the same minimal quotas $q=0.5$ as instant-runoff voting.

We can illustrate the results for the Borda rule and plurality rule using Example 1 presented in Table 2. Candidates a and b are the two ($k=2$) preferred candidates among the total of four ($m=4$) candidates, supported by a mutual majority of 57% voters. That value is less than the minimal quota for the Borda rule ($q=0.625$) and plurality rule ($q=0.667$), and thus those rules might not select a or b. In our example, both rules select candidate c.

3.3 Veto power

The criteria we presented above for majority power also allow us to state a somewhat opposite research question, that is, of veto power. Specifically: how large should a group of voters be in order to be able to block its l least preferred candidates?

This problem is dual to the problem of finding the minimal quota for the mutual majority that has $k=m-l$ preferred candidates. Thus, we immediately can compute the minimal quota for such a group as in the $(q,m-l,m)$-majority criterion.²⁵

Let us define the veto criterion formally. For a given quota q and a given number of least preferred candidates l, we say that a rule satisfies the (q, l)-veto criterion if it satisfies the ($q,m-l,m$)-majority criterion for every m.

Overall, when we compare the rules based on the veto criterion from the most veto-preserving to the least, we get a partial ordering (the same as for the (q, k, m)-majority criterion; see Fig. 1). However, when we compare the rules using the (q, l)-veto criterion, that is, for an arbitrary total number of candidates m, we get a complete ordering for $l>2$ as shown in Table 5. When $l=1$ this ordering is different and is very peculiar, as we discuss below.

Table 5 Measuring veto power: for a given l, the minimal quota q such that the (q, l)-veto criterion is satisfied

When $l=1$, our results highlight the inverse plurality rule as the rule that respects minorities the most: its minimal quota is $q=1/m$. The previous literature arrived at the same conclusion by comparing only the monotonic scoring rules (Baharad and Nitzan 2005, 2007a, b). We extend the comparison to non-scoring rules and confirm that consensus when $l=1$.

However, when $l>1$, we arrive at the opposite conclusion. In that case, the minimal quota q for inverse plurality rule jumps to 1 and, thus, no group of voters (except the entire set) can veto $l>1$ candidates (see Table 4 where $k=m-l$, Table 5, and Theorem 11). The reason is that unless the group coordinates, some of the l candidates may receive very small numbers of lowest positions.

Comparing the results for the veto criterion in Table 5 with the quotas for the (q, k)-majority criterion in Table 3 we see that voting rules differ in their power for the most preferred candidates and the least preferred candidates. Overall, the order of rules remains the same except for the proportional veto core, Black’s rule, the Borda rule, and the inverse plurality rule. Those rules perform better when a group of voters need to veto a candidate, rather than make him win.

Surprisingly, the proportional veto core does not yield the most veto power according to the (q, l)-veto criterion. That is because for each given number of the least preferred candidates l the worst case arises when the total number of candidates is $m=l+1$. In that case voters need to veto all but one candidate, which is the same as forcing the remaining candidate to win.

The situation changes if we restrict our analysis to the case $l\le m/2$ (see Table 6), that is, when one can veto only candidates ranked in the bottom half of her preference order. Comparing the results in Tables 5 and  6 we see that only the proportional veto core changes its relative position and yields the most opportunities to veto not more than half the candidates.

Table 6 Measuring veto power: for a given l, the minimal quota q such that the ($q,m-l,m$)-majority criterion is satisfied whenever $l\le m/2$ and $m\ge 3$

3.4 Other criteria and tradeoffs

In this subsection, we discuss the tradeoffs between the (q, k)-majority criterion, the (q, l)-veto criterion, and other criteria from the literature.

For the general classes of voting rules, satisfying the mutual majority criterion (or the (1 / 2, k)-majority criterion with arbitrary k) is not a concern. For instance, among Condorcet-consistent rules we can highlight the ranked pairs rule introduced by Tideman (1987) and Schulze’s rule (2011), among other iterated positional rules – instant-runoff voting, among positional rules—the median voting rule (Bassett and Persky 1999), Bucklin’s method (see e.g., Tideman 2006), and the majoritarian compromise (Sertel and Yılmaz 1999).

In contrast, for monotonic scoring rules the (q, k)-majority criterion often is out of reach. All scoring rules do not satisfy the (1 / 2, k)-majority criterion for some k. However, for any fixed k, the scoring rule with the scores $s_1=\cdots =s_k=1,s_{k+1}=\cdots =s_m=0$ satisfies the (1 / 2, k)-majority criterion. Below, we consider the tradeoffs for scoring rules in more detail.

For a given voting rule, we can see the tradeoff between majority power (including the majority criterion, and the mutual majority criterion), veto power (including the majority loser criterion), and other criteria from their axiomatic characterizations.

Baharad and Nitzan (2005) prove that the inverse plurality rule is the only non-generalized scoring rule that satisfies the minimal veto criterion.²⁶ Although their minimal veto criterion involves strategic candidates and is different from ours, it shows that the quota $q=1/m$ (for the case of $l=1$ least preferred candidates) characterizes the inverse plurality rule, implying that the (q, k)-majority criterion never is satisfied (for any fixed k, the minimal quota q for the inverse plurality rule equals 1).

Plurality rule is the only non-generalized scoring rule that satisfies the majority criterion (Lepelley 1992; Sanver 2002), implying that if a non-generalized scoring rule satisfies the (1 / 2, 1)-majority criterion for $k=1$, then for any given k the minimal quota necessarily is $q=k/(k+1)$.

Sanver (2002) and Woeginger (2003) prove that a generalized scoring rule cannot simultaneously satisfy the majority criterion and the majority loser criterion. The tradeoff can be illustrated by plurality rule, the Borda rule, and the inverse plurality rule. While plurality rule satisfies the majority criterion, it fails the majority loser criterion. In contrast, the Borda rule and the inverse plurality rule satisfy the majority loser criterion and, hence, fail the majority criterion.

Other impossibility results involving the majority criterion and the majority loser criterion can be found in Theorem 4.2 in Kondratev (2018). Among 37 different criteria only second-order positional dominance (2-PD) is resistant to the 1 / 2-mutual majority criterion. Specifically, no rule satisfies both the 2-PD and 1 / 2-mutual majority criteria.

That impossibility is easy to see from the preference profile in Table 2. There, candidates a and b are supported by a mutual majority of 57% of voters. However, candidate c obtains a higher score than candidates a, b for all convex scoring rules, i.e., c second-order positionally dominates a, b.

We can generalize the latter result from the 1 / 2-mutual majority criterion to the (q, k)-majority criterion for any given k. The next theorem establishes the tradeoff between 2-PD and the (q, k)-majority criterion.

Theorem 12

• 1. If$k \ge 1$and$q<2k/(3k+1)$, then no rule satisfies second-order positional dominance and the (q, k)-majority criteria;

• 2. There exists a rule that satisfies both criteria for each$k \ge 1$and each$q\ge 2k/(3k+1)$.²⁷

The theorem also shows that the 2-PD and q-mutual majority criteria are compatible if and only if $q\ge 2/3$.

4 Concluding remarks

We introduced and studied the quantitative properties of voting rules that we call the (q, k)-majority criterion and the (q, l)-veto criterion. Those criteria allow us to study how decisive each voting rule is, that is, the extent to which a voting rule respects majority power and/or veto power.

Our criteria form a partial ordering over the studied voting rules (see Fig. 1). In general, the rule with more majority power also has more veto power. Instant-runoff voting has the most majority power and veto power, while plurality rule appears to have relatively low levels of majority power and veto power (see Tables 3, 5, 6).

Our results provide several new insights and raise a number of open questions; we list them briefly below.

Minority protection Somewhat surprisingly, inverse plurality rule (anti-plurality rule or negative voting) also yields low veto power, although it previously was assumed to give minorities the most such veto power (Baharad and Nitzan 2005, 2007a, b). The discrepancy comes from the fact that veto power previously was assumed to be used against only one least-preferred candidate, $l=1$. In that case, our results agree with the literature, while when $l>1$ we show that the inverse plurality rule may require the entire set of voters, $q=1$, to veto those l candidates (see Theorem 11 and Tables 5, 6). An open question here is whether that peculiarity of the inverse plurality rule also emerges in the strategic voting framework of Baharad and Nitzan (2002, 2007b), Grofman et al. (2017) and Moulin (1981, 1982, 1983).

For each specific setting (fixed number of preferred candidates and total number of candidates), the partial order becomes complete. Surprisingly, in the complete orderings, the direct relation between majority power and veto power disappears. Specifically, the proportional veto core, the Borda rule, and Black’s rule have less majority power than plurality rule (see Table 3), but at the same time they have more veto power than plurality with runoff (see Tables 5, 6). That is possible since the three rules are not comparable with plurality rule and plurality with runoff in the partial orderings (see Fig. 1). Thus, the proportional veto core, the Borda rule, and Black’s rule are, perhaps, the best rules for protecting minorities.

Among those three rules, Black’s rule seems to have a more distinguished set of properties. From a theoretical point of view, the first stage of Black’s rule, the Condorcet rule (pairwise majority rule), works well because it is strategy-proof in a large domain (Campbell and Kelly 2003) and satisfies independence of irrelevant alternatives (Dasgupta and Maskin 2008; Miller 2019). Statistically, Black’s rule is much less manipulable than the Borda rule (Aleskerov and Kurbanov 1999; Aleskerov et al. 2012; Green-Armytage et al. 2016), however, the Borda rule provides slightly more social utility efficiency (Merrill 1984). In three-candidate elections, Black’s rule encounters voting paradoxes less frequently (Plassmann and Tideman 2014) and selects the “best” candidate more often (Tideman and Plassmann 2014). In real elections, however, both rules generally select the same candidate despite the fact that a Condorcet winner usually exists (Feld and Grofman 1992).

The proportional veto core consistently gives the most veto power to minorities whenever they have a mutual dislike of no more than half the candidates (see Theorem 9 and Table 6). However, practical uses of that rule are limited since it is not easy to compute even for a small total number of candidates, it often selects more than one winner and is extremely manipulable. A practical rule that consistently gives most veto power to minorities still is an open question.

Tradeoffs We find that the (q, k)-majority criterion is compatible with various standard desirable properties for voting rules. The only exception is the second-order positional dominance criterion. For each $q<2k/(3k+1)$, Theorem 12 shows that every rule that satisfies the second-order positional dominance criterion does not satisfy the (q, k)-majority criterion.

Condorcet and Dodgson Our results highlight the distinction between different Condorcet extensions. Most of the Condorcet-consistent rules satisfy the mutual majority criterion (see footnote 18), and we study several important exceptions: Condorcet least-reversal, and the methods of Black, Young, Simpson, and Dodgson.

One specific open question arises from the incomplete result regarding Dodgson’s rule: in contrast to other findings, Theorem 8 does not specify the tight bound on the quota. The value of the tight bound seems to be a hard question, as Dodgson’s rule is known to be difficult to work with (Bartholdi et al. 1989; Caragiannis et al. 2016; Hemaspaandra et al. 1997). It is not easy to check whether the profile in Table 1 in the Online Appendix (which we use for several proofs) gives the worst case for each candidate in the group of mutually supported candidates and, at the same time, the best case for some other candidate outside the group.

Limitations of our approach Our criteria do not provide a comparison for voting rules that satisfy the mutual majority criterion: all such rules have the same high level of majority power and veto power. In fact, all of our results for instant-runoff voting hold for an arbitrary voting rule that satisfies the mutual majority criterion. Designing a proper quantitative criteria that would distinguish these rules is an open question.

Another question is generalizing our criteria of majority power and veto power to the framework of multi-winner elections, as, for instance, done to a proportionality degree in Lackner and Skowron (2018) and Skowron (2018). Similarly, an important open question is whether analogous criteria for grading systems–such as approval voting (Brams 2009) as well as majority judgment (Balinski and Laraki 2011)–should be developed.

A more general open question is the analysis of majority power and veto power in practically-relevant scenarios. In this paper the main results are based on the worst-case analysis as it allows us to provide precise estimates for any total number of candidates. Future research can make use of more realistic scenarios inspired by theories of individual decision-making, empirical results, and experiments on voting. A particularly well-developed approach is the one that measures the statistical properties of voting rules, such as Condorcet efficiency (Gehrlein and Lepelley 2017), majority winner and majority loser efficiency (Diss et al. 2018), manipulability (Aleskerov and Kurbanov 1999; Aleskerov et al. 2012; Green-Armytage et al. 2016), and others.

In studying majority power and veto power one is not restricted to single-winner elections wherein one representative or ruler is selected. Alternative ways of protecting minorities range from using two voting periods (Fahrenberger and Gersbach 2010), allowing storable votes in multi-issue elections (Casella 2005), direct democracy, participatory budgeting (Cabannes 2004), and multi-winner elections.

Resume As a final takeaway, our results suggest that societies that care about the rights of the majority to ensure their most preferred candidates win and their least preferred candidates lose should adopt instant-runoff voting. In contrast, societies that care about the rights of minorities should select Black’s rule.