Majority rule on j-rich ballot spaces

Abstract

Fishburn (Aggregation and revelation of preferences. North Holland, Amsterdam, pp 201–218, 1979) proved that majority rule on any proper permutation closed $j\hbox {-rich}$ ballot space is the only social choice function satisfying faithfulness, consistency, cancellation, and neutrality. Alós-Ferrer (Soc Choice Welf 27:621–625, 2006) showed that neutrality was not needed for Fishburn’s result as long as the ballot space has no restriction on ballot sizes. In this paper, we show that the Alós-Ferrer result can be extended to a much larger class of ballot spaces.

1 Introduction

Fishburn (1979) proved that majority rule is the only social choice function satisfying neutrality, consistency, faithfulness, and cancellation. In his model, a social choice function takes as input a ballot response profile and outputs a nonempty subset of winning alternatives. Each voter submits a nonempty subset of alternatives called a ballot and the set of all admissible ballots is called the ballot space. A voter’s ballot consists of all approved alternatives. In this context, a ballot response profile is a function $\pi$ with domain a ballot space ${\mathcal B}$ and range the set of nonnegative integers with the interpretation that $\pi (B)$ is number of voters that chose the ballot B. Majority rule is the social choice function where the output is the set of alternatives with the maximum number of approvals.

Alós-Ferrer (2006) showed that the axiom of neutrality was not needed for Fishburn’s theorem. Moreover, he was able to give a much simpler argument than Fishburn’s original proof. This simplicity comes at a price. Namely, Alós-Ferrer assumed that the ballot space is the set of all proper subsets of the set of alternatives. In this case, majority rule is known as Approval Voting and so Alós-Ferrer showed that Approval Voting is the only social choice function satisfying consistency, faithfulness, and cancellation. Fishburn’s theorem, however, is true for ballot spaces where the cardinality of the ballot maybe restricted.¹ One example of such a restriction is when each voter can approve of at most 3 alternatives. This leads to the following question. Does there exist an extension of the Alós-Ferrer theorem to a larger class of ballot spaces? To follow our earlier example, suppose there are 4 or more alternatives and each voter can submit a ballot of cardinality at most 3, is majority rule the only social choice function satisfying consistency, faithfulness, and cancellation? It turns out that the answer to the last question is yes and it follows as a consequence of the main result of this paper.

In this paper, we will focus on ballot spaces where there exists a positive integer j such that all ballots of size j belong to our ballot space. We will call this type of ballot space, $j\hbox {-rich}$. For example, if X is the finite set of m alternatives with $m \ge 4$, then the ballot space consisting of all singleton subsets of X, all two element subsets of X and one $3\hbox {-element}$ subset of X is a $1\hbox {-rich}$ ballot space and a $2\hbox {-rich}$ ballot space. By allowing j to vary from 1 to $m - 1$ we can see that the class of $j\hbox {-rich}$ ballot spaces is more general than the class of ballot spaces dealt with by Fishburn. It turns out that majority rule is the only rule fulfilling faithfulness, cancellation, and consistency in a given $j\hbox {-rich}$ ballot space if $j\ge 3$ with $m\ge 4$. This is one of the main results of this paper. The other main result deals with the class of $j\hbox {-rich}$ ballot spaces ${\mathcal B}$ that are closed under permutations. This means that if $B \in {\mathcal B}$ and $B' \subseteq X$ satisfies $|B'| = |B|$, then $B' \in {\mathcal B}$. Based on the number m of alternatives, we give a complete classification of the permutation closed $j\hbox {-rich}$ ballot spaces in which majority rule is the only social choice function satisfying faithfulness, cancellation, and consistency. This second result is an extension of the Alós-Ferrer theorem.

In the next section we establish notation, define our terms, and state the two main results of this paper. The model we use is the one used by Fishburn and Alós-Ferrer. In Sect. 3, two examples are given to show why our results do not hold for all possible permutation closed $j\hbox {-rich}$ ballot spaces with $j \le 2$. Section 3 also contains a proof of the extended Alós-Ferrer theorem. In Sect. 4, we establish the necessity of the other axioms by providing independence examples. Finally, since it is a bit technical, a proof of the first main result is given in an appendix at the end of the paper.

2 Notation, terminology, and the two main results

The finite set of alternatives is $X = \{x_1, \ldots , x_m\}$ with $m \ge 2$. The set of all subsets of X is denoted by P(X) and

$$\begin{aligned} P_{ne}(X) = \{ A \in P(X) : A \ne \emptyset \}. \end{aligned}$$

A nonempty subset ${\mathcal B}$ of $P_{ne}(X)$ is called a ballot space and the sets belonging to ${\mathcal B}$ are called ballots. For any integer k belonging to the interval [1, m], the set

$$\begin{aligned} {\mathcal B}_k = \{B \subseteq X : |B| = k\} \end{aligned}$$

is the ballot space consisting of all ballots of size k. We will say that a ballot space ${\mathcal B}$ is $\mathbf {j}\hbox {-rich}$ if ${\mathcal B}_j\subseteq {\mathcal B}$ for some $j\in \{1,\ldots ,m-1\}$. A $j\hbox {-rich}$ ballot space ${\mathcal B}$ will be called a permutation closed$\mathbf {j}\hbox {-rich}$ballot space if, for any permutation $\sigma$ on X and for any $B \in {\mathcal B}$, $\sigma (B)=\{\sigma (x) \ : \ x\in B\} \in {\mathcal B}$. Furthermore, if $X\notin {\mathcal B}$ we will say that ${\mathcal B}$ is a proper permutation closed $\mathbf {j}\hbox {-rich}$ballot space. Notice that a proper permutation closed $j\hbox {-rich}$ ballot space ${\mathcal B}$ is of the form

$$\begin{aligned} {\mathcal B} = \bigcup _{k \in I}{\mathcal B}_k \end{aligned}$$

for some nonempty subset I of $\{1, \ldots , m-1\}$.

The set of natural numbers including 0 is denoted by ${\mathbb {N}}_0$. If ${\mathcal B}$ is a ballot space, then a function $\pi : {\mathcal B} \rightarrow {\mathbb {N}}_0$ is called a ballot response profile or just simply a profile. The set of all profiles on ${\mathcal B}$ is given by ${\mathbb {N}}_0^{{\mathcal B}}$. For any profile $\pi$ and for any B belonging to ${\mathcal B}$, $\pi (B)$ is the number of voters that chose the ballot B. For any $\pi \in {\mathbb {N}}_0^{{\mathcal B}}$ and for any $x \in X$, the number of voters who approve of the alternative x is given by

$$\begin{aligned} v(x, \pi ) = \sum _{B \in {\mathcal B}, x \in B}\pi (B). \end{aligned}$$

The maximum and minimum approval values based on a profile $\pi$ are

$$\begin{aligned} \text {max}\ v(\pi ) = \text {max} \{v(x,\pi ) : x \in X\}\ \text {and}\ \text {min}\ v(\pi ) = \text {min} \{v(x,\pi ) : x \in X\}. \end{aligned}$$

A social choice function on the ballot space ${\mathcal B}$ is any function of the form $f: {\mathbb {N}}_0^{{\mathcal B}} \rightarrow P_{ne}(X)$.² We say that the domain of $f: {\mathbb {N}}_0^{{\mathcal B}} \rightarrow P_{ne}(X)$ is $j\hbox {-rich}$ if the ballot space $\mathcal {B}$ is $j\hbox {-rich}$ and similarly for permutation closed $j\hbox {-rich}$ domain.

Majority rule is the social choice function $F_M: {\mathbb {N}}_0^{{\mathcal B}} \rightarrow P_{ne}(X)$ defined as follows: for any profile $\pi$,

$$\begin{aligned} F_M(\pi ) = \{ x \in X : v(x,\pi ) = \text {max}\ v(\pi )\}. \end{aligned}$$

Notice that $x \in F_M(\pi )$ means that there is no alternative y that obtained more votes than x. If ${\mathcal B} = P_{ne}(X)$, then $F_M$ is called approval voting and is denoted by $F_A$. In this particular case we will call ${\mathcal B}$ the unrestricted ballot space.

For any profiles $\pi , \rho \in {\mathbb {N}}_0^{{\mathcal B}}$, the sum of $\pi$ and $\rho$ is the profile $\pi + \rho$ defined by $(\pi + \rho )(B) = \pi (B) + \rho (B)$ for all $B \in {\mathcal B}$. A social choice function $f: {\mathbb {N}}_0^{{\mathcal B}} \rightarrow P_{ne}(X)$ satisfies consistency if for any profiles $\pi , \rho \in {\mathbb {N}}_0^{{\mathcal B}}$,

$$\begin{aligned} f(\pi ) \cap f(\rho ) \ne \emptyset \ \Rightarrow \ f(\pi + \rho ) = f(\pi ) \cap f(\rho ). \end{aligned}$$

Consistency says that if an alternative x is an acceptable social outcome by two disjoint groups of voters, then x should be an acceptable social outcome for the union of the two groups. Moreover, if another alternative y is not an acceptable outcome for one of the groups, then y should not be part of the social outcome for the union of the two groups. The consistency axiom, sometimes called reinforcement, was introduced independently by Smith (1973), Young (1974), and Fine and Fine (1974).

Next, f satisfies cancellation if, for any $\pi \in {\mathbb {N}}_0^{{\mathcal B}}$,

$$\begin{aligned} v(x, \pi ) = v(y, \pi )\ \text {for all}\ x,y \in X\ \Rightarrow \ f(\pi ) = X. \end{aligned}$$

If all alternatives get the same number of votes, then cancellation implies that every alternative should belong to the social output.

For any ballot $B \in \mathcal B$, the profile where one voter chooses B is denoted by $\pi _B$ or B. So $\pi _B(B) = 1$ and $\pi _B(B') = 0$ for all $B' \ne B$. A social choice function f satisfies faithfulness if, for all $B \in {\mathcal B}$,

$$\begin{aligned} f(\pi _B) = B. \end{aligned}$$

If there is just one voter and that voter submits the ballot B, then faithfulness implies that the social outcome should be B. We can now state the Alós-Ferrer result.

Theorem 1

Approval Voting is the only social choice function on the ballot space $P_{ne}(X)$³ satisfying faithfulness, consistency, and cancellation.

Theorem 1 is just one of many axiomatic characterizations of approval voting and we refer the reader to Fishburn (1978, 1979), Sertel (1988), Baigent and Xu (1991), Goodin and List (2006), Vorsatz (2007), Alcalde-Unzu and Vorsatz (2009), and Sato (2014) for some other characterizations of approval voting. Alós-Ferrer’s theorem is a sharpening of a result due to Fishburn when $\mathcal {B}=P_{ne}(X)$. Fishburn’s theorem involves a larger class of ballot spaces than just the unrestricted ballot space $P_{ne}(X)$.

A social choice function f on a permutation closed $j\hbox {-rich}$ ballot space ${\mathcal B}$ satisfies neutrality if, for any profiles $\pi$ and $\pi '$ and for any permutation $\sigma$ of X,

$$\begin{aligned} \pi '(\sigma (B)) = \pi (B)\ \text {for all}\ B \in {\mathcal B}\ \Rightarrow \ \sigma \left( f(\pi )\right) = f(\pi ') \end{aligned}$$

where $\sigma (A) = \{\sigma (x) : x \in A\}$ for any subset A of X. Neutrality implies that the labeling of the alternatives does not affect the social outcome. We can now state Fishburn’s theorem.

Theorem 2

Majority rule is the only social choice function on a proper permutation closed $j\hbox {-rich}$ ballot space ${\mathcal B}$ satisfying faithfulness, consistency, cancellation, and neutrality.

We show in the next section that Theorem 2 does not go through for all $j\hbox {-rich}$ ballot spaces if the condition of neutrality is dropped. The next theorem, which is one of the main results of this paper, is a classification of the permutation closed $j\hbox {-rich}$ domains in which majority rule is the only function satisfying faithfulness, consistency, and cancellation.

Theorem 3

For $\mathcal {B}$ a permutation closed $j\hbox {-rich}$ ballot space with m alternatives:

• 1. Majority rule is the only rule fulfilling faithfulness, cancellation, and consistency if $m=2$.

• 2. Majority rule is the only rule fulfilling faithfulness, cancellation, and consistency with $m=3$ if and only if $\mathcal {B}\ne \mathcal {B}_1$.

• 3. Majority rule is the only rule fulfilling faithfulness, cancellation, and consistency with $m\ge 4$ if and only if $\mathcal {B}\notin \{\mathcal {B}_1,\mathcal {B}_2,\mathcal {B}_1\cup \mathcal {B}_2\}$.

Observe that Theorem 3 is a generalization of the Alós-Ferrer result (Theorem 1 above) since ${\mathbb {N}_0}^{{P_{ne}}(X)}$ is a permutation closed $(m - 1)\hbox {-rich}$ domain for all $m\ge 2$. For the case of $m\ge 4$, and so $j \ge 3$, we can drop the requirement that the ballot space is permutation closed. This leads to the second main result of this paper.

Theorem 4

If $m \ge 4$ and $2< j <m$, then majority rule is the only social choice function on a $j\hbox {-rich}$ domain satisfying faithfulness, consistency, and cancellation.

The proof of Theorem 4 is a bit technical and will be given in the appendix at the end of the paper. To help motivate both theorems, we offer the following example.

Example 1

Let $X = \{x_1, x_2, x_3, x_4, x_5\}$ and let ${\mathcal B} = {\mathcal B}_1 \cup {\mathcal B}_2 \cup {\mathcal B}_3$. So there are 5 alternatives and ${\mathcal B}$ is a $3\hbox {-rich}$ ballot space. Assume $f: {\mathbb {N}}_0^{{\mathcal B}} \rightarrow P_{ne}(X)$ satisfies faithfulness, consistency, and cancellation and let $\rho = \{x_1, x_2, x_3\} + \{x_4\}$. We will show that $f(\rho ) = F_M(\rho ) = \{x_1, x_2, x_3, x_4\}$.

By faithfulness, $f(\{x_5\}) = \{x_5\}$ and, by cancellation, $f(\rho + \{x_5\}) = X$. In order to avoid a contradiction based on consistency, we get $f(\rho ) \cap f(\{x_5\}) = \emptyset$. Thus, $x_5 \not \in f(\rho )$ and so $f(\rho ) \subseteq \{x_1, x_2, x_3, x_4\}$.

Assume that $f(\rho )$ is a proper subset of $\{x_1, x_2, x_3, x_4\}$. So there exist $i \ne j$ in $\{1, 2, 3, 4\}$ such that $x_i \in f(\rho )$ and $x_j \not \in f(\rho )$.

Let $\{x_k,x_l\}=X{\setminus } \{x_i,x_j,x_5\}$ and consider that by cancellation we have that $f( \{x_i,x_j,x_5\} + \{x_k\} + \{x_l\})=X$. Using this fact we get

$$\begin{aligned} f(\{x_i\} + \{x_j\} + \{x_5\} )&= f(\{x_i\} + \{x_j\} + \{x_5\} ) \cap X \\&= f(\{x_i\} + \{x_j\} + \{x_5\} ) \cap f( \{x_i,x_j,x_5\} + \{x_k\} + \{x_l\})\\&=f\left( \{x_i\} + \{x_j\} + \{x_5\}\right. \\&\quad \left. +\, \{x_i,x_j,x_5\} + \{x_k\} + \{x_l\}\right) \text { By consistency }\\&=f( \{x_i,x_j,x_5\} +\{x_i\} + \{x_j\} + \{x_5\}+ \{x_k\} + \{x_l\}) \\&= f( \{x_i,x_j,x_5\}) \cap f\left( \{x_i\} + \{x_j\}\right. \\&\quad \left. +\, \{x_5\}+ \{x_k\} + \{x_l\}\right) \text { By consistency }\\&= f( \{x_i,x_j,x_5\}) \cap X \text { By cancellation}\\&= f( \{x_i,x_j,x_5\}). \end{aligned}$$

Hence by faithfulness, we have that⁴

$$\begin{aligned} f(\{x_i\} + \{x_j\} + \{x_5\} ) = f(\{x_i, x_j, x_5\}) = \{x_i, x_j, x_5\}, \end{aligned}$$

and a similar argument will show

$$\begin{aligned} f(\{x_i\} + \{x_j\}) \cap f(\{x_5\} + \rho ) = \{x_i, x_j\}. \end{aligned}$$

Therefore,

$$\begin{aligned} f(\{x_i\} + \{x_j\} + \{x_5\}) \cap f(\rho ) = \{x_i\} \end{aligned}$$

and

$$\begin{aligned} f(\{x_i\} + \{x_j\}) \cap f(\{x_5\} + \rho ) = \{x_i, x_j\}. \end{aligned}$$

But this violates consistency since

$$\begin{aligned} f(\{x_i\} + \{x_j\} + \{x_5\}) \cap f(\rho )= & {} f(\{x_i\} + \{x_j\} +\{x_5\} + \rho )\\= & {} f(\{x_i\} + \{x_j\}) \cap f(\{x_5\} + \rho ). \end{aligned}$$

This final contradictions tell us that $f(\rho )$ is not a proper subset of $\{x_1, x_2, x_3, x_4\}$. So $f(\rho ) = F_M(\rho )$ and this completes the example.

In the next section we give two examples showing why the bound for j in Theorem 4 must be greater than or equal to 3. We will then use these examples to carefully prove Theorem 3.

3 Two examples and the proof of Theorem 3

Plurality rule is the special case of majority rule where each voter votes for one alternative. So the corresponding ballot space is ${\mathcal B}_1$. We now give a simple example of a social choice function f on ${\mathcal B}_1$ that is not equal to plurality rule and yet f satisfies faithfulness, consistency, and cancellation.

Example 2

Define the social choice function $f: {\mathbb {N}}_0^{{\mathcal B}_1} \rightarrow P_{ne}(X)$ by

$$\begin{aligned} f(\pi ) = \left\{ \begin{array}{cl} X &{} \text {if}\ F_M(\pi ) = X\\ \text {min}\ F_M(\pi ) &{} \text {otherwise} \end{array} \right. \end{aligned}$$

where

$$\begin{aligned} \text {min}\ F_M(\pi ) = \{x_i\in F_M(\pi ) : i \le j\ \forall \ x_j \in F_M(\pi )\}. \end{aligned}$$

Notice that $\text {min}\ F_M(\pi )$ is the unique element belong to the majority output having minimum index. Note that cancellation is trivial since universal-tie profiles result in the first case of the rule. Moreover, since the ballot space is $\mathcal {B}_1$, it is not hard to verify that f satisfies faithfulness and consistency.

Example 2 show why neutrality is needed in Fishburn’s theorem when the ballot space is ${\mathcal B}_1$ and $m\ge 3$. In the case that $m=2$ it turns out that $f=F_M$.

We now explore the permutation closed $j\hbox {-rich}$ ballot spaces $\mathcal {B}_2$ and $\mathcal {B}_1\cup \mathcal {B}_2$ when $m\ge 4$.

Example 3

Let $\mathcal {B}\in \{\mathcal {B}_2,\mathcal {B}_1\cup \mathcal {B}_2\}$ and let $\sigma :X\rightarrow X$ be the cyclic permutation $\sigma (x_i)=x_{i+1}$ for $i = 1, \ldots m$ with the convention that $x_{m+1}=x_1$. Define the social choice function $f_\sigma : {\mathbb {N}}_0^{{\mathcal B}_1} \rightarrow P_{ne}(X)$ by $f_\sigma (\pi )={F_{M}}(\widehat{\pi })$ for all profiles $\pi \in {\mathbb {N}_0}^\mathcal {B}$ where

For any profile $\pi$ and for any $x \in X$,

$$\begin{aligned} v(x,\widehat{\pi })&=v(x,\pi )+[v(x,\pi )+v(\sigma (x),\pi )]+[v(\sigma ^{-1}(x),\pi )+v(x,\pi )]\\&=3\cdot v(x,\pi )+v(\sigma (x),\pi )+v(\sigma ^{-1}(x),\pi ). \end{aligned}$$

Therefore, $f_\sigma (\pi )$ is the set of all x in X that maximize the sum

$$\begin{aligned} v(x,\widehat{\pi }) = 3\cdot v(x,\pi )+v(\sigma (x),\pi )+v(\sigma ^{-1}(x),\pi ). \end{aligned}$$

(1)

By using Eq. (1) we now show that $f_\sigma$ satisfies faithfulness. If $\pi = \pi _B$ for some $B \in {\mathcal B}$ and $x \in B$, then

$$\begin{aligned} v(x, \widehat{\pi }) \ge 3\cdot v(x,\pi ) = 3. \end{aligned}$$

If $y \in X {\setminus } B$, then $v(y, \pi ) = 0$ and so

$$\begin{aligned} v(y, \widehat{\pi }) = v(\sigma (y),\pi )+v(\sigma ^{-1}(y),\pi ) \le 2. \end{aligned}$$

Thus,

$$\begin{aligned} f_\sigma (\pi _B) = F_M(\widehat{\pi _B}) \subseteq B. \end{aligned}$$

If $B \in \mathcal {B}_1$, then, since $f_\sigma (\pi _B)$ is nonempty, $f_\sigma (\pi _B) = B$. If $B \in \mathcal {B}_2$, then $B = \{x,y\}$ for some $x \ne y$ in X. If $y \ne \sigma (x)$ and $y \ne \sigma ^{-1}(x)$, then

$$\begin{aligned} v(x, \widehat{\pi }) = v(y, \widehat{\pi }) = 3 \end{aligned}$$

and so $f_\sigma (\pi _B) = B$. Finally, if $y \in \{\sigma (x), \sigma ^{-1}(x)\}$, then

$$\begin{aligned} v(x, \widehat{\pi }) = v(y, \widehat{\pi }) = 4 \end{aligned}$$

and again $f_\sigma (\pi _B) = B$. We now know that $f_\sigma$ satisfies faithfulness.

Suppose $\pi \in {\mathbb {N}_0}^\mathcal {B}$ satisfies $v(x,\pi )=v(y,\pi ) = k$ for all $x,y\in X$. Using equation (1) we get $v(x,\widehat{\pi })=v(y,\widehat{\pi }) = 5k$ for all $x,y\in X$. Since $F_M$ satisfies cancellation, $f_\sigma (\pi ) = F_M(\widehat{\pi }) = X$. Thus, $f_\sigma$ satisfies cancellation.

To prove consistency we need the following observation. For any $\pi ,\rho \in {\mathbb {N}_0}^\mathcal {B}$,

Therefore,

$$\begin{aligned} \widehat{\pi +\rho }=\widehat{\pi }+\widehat{\rho } \text { for all } \pi ,\rho \in {\mathbb {N}_0}^\mathcal {B}. \end{aligned}$$

Now suppose $f_\sigma (\pi )\cap f_\sigma (\rho )\ne \emptyset$. Using the previous observation and the fact that majority rule is consistent we get

$$\begin{aligned} f_\sigma (\pi )\cap f_\sigma (\rho )= {F_{M}}\left( \widehat{\pi }\right) \cap {F_{M}}\left( \widehat{\rho }\right) ={F_{M}}\left( \widehat{\pi }+\widehat{\rho } \right) ={F_{M}}\left( \widehat{\pi +\rho }\right) = f_\sigma (\pi +\rho ). \end{aligned}$$

Hence $f_\sigma$ satisfies consistency.

Finally , we will show that $f_\sigma$ is not equal to $F_M$. Consider the profile

Since $v(x,\pi )=2$ for $x\in \{x_1,x_2,x_3\}$ and $v(x,\pi )=0$ for $x\in X{\setminus } \{x_1,x_2,x_3\}$, it follows that ${F_{M}}(\pi )=\{x_1,x_2,x_3\}$. Using Eq. (1) and the fact that $\sigma (x_1) = x_2 = \sigma ^{-1}(x_3)$ we get

$$\begin{aligned} v(x_2, \widehat{\pi }) = 3 \cdot v(x_2, \pi ) + v(x_3, \pi ) + v(x_1, \pi ) = 10. \end{aligned}$$

In general,

$$\begin{aligned} v(x,\widehat{\pi })= {\left\{ \begin{array}{ll} 8 &{} \text {if } x=x_1,x_3 \\ 10 &{} \text {if } x=x_2 \\ 2 &{} \text {if } x=x_4,x_m \text { and } x_4\ne x_m \\ 4 &{} \text {if } x=x_m \text { and } x_4= x_m \\ 0 &{} \text {otherwise. } \end{array}\right. } \end{aligned}$$

Therefore, $f_\sigma (\pi )=\{x_2\}\ne {F_{M}}(\pi )$ and we’re done.

This example show why neutrality is needed in Fishburn’s theorem when the ballot space is either ${\mathcal B}_2$ or ${\mathcal B}_1 \cup {\mathcal B}_2$ when $m\ge 4$.⁵ Surprisingly, when $m=3$ it turns out that $f_\sigma ={F_{M}}$. Theorem 4 shows that for any other $j\hbox {-rich}$ ballot space neutrality is not needed.

Our proof of Theorem 3 will involve the following notation. For any $j\hbox {-rich}$ ballot space ${\mathcal B}$, let

$$\begin{aligned} j_{max}({\mathcal B}) = \text {max}\ \{j \in \{1, \ldots , m - 1\} : {\mathcal B}_j \subseteq {\mathcal B}\}. \end{aligned}$$

For example, if ${\mathcal B} = {\mathcal B}_1\ \cup \ {\mathcal B}_2$, then ${\mathcal B}$ is $1\hbox {-rich}$, $2\hbox {-rich}$ and $j_{max}({\mathcal B}) = 2$. Using this notation, we can rephrase Theorem 3 as follows:

Theorem 5

Majority rule is the only rule fulfilling faithfulness, cancellation, and consistency in a given permutation closed $j\hbox {-rich}$ domain ${\mathbb {N}_0}^\mathcal {B}$ with m alternatives if and only if

$$\begin{aligned} j_{max}(\mathcal {B})\ge \min \{m-1,3\}. \end{aligned}$$

Proof

$(\Rightarrow )$ Let ${\mathcal B}$ be a permutation closed $j\hbox {-rich}$ ballot space and assume

$$\begin{aligned} j_{max}({\mathcal B}) < \text {min} \{m - 1, 3\}. \end{aligned}$$

Then $j_{max}({\mathcal B}) = 1$ and $m \ge 3$ or $j_{max}({\mathcal B}) = 2$ and $m \ge 4$. In the first case, ${\mathcal B} = {\mathcal B}_1$ and $m \ge 3$. In the second case, ${\mathcal B} \in \{{\mathcal B}_1 \cup {\mathcal B}_2, {\mathcal B}_2\}$ and $m \ge 4$. Examples 2 and 3 given above show that in both cases majority rule is not the only rule satisfying faithfulness, cancellation, and consistency.

$(\Leftarrow )$ Suppose $f: {\mathbb {N}}_0^{{\mathcal B}} \rightarrow P_{ne}(X)$ satisfies faithfulness, cancellation, and consistency and ${\mathcal B}$ is a permutation closed $j\hbox {-rich}$ ballot space such that $j_{max}({\mathcal B}) \ge \text {min} \{m - 1, 3\}$. We will show that f is majority rule.

If $m = 2$, then $j_{max}({\mathcal B}) = 1$ and ${\mathcal B} = {\mathcal B}_1$. If $m = 3$, then $j_{max}({\mathcal B}) = 2$ and ${\mathcal B} \in \{{\mathcal B}_1 \cup {\mathcal B}_2, {\mathcal B}_2\}$. If ${\mathcal B} = {\mathcal B}_1$ and $m = 2$ or ${\mathcal B} = {\mathcal B}_1 \cup {\mathcal B}_2$ and $m = 3$, then ${\mathcal B} = P_{ne}(X) {\setminus } \{X\}$. In these cases, the Alós-Ferrer Theorem implies that f is majority rule.

We now consider the case where ${\mathcal B} = {\mathcal B}_2$ and $m = 3$. Let $\pi$ be an arbitrary nontrivial profile. If $\pi (B) = 0$ for some $B \in {\mathcal B}_2$, then there exists $x \in X$ such that $x \in B'$ for all $B' \in {\mathcal B}_2$ such that $\pi (B') > 0$. By faithfulness, $x \in f(\pi _B)$ for all $B \in B_2$ such that $\pi (B) > 0$. Therefore,

$$\begin{aligned} \bigcap _{\pi (B) > 0}\ f(\pi (B) \cdot \pi _B) \ne \emptyset . \end{aligned}$$

Using the fact that both f and $F_m$ are consistent and faithful we get

$$\begin{aligned} f(\pi ) = \bigcap _{\pi (B)> 0}\ f(\pi (B) \cdot \pi _B) = \bigcap _{\pi (B) > 0}\ F_M(\pi (B) \cdot \pi _B) = F_M(\pi ). \end{aligned}$$

If the profile $\pi$ satisfies, $\pi (B) > 0$ for all $B \in {\mathcal B}_2$, then let

$$\begin{aligned} j' = \text {min} \{\pi (B) : B \in {\mathcal B}_2\}. \end{aligned}$$

Next, we introduce the profiles $\rho _1$ and $\rho _2$ defined by

$$\begin{aligned} \rho _1(B) = \pi (B) - j'\ \text {and}\ \rho _2(B) = j' \end{aligned}$$

for all $B \in {\mathcal B}_2$. Observe that there exists $B' \in {\mathcal B}_2$ such that $\rho _1(B') = 0$. Therefore, by the previous argument, $f(\rho _1) = F_M(\rho _1)$. By cancellation, $f(\rho _2) = X$. Since $\pi = \rho _1 + \rho _2$ and $F_M(\rho _2) = X$ it follows from consistency that

$$\begin{aligned} f(\pi ) = f(\rho _1) = F_M(\rho _1) = F_M(\pi ). \end{aligned}$$

It now follows that $f = F_M$.

The final case is when $m \ge 4$. In this case, by Theorem 4, f has to be majority rule and we’re done.

4 Independence examples

It is not possible to remove any of the axioms in Theorems 3 and 4 and still uniquely describe majority rule. In other words, there exist social choice functions that satisfy only two out of the three axioms. Following (Duddy and Piggins 2013) we define the mean based rule $F_{mean}$ on the unrestricted ballot space $P_{ne}(X)$ as follows: for any profile $\pi$,

where

The rule $F_{mean}$ is faithful, cancellative, and neutral but not consistent. However, Duddy and Piggins showed that $F_{mean}$ satisfies a modified version of consistency.

Our next example is a weighted refinement of Approval Voting. Define $F_{w}$ on $P_{ne}(X)$ as follows: for any profile $\pi$,

$$\begin{aligned} F_w(\pi )=\{ x\in F_A(\pi ):\ w(x,\pi ) \le w(y,\pi ) \; \forall \; y\in F_A(\pi ) \} \end{aligned}$$

where

$$\begin{aligned} w(x,\pi )=\sum _{B\in P_{ne}(X),\ x \in B} \left|{B} \right|\ \pi (B). \end{aligned}$$

Notice that $F_w(\pi ) \subseteq F_A(\pi )$ for any profile $\pi$. The rule $F_w$ rule is faithful, consistent and neutral but not cancellative. Our third example is inverse approval voting$F_{-A}$ defined as follows: for any $\pi \in {\mathbb {N}}_0^{P_{ne}(X)}$,

$$\begin{aligned} F_{-A}(\pi ) = \{x \in X : v(x, \pi ) = \text {min}\ v(\pi )\}. \end{aligned}$$

By Theorem 1 in Ninjbat (2013), $F_{-A}$ is consistent, cancellative and neutral but not faithful. See also Theorem 2 in Alcalde-Unzu and Vorsatz (2014) where the function $F_{-A}$ is called Disapproval Voting. Finally, the ballot aggregation functions $f_1$, $f_2$, and $f_3$ given on page 96 in Xu (2010) are three more examples of social choice functions that satisfy exactly two out of the three axioms in Theorem 3.

Appendix

To prove Theorem 4 we will assume that $m \ge 4$, ${\mathcal B}$ is a j-rich ballot space for some $j \ge 3$, and $f: {\mathbb {N}}_0^{{\mathcal B}} \rightarrow P_{ne}(X)$ is a social choice rule satisfying faithfulness, consistency, and cancellation. We want to show that f is majority rule, i.e.,

$$\begin{aligned} f(\pi ) = F_M(\pi ) \end{aligned}$$

for any profile $\pi$. This proof will involve the following notation. For each alternative $x_i\in X$, let the profile $\rho _{x_i}$ be the profile that consists of each of the j sized ballots containing $x_i$. That is,

$$\begin{aligned} \rho _{x_i} = \sum _{B \in {\mathcal B}_j, x_i \in B}B. \end{aligned}$$

For example, if $X = \{x_1, x_2, x_3, x_4\}$ and $j = 3$, then

$$\begin{aligned} \rho _{x_1} = \pi _{\{x_1, x_2, x_3\}} + \pi _{\{x_1, x_2, x_4\}} + \pi _{\{x_1, x_3, x_4\}}. \end{aligned}$$

In this case,

$$\begin{aligned} v(x_1, \rho _{x_1}) = 3\ \text {and}\ v(x_2, \rho _{x_1}) = v(x_3, \rho _{x_1}) = v(x_4, \rho _{x_1}) = 2. \end{aligned}$$

In the general case,

$$\begin{aligned} v(x_i, \rho _{x_i}) = \left( {\begin{array}{c}m - 1\\ j - 1\end{array}}\right) \ \text {and}\ v(x_t, \rho _{x_i}) = \left( {\begin{array}{c}m - 2\\ j - 2\end{array}}\right) \end{aligned}$$

for all $t \ne i$. It follows from consistency and faithfulness that $f(\rho _{x_i}) = \{x_i\}$. For any nonempty subset I of $\{1, \ldots , m\}$ let

$$\begin{aligned} \rho _I = \sum _{i \in I} \rho _{x_i}\ \text {and}\ B_I = \{x_i : i \in I\}. \end{aligned}$$

If $|I| = k$, then

$$\begin{aligned} v(x_i, \rho ) = \left( {\begin{array}{c}m - 1\\ k - 1\end{array}}\right) + (k - 1) \cdot \left( {\begin{array}{c}m - 2\\ k - 2\end{array}}\right) \end{aligned}$$

for all $i \in I$ and

$$\begin{aligned} v(x_t, \rho ) = k \cdot \left( {\begin{array}{c}m - 2\\ k - 2\end{array}}\right) \end{aligned}$$

for all $t \in \{1, \ldots , m\} {\setminus } I$. Therefore,

$$\begin{aligned} F_M(\rho _I) = B_I. \end{aligned}$$

We want to show that $f(\rho _I) = B_I$ as well. The next lemma shows that this equality holds when $|I| = j$ or $j - 1$.

Lemma 1

If $|I| \in \{j, j - 1\}$, then

$$\begin{aligned} f(\rho _I) = B_I. \end{aligned}$$

Proof

Assume $|I| = j$ and note that $B_I \in {\mathcal B}$ since ${\mathcal B}$ is $j\hbox {-rich}$. Let $\alpha$ and $\beta$ be the positive integers satisfying

$$\begin{aligned} \alpha = v(x_i, \rho _I)\ \text {and}\ \beta = v(x_j, \rho _I) \end{aligned}$$

for some $i \in I$ and $j \in \{1, \ldots , m\} {\setminus } I$. Notice that $\alpha > \beta$. Next, let

$$\begin{aligned} \widehat{\rho } = \sum _{i=1}^m \rho _{x_i} \end{aligned}$$

and observe that $f(\widehat{\rho }) = X$ by cancellation. Let $\gamma$ be the positive integer

$$\begin{aligned} \gamma = v(x, \widehat{\rho }) \end{aligned}$$

for any $x \in X$. We now compare the two profiles:

$$\begin{aligned} \gamma \cdot \rho _I\ \quad \ \text {and}\ \quad \ [\beta \cdot \widehat{\rho } + \gamma (\alpha - \beta ) \cdot B_I]. \end{aligned}$$

For any $x_i \in B_I$,

$$\begin{aligned} v(x_i, \gamma \cdot \rho _I) = \gamma v(x_i, \rho _I) = \gamma \alpha \end{aligned}$$

and

$$\begin{aligned} v(x_i, \beta \cdot \widehat{\rho } + \gamma (\alpha - \beta ) \cdot B_I) = \beta \gamma + \gamma (\alpha - \beta ) = \gamma \alpha . \end{aligned}$$

Next, for any $x_j \in X {\setminus } B_I$,

$$\begin{aligned} v(x_j, \gamma \cdot \rho _I) = \gamma v(x_j, \rho _I) = \gamma \beta \end{aligned}$$

and

$$\begin{aligned} v(x_j, \beta \cdot \widehat{\rho } + \gamma (\alpha - \beta ) \cdot B_I) = \beta \gamma . \end{aligned}$$

We now know that

$$\begin{aligned} v(x, \gamma \cdot \rho _I) = v(x, \beta \cdot \widehat{\rho } + \gamma (\alpha - \beta ) \cdot B_I) \end{aligned}$$

for all $x \in X$. Let $I' = \{1, \ldots , m\} {\setminus } I$ and observe that

$$\begin{aligned} \rho _I + \rho _{I'} = \widehat{\rho }. \end{aligned}$$

Therefore,

$$\begin{aligned} v(x, \gamma \rho _I + \gamma \rho _{I'}) = v(x, \gamma \cdot \widehat{\rho }) = \gamma ^2 \end{aligned}$$

for all $x \in X$. Using the previous equation and fact that

$$\begin{aligned} v(x, \gamma \cdot \rho _I) = v(x, \beta \cdot \widehat{\rho } + \gamma (\alpha - \beta ) \cdot B_I) \end{aligned}$$

for all $x \in X$ it follows that

$$\begin{aligned} v(x, [ \gamma \rho _{I'} + \beta \cdot \widehat{\rho } + \gamma (\alpha - \beta ) \cdot B_I)]) = \gamma ^2 \end{aligned}$$

for all $x \in X$ as well. Since f satisfies cancellation we get

$$\begin{aligned} f( \gamma \rho _I + \gamma \rho _{I'}) = f([ \gamma \rho _{I'} + \beta \cdot \widehat{\rho } + \gamma (\alpha - \beta ) \cdot B_I)]) = X. \end{aligned}$$

Therefore, using consistency (many times) we get

$$\begin{aligned} f(\rho _I)&= f(\gamma \rho _I)\\&=f(\gamma \rho _I + [\gamma \rho _{I'} +\beta \cdot \widehat{\rho } + \gamma (\alpha - \beta ) \cdot B_I])\\&=f([\gamma \rho _I + \gamma \rho _{I'}] + \beta \cdot \widehat{\rho } + \gamma (\alpha - \beta ) \cdot B_I)\\&=f(\beta \cdot \widehat{\rho } + \gamma (\alpha - \beta ) \cdot B_I))\\&=f( \gamma (\alpha - \beta ) \cdot B_I))\\&=f(B_I). \end{aligned}$$

Finally, since f is faithful, $f(\rho _I) = f(B_I) = B_I$ and we’re done with the first part of the proof of Lemma 1.

Now assume $|I| = j - 1$ and, as above, let $I' = \{1, \ldots , m\} {\setminus } I$. Using consistency and the first part of this lemma we get

$$\begin{aligned} f\left( \sum _{t \in I'}\ [ \rho _I + \rho _{x_t}] \right) = \bigcap _{t \in I'} \left[ B_I \cup \{x_t\} \right] = B_I. \end{aligned}$$

Note that

$$\begin{aligned} \sum _{t \in I'} [ \rho _I + \rho _{x_t}] = \sum _{i=1}^m \rho _{x_i} + (m - j) \rho _I. \end{aligned}$$

By consistency and cancellation,

$$\begin{aligned} f\left( \sum _{i=1}^m \rho _{x_i} + (m - j) \rho _I \right) = f(\rho _I). \end{aligned}$$

Hence $f(\rho _I) = B_I$.

We are now ready to use Lemma 1 to complete the proof of Theorem 4.

Proof of Theorem 4

Assume that the set

$$\begin{aligned} D = \{ \pi \in {\mathbb {N}}_0^{{\mathcal B}} : f(\pi ) \ne F_M(\pi )\} \end{aligned}$$

is nonempty. So D is the set of profiles where the functions f and $F_M$ disagree. Choose $\rho \in D$ such that $|F_M(\rho )|$ is maximal. This means that if $\pi$ is a profile such that $|F_M(\pi )| > |F_M(\rho )|$, then $f(\pi ) = F_M(\pi )$. Since f is cancellative and $\rho \in D$ it follows that $F_M(\rho ) \ne X$. So

$$\begin{aligned} |F_M(\rho )| \le m - 1. \end{aligned}$$

Assume that there exists $x \in f(\rho )$ such that $x \not \in F_M(\rho )$. We may assume that $x = x_1$. Let

$$\begin{aligned} \ell = \text {max}\ v(\rho ) - v(x_1,\rho ) \end{aligned}$$

and note that $\ell > 0$. Next, let

$$\begin{aligned} \widehat{\rho } = \alpha \rho + \ell \rho _{x_1} \end{aligned}$$

where

$$\begin{aligned} \alpha = \left( {\begin{array}{c}m - 1\\ j - 1\end{array}}\right) - \left( {\begin{array}{c}m - 2\\ j - 2\end{array}}\right) . \end{aligned}$$

Then

$$\begin{aligned} v(x_1, \widehat{\rho }) = \alpha v(x_1, \rho ) + \ell \cdot \left( {\begin{array}{c}m - 1\\ j - 1\end{array}}\right) \end{aligned}$$

and

$$\begin{aligned} v(x_i, \widehat{\rho }) = \alpha v(x_i, \rho ) + \ell \cdot \left( {\begin{array}{c}m - 2\\ j - 2\end{array}}\right) \end{aligned}$$

for all $i \ne 1$. If $v(x_i, \rho ) = \text {max}\ v(\rho ) = [\ell + v(x_1, \rho )]$, then

$$\begin{aligned} v(x_i, \widehat{\rho })&= \alpha \cdot [\ell + v(x_1, \rho )] + \ell \cdot \left( {\begin{array}{c}m - 2\\ j - 2\end{array}}\right) \\&= \alpha v(x_1, \rho ) + \ell \cdot \left( {\begin{array}{c}m - 1\\ j - 1\end{array}}\right) \\&= v(x_1, \widehat{\rho }). \end{aligned}$$

It follows that

$$\begin{aligned} F_M(\widehat{\rho }) = F_M(\rho )\ \cup \{x_1\}. \end{aligned}$$

By our choice of $\rho$ and the fact that $|F_M(\widehat{\rho })| > |F_M(\rho )|$ it follows that

$$\begin{aligned} f(\widehat{\rho }) = F_M(\widehat{\rho }) = F_M(\rho )\ \cup \{x_1\}. \end{aligned}$$

On the other hand, by consistency,

$$\begin{aligned} f(\widehat{\rho }) = f(\rho ) \cap f(\rho _{x_1}) = \{x_1\}. \end{aligned}$$

Since $F_M(\rho )\ \cup \{x_1\} \ne \{x_1\}$ we get a contradiction. It now follows that $f(\rho ) \subset F_M(\rho )$.

Since $f(\rho ) \subset F_M(\rho )$ and $f(\rho ) \ne F_M(\rho )$, there exists $y \in F_M(\rho ) {\setminus } f(\rho )$. Let $x \in X {\setminus } F_M(\rho )$ and $z \in f(\rho )$. We may assume that $x = x_1$, $y = x_2$, and $z = x_3$. As above, let

$$\begin{aligned} \ell = \text {max}\ v(\rho ) - v(x_1,\rho ) \end{aligned}$$

and note that $\ell > 0$. We now introduce the profile

$$\begin{aligned} \mu = \alpha \rho + \ell [ \rho _{x_1} + \rho _{x_2} + \cdots + \rho _{x_j} ]. \end{aligned}$$

By our choice of $\rho$ we know that

$$\begin{aligned} f(\alpha \rho + \ell \rho _{x_1}) = F_M(\alpha \rho + \ell \rho _{x_1}) = F_M(\rho ) \cup \{x_1\}. \end{aligned}$$

Using consistency and Lemma 1,

$$\begin{aligned} f\left( \ell [ \rho _{x_2} + \cdots + \rho _{x_j} ]\right) = \{x_2, \ldots , x_j\}. \end{aligned}$$

Using consistency and the fact that $x_2, x_3 \in F_M(\rho )$ we get

$$\begin{aligned} f(\mu ) = f(\alpha \rho + \ell \rho _{x_1}) \cap f\left( \ell [ \rho _{x_2} + \cdots + \rho _{x_j} ]\right) \supseteq \{x_2,x_3\}. \end{aligned}$$

Next, using consistency and Lemma 1, we get

$$\begin{aligned} f\left( \ell [ \rho _{x_1} + \cdots + \rho _{x_j} ]\right) = \{x_1, \ldots , x_j\}. \end{aligned}$$

Since $x_3 \in f(\rho ) = f(\alpha \rho )$ and $x_3 \in f\left( \ell [ \rho _{x_1} + \cdots + \rho _{x_j} ]\right)$ it follows that

$$\begin{aligned} f(\mu ) = f(\alpha \rho ) \cap f\left( \ell [ \rho _{x_1} + \cdots + \rho _{x_j} ]\right) . \end{aligned}$$

Since $x_2 \not \in f(\rho ) = f(\alpha \rho )$ it follows from the previous equation that $x_2 \not \in f(\mu )$. But this contradicts the fact that $\{x_2, x_3\} \subseteq f(\mu )$. This final contradiction shows that the set $D = \{ \pi \in {\mathbb {N}}_0 : f(\pi ) \ne F_M(\pi )\}$ must be the empty set. Hence $f = F_M$ and we’re done.