1 Introduction
We consider a collective choice problem in which a society chooses from the set of feasible alternatives on the basis of individual preferences. The society attempts to make decisions not only by treating individuals as equally as possible, but also by treating alternatives as equally as possible. In other words, it respects equal treatment (or symmetry) criteria. The numbers of alternatives and individuals are assumed to be both fixed. The preferences of individuals are linear orders over the set of alternatives. We particularly focus on the procedures of outputting alternatives as social outcomes (i.e., social choice correspondences), not on the ones of outputting social rankings of alternatives (i.e., social preference correspondences). A social choice correspondence is a procedure that assigns a nonempty subset of the set of alternatives to every possible profile of individual preferences called a preference profile. One of the most well-known social choice correspondences is the plurality rule, in which individuals vote for their most preferred alternatives. Then, the rule chooses alternatives having the maximal votes,1
Although the analyses of social choice correspondences, including those about the plurality rule, have been extensively conducted thus far, they cannot be applied to the most essential situation in which only one alternative must be chosen since such procedures may output two or more alternatives (i.e., there is a possibility of a tie) for a preference profile. Situations requiring choosing a single alternative occur universally, and there is no doubt about the importance of dealing with such situations. To accommodate these, it is appropriate to adopt social choice functions2 which assign a single alternative to every possible preference profile. However, the serious conflict described below between two major equal treatment conditions (i.e., anonymity and neutrality) make the analysis of social choice functions difficult from the perspective3 of equal treatment criteria. In this paper, we restrict our attention to social choice functions and address the critical problem of the impossibility of achieving full equal treatment resulting from the conflict, with the aiming of achieving some equal treatment.
Anzeige
Anonymity and neutrality are the most standard equal treatment conditions. Anonymity, which is a condition for the equal treatment of individuals, requires that a social choice correspondence should be independent of individual names. On the other hand, neutrality, which is a condition for the equal treatment of alternatives, requires that it should be independent of the names of the alternatives. Most studies rely on these conditions as basic axioms for characterizations4 of various social choice correspondences, including the plurality rule.
Although anonymity and neutrality play important roles for characterization of social choice correspondences, it is well-known that they are generally incompatible5 on social choice functions. In other words, they are compatible only under a specific condition on the numbers of alternatives and individuals. Concretely, Moulin (1983) showed that a necessary and sufficient condition for the existence of a social choice function that satisfies both anonymity and neutrality is that the number of alternatives cannot be written as the sum of some divisors (other than 1) of the number of individuals. Therefore, given the impossibility result, if we attempt to pursue social choice functions from the perspective of equal treatment criteria, then we must generally give up either anonymity, neutrality, or both. In related research on these lines, Fishburn and Gehrlein (1977) and Nitzan and Paroush (1981) analyzed binary social choice functions satisfying neutrality without imposing anonymity in a binary decision problem, which is a special case of our setting. Campbell and Kelly (2013) and Jeong and Ju (2017) also treated the binary decision problem. Both studies analyzed binary social choice functions satisfying anonymity and some weakenings of neutrality. Recently, Bubboloni and Gori (2021) and Ozkes and Sanver (2021) treated the same setting as ours. Bubboloni and Gori (2021) employed two axioms: one is a weakening of anonymity and the other is a weakening of neutrality. They gave a condition for which those two axioms are compatible. Ozkes and Sanver (2021) analyzed social choice functions satisfying anonymity and a weakening of neutrality. They investigated the existence problem of social choice functions satisfying those conditions.
In this paper, we adopt the third option described above to pursue social choice functions from the perspective of equal treatment criteria. That is, we impose neither anonymity nor neutrality. Instead, we introduce a new condition called equal treatment of congruent distributions (ETCD), which is linked to some equal treatment conditions both for individuals and for alternatives, as described below.
To explain ETCD, suppose, as with the plurality rule, that individuals vote for their most preferred alternatives according to their preferences. We then focus on the associated distribution of votes under a preference profile. If two given preference profiles share the same shape of the distribution of votes except for the names of alternatives and individuals, then we say that these preference profiles have congruent distributions. ETCD requires that under two preference profiles having congruent distributions, the chosen two alternatives should share the same number of votes. As a basic property, ETCD implies nondictatorship whenever the number of individuals is three or more (Fact 1 in Sect. 3.1).
Anzeige
ETCD can be regarded as linked to some equal treatment conditions from two perspectives. The first perspective is related to the situations in which anonymity and neutrality are compatible. Under such situations, it is shown that ETCD is equivalent to anonymity and neutrality whenever the number of alternatives is two (Proposition 1 in Sect. 3.2). Furthermore, it is shown that ETCD is a conditional generalization of anonymity and neutrality whenever the number of alternatives is more than two (Proposition 2 in Sect. 3.2). The second perspective is related to the situations in which anonymity and neutrality are incompatible. Even in such situations, ETCD is available, and it is shown that it implies two equal treatment conditions: anonymity in the number of votes (ANV) and neutrality in the number of votes (NNV) (Proposition 3 in Sect. 3.2). ANV, which is weaker than anonymity, requires that the number of votes for the chosen alternatives should be independent of the names of individuals. On the other hand, NNV, which is weaker than neutrality, requires that the number of votes for the chosen alternatives should be independent of the names of alternatives. ANV and NNV can be interpreted as weak equal treatment conditions for individuals and for alternatives, respectively. These requirements are mild, but natural and intuitive. It is easily checked that ETCD implies both ANV and NNV. Thus, even in the situations such that anonymity and neutrality are incompatible, ETCD can play the role of weak equal treatment conditions both for individuals and for alternatives.
Using ETCD, we characterize a class of social choice functions called the class of tie-breaking plurality (TBP) rules, which are social choice functions derived from the plurality rule in a natural way. Specifically, a TBP rule always selects a single alternative among the alternatives having the maximal votes (i.e., it breaks a tie in some manner if there are two or more such alternatives). Formally, a TBP rule is identified with a selection of the plurality rule,6
As the main results of the paper, we give two characterizations of the class of TBP rules by ETCD and two types of positive responsiveness conditions called monotonicity and weak monotonicity. Monotonicity requires that if an alternative chosen at a given preference profile becomes most preferred whereas the relative rank of other alternatives remains the same under a new preference of an individual, then the alternative should remain chosen at the new preference profile. On the other hand, weak monotonicity7 requires that if an alternative chosen at a given preference profile becomes from second preferred to most preferred, whereas the relative rank of other alternatives remains the same under a new preference of an individual, then the alternative should remain chosen by the new preference profile. Although there are various types of definitions of monotonicity, our monotonicity conditions are mild requirements in the sense that they focus only on an improvement of the rank of an alternative to the top rank. Especially, weak monotonicity is a very weak condition. Our first result (Theorem 1 in Sect. 5) states that the class of TBP rules is characterized by ETCD and monotonicity. Our second result (Theorem 2 in Sect. 5) states that if the number of individuals is sufficiently large, then the class of TBP rules is characterized by ETCD and weak monotonicity.
Our research is significant in two ways. The first regards the proposal of a new easy-to-use condition (i.e., ETCD), which implies some natural equal treatment conditions both for individuals and for alternatives. The definition of ETCD is simple, intuitive, and easy to understand. ETCD focuses on the distribution of votes, which is one of the easiest data to handle in a preference profile. It is available without any essential restriction on the numbers of alternatives and individuals. In existing research that tried to avoid conflicts between equal treatments of individuals vs. alternatives, some weakenings of anonymity and/or neutrality were employed. Although it is usually necessary to pay attention to the possibilities of further incompatibilities between such conditions, ETCD can be used without worrying about them. Furthermore, even if a society takes a great interest in treating individuals (resp. alternatives) more equally, it is also possible to make ETCD and anonymity (resp. neutrality) compatible. The second is the characterizations of a natural class of social choice functions (i.e., TBP rules). TBP rules are also simple, intuitive, and easy to understand. Our results support TBP rules from equal treatment criteria and positive responsiveness criteria. Apart from those, it is also argued that TBP rules are supported by efficiency criteria and that they are partially supported by incentive compatibility criteria.
The rest of the paper is organized as follows: Sect. 2 gives definitions and notations and reviews the plurality rule. Section 3 describes ETCD. Section 4 defines TBP rules. Section 5 states our characterization results for TBP rules. Section 6 discusses TBP rules and states some open questions. Appendix A shows the independence of axioms. Appendices B and C are devoted to the proofs of our results.
2 Definition
Let \(N=\{1,\dots ,n\}\) be the set of individuals with \(n\ge 3\). Let X be the set of feasible alternatives with \(|X|\equiv m\ge 2\).8 Each individual \(i\in N\) has a preference \(P_i\), which is a complete, transitive, and anti-symmetric binary relation on X. Let \({\mathscr {P}}\) be the set of all preferences on X. A preference profile, or simply, a profile \(P=(P_i)_{i\in N}\) is an element of \({\mathscr {P}}^N\). A social choice correspondence F is a mapping from \({\mathscr {P}}^N\) to \(2^X\backslash {\{\emptyset \}}\). If a social choice correspondence F satisfies that for each \(P\in {\mathscr {P}}^N\), \(|F(P)|=1\) (i.e., it always selects a single alternative), we say that F is a social choice function. To distinguish functions from correspondences, we employ the lower case f as the generic notation for social choice functions. For abbreviation, we write \(f(P)=x\) instead of \(f(P)=\{ x\}\).
A well-known social choice correspondence is the plurality rule. To introduce the rule, we provide some notations. Given \(i\in N\) and \(P_i\in {\mathscr {P}}\), let \(t(P_i)\in X\) be such that for each \(x\in X\backslash \{ t(P_i)\}\), \(t(P_i)P_{i}x\) (i.e., it is the most preferred, or equivalently, top-ranked, alternative under \(P_i\)). Given \(x\in X\) and \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\), let \(N(x,P)=\{ i\in N:t(P_i)=x\}\), which is the set of individuals whose top-ranked alternatives are x under P. Then, although |N(x, P)| indicates the number of individuals whose top-ranked alternatives are x under P, it is identified with the number of votes for x under P in the situation where individuals vote for their most preferred alternatives according to their preferences. The plurality rule is then defined as follows.
The plurality rule \(F_p\) is a social choice correspondence such that for each \(P\in {\mathscr {P}}^N,\)That is, it always chooses alternatives having the maximal votes. It is known that the plurality rule satisfies many properties. The most standard ones are anonymity and neutrality.
$$\begin{aligned} F_p(P)=\{ x\in X:|N(x,P)|\ge |N(y,P)|\ \text {for all } y\in X\}. \end{aligned}$$
Anonymity: For each \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\) and each \(P'=(P'_i)_{i\in N}\in {\mathscr {P}}^N\), if there exists a bijection \(\pi :N\rightarrow N\) such that for each \(j\in N\), \(P'_{\pi (j)}=P_j\), then \(F(P)=F(P')\).
Neutrality: For each \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\) and each \(P'=(P'_i)_{i\in N}\in {\mathscr {P}}^N\), if there exists a bijection \(\sigma :X\rightarrow X\) such that for each \(j\in N\) and each \(x,y\in X\), \(xP_jy\) if and only if \(\sigma (x)P'_j\sigma (y)\), then \(\sigma (F(P))=F(P')\).
Anonymity and neutrality are equal treatment, or symmetry, conditions on individuals and alternatives, respectively. Anonymity requires that a social choice correspondence be independent on the names of individuals. Neutrality requires that it should be independent on the names of alternatives.
Furthermore, the plurality rule satisfies the following three properties:
Tops-only: For each \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\) and each \(P'=(P'_i)_{i\in N}\in {\mathscr {P}}^N\), if for all \(j\in N\), \(t(P_j)=t(P'_j)\), then \(F(P)=F(P')\).
Tops-only is a simplicity condition in which a social choice correspondence depends only on the list of top-ranked alternatives of individuals. Especially in decision making in a large society, some simplification of the rules is important for smooth execution of decision making. Note that this condition is automatically satisfied by all social choice correspondences whenever \(m=2\).
Given \(i\in N\), \(P_i\in {\mathscr {P}}\), and \(x\in X\), \({\tilde{P}}(P_i;x)\in {\mathscr {P}}\) is defined by \(t({\tilde{P}}(P_i;x))=x\) and for each \(y,z\in X\backslash \{ x\}\), \(y{\tilde{P}}(P_i;x)z\) if and only if \(yP_iz\). That is, \({\tilde{P}}(P_i;x)\) is a transformation of \(P_i\) obtained by moving x to the top rank and by preserving the relative rank of alternatives other than x. Given \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\), \(j\in N\), and \(P'_{j}\in {\mathscr {P}}\), we write a profile \((P'_{j},(P_{i})_{i\ne j})\in {\mathscr {P}}^N\) as \((P'_{j},P_{-j})\).
Monotonicity:9 For each \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\), each \(j\in N\), and each \(x\in X\), if \(x\in F(P)\), then \(x\in F({\tilde{P}}(P_j;x),P_{-j})\) and \(F({\tilde{P}}(P_j;x),P_{-j})\subseteq F(P)\).
Monotonicity is a positive responsiveness condition in which, if an alternative chosen at a given profile is moved to the top rank under a new preference of an individual, then the alternative remains chosen under the new profile, and the set of chosen alternatives does not expand.
Given \(i\in N\) and \(P_i\in {\mathscr {P}}\), let \(t_2(P_i)\in X\) be such that \(t_2(P_i)\ne t(P_i)\) and for each \(x\in X\backslash \{ t(P_i),t_2(P_i)\}\) (if such x exists), \(t_2(P_i)P_{i}x\), i.e., it is the second-ranked alternative under \(P_i\).
Weak Monotonicity:10 For each \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\), each \(j\in N\), and each \(x\in X\), if \(x\in F(P)\) and \(x=t_2(P_j)\), then \(x\in F({\tilde{P}}(P_j;x),P_{-j})\) and \(F({\tilde{P}}(P_j;x),P_{-j})\subseteq F(P)\).
That is, weak monotonicity means that, if an alternative chosen at a profile is changed from the second rank to the top rank under a new preference of an individual, then the alternative remains at the new profile chosen, and the set of chosen alternatives does not expand. It is obvious that weak monotonicity coincides with monotonicity whenever \(m=2\). On the other hand, it is implied by monotonicity whenever \(m\ge 3\).
As mentioned, we focus on social choice functions. Thus, it is useful to rewrite the definitions of the above two monotonicity conditions for social choice functions.
Monotonicity (for social choice functions): For each \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\), each \(j\in N\), and each \(x\in X\), if \(x=f(P)\), then \(x=f({\tilde{P}}(P_j;x),P_{-j})\).
Weak Monotonicity (for social choice functions): For each \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\), each \(j\in N\), and each \(x\in X\), if \(x=f(P)\) and \(x=t_2(P_j)\), then \(x=f({\tilde{P}}(P_j;x),P_{-j})\).
3 Equal treatment of congruent distributions
3.1 Definition
As mentioned in Sect. 1, social choice functions suffer from the conflict of anonymity and neutrality, meaning that we must generally give up either anonymity, neutrality, or both. In this paper, we take the third option, and so we employ neither anonymity nor neutrality. Instead, we introduce a new condition that plays the role of some equal treatment conditions both for individuals and for alternatives. We call it equal treatment of congruent distributions (ETCD).
ETCD requires that, if two given preference profiles share some kind of congruity property with respect to the associated distributions of votes, the chosen alternatives at those profiles should share the same number of votes.
For an intuitive explanation of ETCD prior to its formal definition, consider the mayoral election of a town, in which 10,000 townspeople (i.e., individuals) vote for their top-ranked candidates (i.e., alternatives) among six candidates. Then, consider the following two distributions of votes that are derived from profiles P and \(P'\), respectively:Recall that \(|N(x_k,P)|\) is identified with the number of votes for \(x_k\) under P. Then, a list \((|N(x_k,P)|)_{k=1,\dots ,6}\) forms the distribution of votes under P. Note that there is a clear similarity between P and \(P'\). That is, except for the names of alternatives and individuals, these profiles exhibit the same shape of vote distribution. Concretely, for both profiles, three alternatives have 3,333 votes, one alternative has one, and two alternatives have none. We say that two profiles exhibiting the same shape of the distribution of votes have congruent distributions.
$$\begin{aligned} \text {The distribution of votes under}\, P: {\left\{ \begin{array}{ll} |N(x_1,P)|=|N(x_2,P)|=|N(x_3,P)|=3,333, \\ |N(x_4,P)|=1,\ \text {and}\\ |N(x_5,P)|=|N(x_6,P)|=0. \end{array}\right. } \\ \text {The distribution of votes under}\, P':{\left\{ \begin{array}{ll} |N(x_1,P')|=|N(x_4,P')|=|N(x_6,P')|=3,333, \\ |N(x_2,P')|=1,\ \text {and} \\ |N(x_3,P')|=|N(x_5,P')|=0. \end{array}\right. } \end{aligned}$$
Under the incompatibility of anonymity and neutrality, if a society tries to make a decision that is based on equal treatment criteria for individuals and alternatives, what condition should be adopted for a social choice function? For example, in the above example, it seems that a social choice function choosing an alternative that has 3,333 votes for P, and choosing an alternative that has one or no vote for \(P'\) causes an apparent asymmetry. In other words, it seems that some of alternatives and/or individuals are treated quite asymmetrically. Here, to reduce the asymmetry between two profiles having congruent distributions, we adopt the condition as an equal treatment requirement that the chosen alternatives at those profiles always should share the same number of votes. This is ETCD. For the above example, if a social choice function f satisfies ETCD, then \(f(P)\in \{ x_1,x_2,x_3 \}\) if and only if \(f(P')\in \{ x_1,x_4,x_6\}\), \(f(P)=x_4\) if and only if \(f(P')=x_2\), and \(f(P)\in \{ x_5,x_6\}\) if and only if \(f(P')\in \{ x_3,x_5\}\).
ETCD requires an invariance up to choosing from among alternatives having the same number of votes for both two profiles having congruent distributions. This means that it does not require anything about which alternative should be chosen from among such alternatives for each of those profiles. Thus, even if P and \(P'\) satisfy the assumptions both of anonymity and neutrality in the above example, a further asymmetry between the result of a choice from \(\{ x_1,x_2,x_3\}\) under P and that of a choice from \(\{ x_1,x_4,x_6\}\) under \(P'\) may also occur. However, since it is generally caused by the incompatibility of anonymity and neutrality, such asymmetry is inevitable as long as we employ social choice functions.
To define ETCD formally, we define a notation. For given \(P\in {\mathscr {P}}^N\) and given \(\ell \in \{ 0,1,\dots ,n\}\), let \(X_\ell (P)=\{ x\in X:|N(x,P)|=\ell \}\). \(X_\ell (P)\) is the set of alternatives that get \(\ell \) vote(s) under P. Note that \(\bigcup _{\ell \ge 1}X_\ell (P)(=X\backslash X_0(P))\) forms the set of alternatives that are most preferred by some individuals under P (i.e., it is the set of top-ranked alternatives under P).
For given \(P\in {\mathscr {P}}^N\) and \(P'\in {\mathscr {P}}^N\), we say that P and \(P'\) have congruent distributions (CD) if for all \(\ell \in \{ 0,1,\dots ,n\}\), \(|X_\ell (P)|=|X_\ell (P')|\). That is, two profiles having CD exhibit the same shape of the distribution of votes, except for the names of alternatives and individuals. ETCD is then defined as follows.
Equal Treatment of Congruent Distributions (ETCD): For each \(P\in {\mathscr {P}}^N\) and each \(P'\in {\mathscr {P}}^N\), if P and \(P'\) have congruent distributions, then for all \(\ell \in \{ 0,1,\dots ,n\}\), \(f(P)\in X_\ell (P)\) if and only if \(f(P')\in X_\ell (P')\).
This requires that the chosen alternatives under two given profiles having CD should share the same number of votes. Note that although ETCD focuses on the distribution of votes, it is distinctly different from tops-only. In other words, under ETCD, for two profiles with the same list of top-ranked alternatives of individuals, the social choice function may assign different alternatives to each other. Thus, a social choice function that satisfies ETCD generally uses more information about a preference profile than a social choice function that satisfies tops-only. The following fact states that ETCD implies nondictatorship.
Fact 1
If a social choice function f satisfies equal treatment of congruent distributions, then it is nondictatorial in the sense that there is no dictator \(j_0\in N\) such that for all \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\), \(f(P)=t(P_{j_0})\).
Proof of Fact 1:
Suppose the contrary that f satisfies equal treatment of congruent distributions and that it is dictatorial. Let \(j_0\in N\) be a dictator. Let \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\) and \(P'=(P'_i)_{i\in N}\in {\mathscr {P}}^N\) be such that (i) \(t(P_{j_0})=x\) and for all \(j\ne j_0\), \(t(P_j)=y\) with \(y\ne x\) and (ii) \(t(P'_{j'})=y\) with \(j'\ne j_0\) and for all \(j\ne j'\), \(t(P'_j)=x\). It then holds that \(f(P)=f(P')=x\). It is obvious that P and \(P'\) have CD. However, we have \(f(P)=x\in X_{1}(P)\) and \(f(P')=x\in X_{n-1}(P')\), a contradiction to ETCD since \(n\ge 3\). \(\square \)
3.2 Relationship to other axioms
ETCD has a relationship with some equal treatment conditions. At first, under a pair of m and n such that anonymity and neutrality are compatible, ETCD is equivalent to anonymity and neutrality whenever \(m=2\). Furthermore, it is a conditional generalization of anonymity and neutrality whenever \(m\ge 3\). To see this, we first give a condition for the compatibility of anonymity and neutrality, as obtained by Moulin (1983). Let (m, n) denote a tuple of the number of alternatives and the number of individuals.
Fact 2
(Moulin (1983)) A necessary and sufficient condition on (m, n) for the existence of a social choice function that satisfies both anonymity and neutrality is that m cannot be written as the sum of some divisors (other than 1) of n.
Note that (2, n) satisfies the condition of Fact 2 if and only if n is odd. By this fact, we have the following equivalence result.
Proposition 1
Assume that \(m=2\) and n is odd. Then, a social choice function f satisfies anonymity and neutrality if and only if it satisfies equal treatment of congruent distributions.
The proof is given in Appendix B.1. Note that anonymity (resp. neutrality) itself does not imply ETCD (Example 6 (resp. 7) in Appendix A.1).
For (m, n) with \(m\ge 3\), even if it satisfies the condition of Fact 2, the similar equivalence does not hold. That is, there exists a social choice function that satisfies ETCD, but violates both anonymity and neutrality (Example 5 in Appendix A.1). Conversely, the Coombs social choice function11 due to Moulin (1983) satisfies anonymity and neutrality, but violates ETCD since the shape of the distribution of votes does not matter under the social choice function. However, under tops-only, anonymity and neutrality imply ETCD for any (m, n) such that anonymity and neutrality are compatible.
Proposition 2
Assume that (m, n) with \(m\ge 3\) is such that anonymity and neutrality are compatible. Then, if a social choice function f satisfies anonymity, neutrality, and tops-only, then it satisfies equal treatment of congruent distributions.
The proof is given in Appendix B.2. Note that the Coombs social choice function violates tops-only since non-top-ranked alternatives matter under the social choice function. Proposition 2 means that under tops-only, ETCD is a generalization of anonymity and neutrality whenever \(m\ge 3\).
Next, consider any pair (m, n) such that anonymity and neutrality may be incompatible. ETCD then implies the following two conditions that can be considered as equal treatment conditions for individuals and for alternatives: anonymity in the number of votes and neutrality in the number of votes, respectively.
Anonymity in the Number of Votes (ANV): For each \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\) and each \(P'=(P'_i)_{i\in N}\in {\mathscr {P}}^N\), if there exists a bijection \(\pi :N\rightarrow N\) such that for each \(j\in N\), \(P'_{\pi (j)}=P_j\), then for all \(\ell \in \{ 0,1,\dots ,n\}\), \(f(P)\in X_\ell (P)\) if and only if \(f(P')\in X_\ell (P')\).
Neutrality in the Number of Votes (NNV): For each \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\) and each \(P'=(P'_i)_{i\in N}\in {\mathscr {P}}^N\), if there exists a bijection \(\sigma :X\rightarrow X\) such that for each \(j\in N\) and each \(x,y\in X\), \(xP_jy\) if and only if \(\sigma (x)P'_j\sigma (y)\), then for all \(\ell \in \{ 0,1,\dots ,n\}\), \(f(P)\in X_\ell (P)\) if and only if \(f(P')\in X_\ell (P')\).
ANV requires that the number of votes for the chosen alternatives should be independent of the names of individuals. NNV requires that the number of votes for the chosen alternatives should be independent of the names of alternatives. The following proposition, which summarizes the basic logical relationships, justifies these two conditions to be equal treatment conditions.
Proposition 3
The following holds:
[1]
If a social choice function f satisfies anonymity, then it satisfies anonymity in the number of votes. Moreover, for (m, n) such that \(m=2\) and n is odd, the converse is also true.
[2]
If a social choice function f satisfies neutrality, then it satisfies neutrality in the number of votes. Moreover, for (m, n) such that \(m=2\) and n is odd, the converse is also true.
[3]
If a social choice function f satisfies equal treatment of congruent distributions, then it satisfies both anonymity in the number of votes and neutrality in the number of votes. Moreover, if \(m=2\), then the converse is also true.
The first part of every statement follows immediately from the definitions. The proof of the second part of every statement is given in Appendix B.3. For [1] and [2], except for (m, n) such that \(m=2\) and n is odd, the converse is not true. For example, \(f_{5}\) in Example 5 of Appendix A.1 satisfies ETCD, and hence by [3], does ANV and NNV, but violates anonymity and neutrality. Note that for the second part of [3], the condition on n is not necessary. Also, if \(m\ge 3\), then the converse is not true. The Coombs social choice function, which satisfies ANV and NNV, but violates ETCD, is an example.
By [1] (resp. [2]), ANV (resp. NNV) can be interpreted as an equal treatment condition for individuals (resp. for alternatives), which is weaker than anonymity (resp. neutrality). ANV and NNV are both mild requirements for equal treatment, but they are natural and intuitive. By [3], ETCD is a condition that implies ANV and NNV. This means that ETCD plays the role of weak equal treatment conditions both for individuals and for alternatives. Furthermore, it is effective even under situations where anonymity and neutrality are incompatible, that is, situations in which they cannot be relied upon.
Note that tops-only also shares the similar invariance property of ANV and NNV. That is, if, between two given profiles, the best alternatives of all individuals are identical, then the chosen alternatives share the same number of votes. Clearly, ETCD also has this property. Thus, ETCD has a weak relationship with anonymity, neutrality, and tops-only. Despite the relationship of the four conditions, they are logically independent under (m, n) such that anonymity and neutrality are incompatible. We show the independence in Appendix A.1.
4 Tie-breaking plurality rule
We introduce a class of social choice functions that satisfy ETCD: the class of tie-breaking plurality (TBP) rules. A TBP rule is a social choice function derived from the plurality rule in a natural way. That is, it always selects an alternative from the set of alternatives having the maximal votes by breaking a tie in some manner if there is more than one alternative in that set. Namely, it is a tie-breaking procedure of the plurality rule. Formally, a TBP rule is represented as a selection of the plurality rule, as defined below.
A tie-breaking plurality rule \(f_p\) is a selection of \(F_p\), i.e., for each \(P\in {\mathscr {P}}^N\),There are many ways to break a tie. The following examples12 are parts of the TBP rules.
$$\begin{aligned} f_p(P)\in F_p(P)\text {.} \end{aligned}$$
Example 1
(Pazner and Wesley 1978) Let \(X=\{ x_1,\dots ,x_m\}\). A TBP rule \(f_{1}\) is defined by for each \(P\in {\mathscr {P}}^N\),\(f_{1}\) chooses an alternative having the smallest index number among alternatives having the maximal votes. That is, the smaller the index number, the higher its priority. \(f_{1}\) satisfies anonymity and tops-only, but violates neutrality.
$$\begin{aligned} f_{1}(P)=x_{k^*},\ \text {where}\ k^*=\min _{k}\{ k:x_k\in F_p(P)\}\text {.} \end{aligned}$$
Example 2
A TBP rule \(f_{2}\) is defined by for each \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\),\(f_{2}\) chooses an alternative that is most preferred for an individual having the smallest index number among individuals whose top-ranked alternatives have maximal votes. \(f_{2}\) satisfies neutrality and tops-only, but violates anonymity.
$$\begin{aligned} f_{2}(P)=t(P_{j^*}),\ \text {where}\ j^*=\min _{j}\left\{ j:j\in \bigcup _{x\in F_p(P)}N(x,P)\right\}. \end{aligned}$$
Example 3
Let (m, n) with \(m\ge 3\) be such that every prime factor of n exceeds m.13 A TBP rule \(f_{3}\) in this example is a simple application of the elimination method of the Coombs social choice function. Given \(P\in {\mathscr {P}}^N\) and a nonempty \(Y\subseteq X\), let \(L(P,Y)\subseteq Y\) be the set of alternatives that are last-ranked over Y by the largest number of individuals under P. It is known that the assumption of (m, n) implies that \(L(P,Y)\subsetneq Y\) whenever \(|Y|\ge 2\).14 Thus, a sequence \(\{ B_t\}\) defined bysatisfies \(|B_T|=1\) for some T. Let \(f_{3}(P)=B_T\). \(f_{3}(P)\) is the result of extraction from \(F_p(P)\) by the elimination method of the Coombs social choice function.15\(f_{3}\) satisfies anonymity and neutrality, but violates tops-only.
$$\begin{aligned} B_0=F_p(P),\ B_1=B_0\backslash L(P,B_0),\ B_2=B_1\backslash L(P,B_1),\dots ,B_t=B_{t-1}\backslash L(P,B_{t-1}),\dots \end{aligned}$$
It is obvious that all TBP rules satisfy ETCD, monotonicity, and, hence, weak monotonicity. On the other hand, some TBP rules satisfy some of the three conditions (anonymity, neutrality, or tops-only), whereas others violate some of them. Generally, as shown in the following proposition, even if (m, n) satisfies the condition of Fact 2 (i.e., even if anonymity and neutrality are compatible on (m, n)), it is impossible for any TBP rule on (m, n) to satisfy all of the three conditions.
Proposition 4
Assume that (m, n) with \(m\ge 3\) is such that anonymity and neutrality are compatible. Then, there is no tie-breaking plurality rule that satisfies anonymity, neutrality, and tops-only.
The proof is in Appendix B.4. This proposition indicates that for any (m, n) such that anonymity and neutrality are compatible, even with TBP rules, it is impossible to satisfy a more demanding property than anonymity and neutrality. Not surprisingly, this impossibility is only a trivial issue under the incompatibility problem of anonymity and neutrality, and is not a critical issue for TBP rules. TBP rules have the great advantage that they can be employed in any situation of (m, n) while satisfying ETCD, which plays the role of equal treatment conditions both for individuals and for alternatives. As the main results of the paper, it is shown that the class of TBP rules is the unique class of social choice functions that satisfy ETCD and monotonicity conditions. We provide the characterizations in the next section. TBP rules are also justified from different viewpoints in Sect. 6.
5 Characterization
The class of TBP rules is characterized by ETCD and monotonicity conditions. The following result is our first characterization.
Theorem 1
A social choice function f satisfies equal treatment of congruent distributions and monotonicity if and only if it is one of the tie-breaking plurality rules.
Corollary 1
Assume that \(m=2\) and n is odd. Then, a social choice function f satisfies anonymity, neutrality, and weak monotonicity if and only if it is one of the tie-breaking plurality rules.16
The independence of axioms is given in Appendix A.2. The proof of Theorem 1 is in Appendix C.1. Corollary 1 follows from Proposition 1 and the fact that monotonicity coincides with weak monotonicity whenever \(m=2\). As another corollary, even under (m, n) such that anonymity and neutrality are compatible, it is shown that no social choice function completely inherits the properties of the plurality rule.
Corollary 2
Assume that (m, n) with \(m\ge 3\) is such that anonymity and neutrality are compatible. Then, there is no social choice function that satisfies anonymity, neutrality, tops-only, and monotonicity.
Proof of Corollary 2:
Although our characterization in Theorem 1 is valid for all \(n\ge 3\), monotonicity can be replaced with weak monotonicity in large finite societies. The following results are our second characterizations by ETCD and weak monotonicity.
Theorem 2
The following holds:
[1]
Assume that \(m\le 4\). Then, a social choice function f satisfies equal treatment of congruent distributions and weak monotonicity if and only if it is one of the tie-breaking plurality rules.
[2]
Assume that \(m\ge 5\). Then, there exists \({\bar{n}}>m\) such that if \(n\ge {\bar{n}}\), then a social choice function f satisfies equal treatment of congruent distributions and weak monotonicity if and only if it is one of the tie-breaking plurality rules.
The proof of Theorem 2 is given in Appendix C.2. The statement [1] states that if \(m\le 4\), then for all n, the class of TBP rules is characterized by ETCD and weak monotonicity. On the other hand, the statement [2] states that even if \(m\ge 5\), for all sufficiently large n, the similar characterization holds.
Remark 1
Note that the assumption of (m, n) in [1] (together with \(n\ge 3\)) is a special case of (m, n) with \(m\le n+1\). [1] indicates that for all (m, n) with \(m\le \min \{ 4,n+1\}\), the characterization by ETCD and weak monotonicity is valid. However, it remains unclear whether the class of TBP rules is characterized by ETCD and weak monotonicity for all (m, n) with \(5\le m\le n+1\). As a side note, more generally, it is shown, in Lemma 2 in Appendix C.2, that under (m, n) with \(m\le n+2\), if a social choice function satisfies ETCD and weak monotonicity, then the chosen alternative at a given profile belongs to the set of top-ranked alternatives, which is a necessary condition to be a TBP rule. It may be possible to characterize the class of TBP rules by ETCD and weak monotonicity for all (m, n) with \(m\le n+2\). We leave it as an open question. On the other hand, for some (m, n) with \(m>n+2\), there exists a social choice function that satisfies ETCD and weak monotonicity, but it is different from any TBP rule, as shown in the below example.
Example 4
Suppose either that n is odd and \(m\ge n+4\) or that n is even and \(m\ge n+3\). Let \(X=\{ x_{1},\dots ,x_{m}\}\). A social choice function \(f_{4}\) is defined by for each \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\),Note that the third case of \(f_{4}\) is possible. For example, if n is odd and equal to \(2k+1\) for some integer \(k\ge 1\), then let \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\) be such that for all \(j\in \{ 1,\dots ,k\}\), \(t(P_j)=x_1\), for all \(j\in \{ k+1,\dots ,2k\}\), \(t(P_j)=x_2\), and \(t(P_{2k+1})=x_3\). Note17 then that \(|F_p(P)|=2\) or 3 and \(|X_0(P)|=m-3>n\). The last inequality follows from the assumption of \(m\ge n+4\). Furthermore, \(|X_0(P)|>n\) implies that \(|X_0(P)\backslash \{ t_2(P_1),\dots ,t_2(P_n) \}|=|X_0(P)|-|\{ t_2(P_1),\dots ,t_2(P_n) \}|\ge |X_0(P)|-n>0\). Thus, \(X_0(P)\backslash \{ t_2(P_1),\dots ,t_2(P_n) \}\) is nonempty, and so \(f_{4}(P)\) is well-defined. By \(f_{4}(P)\notin F_p(P)\), \(f_{4}\) is different from any TBP rule. It is similar for the case that n is even and \(m\ge n+3\). Then, it is checked that \(f_{4}\) satisfies ETCD and weak monotonicity. ETCD follows from the facts that for all \(P,P'\in {\mathscr {P}}^N\) having CD, \(|F_p(P)|=1\) if and only if \(|F_p(P')|=1\), [\(|F_p(P)|\ge 2\) and \(|X_0(P)|\le n\)] if and only if [\(|F_p(P')|\ge 2\) and \(|X_0(P')|\le n\)], and [\(|F_p(P)|\ge 2\) and \(|X_0(P)|>n\)] if and only if [\(|F_p(P')|\ge 2\) and \(|X_0(P')|>n\)]. For weak monotonicity, given \(P=(P_i)_{i\in N}\in {\mathscr {P}}^N\) and \(j\in N\), let \(t_2(P_j)=f_{4}(P)\). By the definition of \(f_{4}\), we have either (i) \(|F_p(P)|=1\) or (ii) [\(|F_p(P)|\ge 2\) and \(|X_0(P)|\le n\)]. Let \(P'=({\tilde{P}}(P_j;f_{4}(P)),P_{-j})\). Both of (i) and (ii) imply that \(F_p(P')=\{ f_{4}(P)\}\), and so \(f_{4}(P')=F_p(P')=f_{4}(P)\) for both (i) and (ii).
$$\begin{aligned} f_{4}(P)= {\left\{ \begin{array}{ll} \displaystyle F_p(P), \ \ \text {if}\, |F_p(P)|=1, \\ \displaystyle x_{k^*},\ \text {where}\ k^*=\min _{k}\{ k:x_{k}\in F_p(P)\}, \ \ \text {if }\ |F_p(P)|\ge 2 \hbox { and } |X_0(P)|\le n, \text {and}\\ \displaystyle x_{k^*},\ \text {where}\ k^*=\min _{k}\{ k:x_k\in X_0(P)\backslash \{ t_2(P_1),\dots ,t_2(P_n) \}\}, \ \ \text {otherwise.} \\ \end{array}\right. } \end{aligned}$$
6 Concluding remarks
We have introduced a condition called ETCD. ETCD requires some invariance between two profiles having CD. ETCD is a conditional generalization of anonymity and neutrality on the situations in which those conditions are compatible. Furthermore, since ETCD implies ANV and NNV, which are weak equal treatment conditions for individuals and for alternatives, respectively, a social choice function satisfying ETCD treats individuals equally to some extent and alternatives equally to some extent even on the situations in which anonymity and neutrality are incompatible. Then, we provided two characterizations of the class of TBP rules by ETCD and two mild positive responsiveness conditions. These results indicate that TBP rules are supported from two viewpoints of equal treatment and positive responsiveness criteria. Furthermore, it is obvious that any TBP rule satisfies efficiency. That is, the chosen alternative at a given profile is not Pareto-dominated. Thus, TBP rules are also supported from the viewpoint of efficiency criteria.
Furthermore, TBP rules are partially supported from the viewpoint of incentive compatibility criteria by the following two aspects: First, by the result of Pazner and Wesley (1978), TBP rules18 are approximately strategy-proof19 in situations where the number of individuals is sufficiently large. Second, Campbell and Kelly (2016) characterized the (single-valued) plurality rule by strategy-proofness, nondictatorship, and citizen sovereignty20 on the resolute domain on which the set of alternatives with the maximal votes is always a singleton. That is, the plurality rule is necessarily single-valued on the resolute domain. Our domain includes the resolute domain, and TBP rules coincide with the plurality rule on the resolute domain. Thus, TBP rules are immune to strategic behavior on the resolute domain. These two arguments partially support TBP rules from the viewpoint of incentive compatibility criteria.
We leave some open questions for future research. First, as mentioned in the previous section, it remains unsolved whether the class of TBP rules is characterized by ETCD and weak monotonicity for all (m, n) with \(m\le n+2\). Second, in our setting, the numbers of alternatives and individuals are fixed. On the other hand, some studies21 employ the settings in which the numbers of alternatives and/or individuals vary. ETCD can be redefined in such settings in a suitable way. It may be possible to characterize TBP rules by ETCD and some consistency axioms in those settings. Third, our results are characterizations of the class of TBP rules, not a characterization of a specific TBP rule. Thus, our research is a starting point of analyzing specific tie-breaking rules in the class of TBP rules. It is future research to characterize some reasonable TBP rules as a further step. Finally, although ETCD was defined as a condition on social choice functions, it can be easily extended to social choice correspondences, as follows:
ETCD (for social choice correspondences): For each \(P\in {\mathscr {P}}^N\) and each \(P'\in {\mathscr {P}}^N\), if P and \(P'\) have congruent distributions, then for all \(\ell \in \{ 0,1,\dots ,n\}\), \(|F(P)\cap X_\ell (P)|=|F(P')\cap X_\ell (P')|\).
Note that it coincides with ETCD used in the previous sections whenever F is always single-valued. Clearly, the plurality rule satisfies this condition. A characterization of the plurality rule by this condition is also an open question.
Acknowledgements
The author is grateful to the anonymous reviewers for helpful comments and suggestions on an earlier version of the paper.
Declarations
Conflict of interest
The author has no conflicts of interest to declare that are relevant to the content of this article.
Code availability
Not applicable.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.