Abstract
We consider a collective choice problem in which the number of alternatives and the number of voters vary. Two fundamental axioms of consistency in such a setting, reinforcement and composition-consistency, are incompatible. We first observe that the latter implies four conditions each of which can be formulated as a consistency axiom on its own right. We find that two of these conditions are compatible with reinforcement. In fact, one of these, called composition-consistency with respect to non-clone winners, turns out to characterize a class of scoring rules which contains the Plurality rule. When combined with a requirement of monotonicity, composition-consistency with respect to non-clone winners uniquely characterizes the Plurality rule. A second implication of composition-consistency leads to a class of scoring rules that always select a Plurality winner when combined with monotonicity.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The outcome of an election can be manipulated by an interested party to achieve strategic results. This paper studies two consistency conditions that rule out manipulations via partitioning the electorate into sub-electorates and manipulations via altering the set of alternatives running in the election.
The framework includes a potential set of electorates and a potential set of alternatives. Each individual has preferences over the set of all possible alternatives. A social choice rule specifies the winning alternative(s) as a function of the set of entering alternatives (called agendas) and voters’ preferences over the entering alternatives. We focus only on social choice rules that are neutral and anonymous. Additionally, we often insist that the social choice rule satisfy faithfulness. The condition states that if there is only one voter, the most preferred alternative of the single voter should be uniquely chosen. Our first consistency condition, reinforcement due to Young (1974), says that if two disjoint electorates have some alternative in common in their choice set, then the choice set of their union should consist of the common choices of the separate groups.Footnote 1 The second consistency axiom, composition-consistency due to Laffond et al. (1996), uses the notion of a set of clones. We say that a set of alternatives A is a set of clones at a preference profile if the alternatives in A perform identically in pairwise comparisons with alternatives outside the set A. In other words, the alternatives in A are adjacent in all voters’ preference relations. Composition-consistency states that (i) cloning of an alternative should not change the winning status of another alternative, and (ii) a cloned alternative should win after cloning if and only if it is the best alternative among its clones (i.e., if it is chosen when the social choice rule is applied to the set of clones only) and it wins when all of its clones are removed from the agenda. In other words, part (ii) of the condition says that the best clones of the best alternatives should win after cloning.
Brandl et al. (2016) showed that population-consistency—a condition implied by reinforcement—and composition-consistency are incompatible if one insists on faithfulness applied only to the case of two alternatives.Footnote 2 They proceed to show that this impossibility disappears if we change the context from non-probabilistic social choice to probabilistic social choice. Probabilistic social choice has its merits and areas of applications. However, not all voting situations where a group of individuals must make a choice involves lotteries over alternatives. Our main goal in this paper is to investigate the incompatibility of reinforcement and composition-consistency more closely in a non-probabilistic social choice setting. Since reinforcement is a defining feature of scoring rules, our study is mainly about the composition-consistency properties of scoring rules. We first show that the only scoring rule that satisfies composition-consistency is the trivial rule which always selects all members of a given agenda regardless of the configuration of voters’ preferences (Proposition 1). It immediately follows that no scoring rule satisfies composition-consistency and faithfulness.
We insist on faithfulness and move on to investigate the requirements of composition-consistency more closely. First, we observe that composition-consistency implies four conditions each of which is a reasonable consistency condition on its own right (Sect. 4). Broadly put, the first condition says that a loser of an election should continue to lose if clones of another alternative are added to the agenda. The second condition, called composition-consistency with respect to non-clone winners, says that a winner of an election should continue to win if clones of another alternative are added to the agenda. The third condition, called composition-consistency with respect to clone losers, says that a loser of an election should continue to lose after it is cloned. The fourth condition, called composition-consistency with respect to clone winners, says that a winner of an election should continue to win after it is cloned if it is the best alternative among its clones.
We find that, individually, the first three of these conditions are satisfied by scoring rules other than the trivial rule. However, composition-consistency with respect to non-clone losers clashes with faithfulness and composition-consistency with respect to clone winners is only satisfied by the trivial rule. Furthermore, combinations of the four conditions with each other also lead us to the trivial rule (Proposition 2). It follows immediately that combinations of the conditions of composition-consistency still clash with faithfulness and reinforcement. Fortunately, we are able to find scoring rules that satisfy faithfulness and composition-consistency with respect to non-clone winners or composition-consistency with respect to clone losers. The class of faithful scoring rules that satisfy composition-consistency with respect to non-clone winners consists of scoring rules with non-monotonic score vectors, with the Plurality rule being the only exception. The class of faithful scoring rules that satisfy composition-consistency with respect to clone losers, on the other hand, also consists of scoring rules with non-monotonic score vectors, with scoring rules that always choose a Plurality winner being the only exception (Lemma 1 and Theorem 1).
As noted before, conditions two and four clash with faithfulness. The definition of the best clone alternative by composition-consistency with respect to clone winners is open to interpretation. Indeed, the condition defines the best clone as the clone alternative that is chosen when the social choice rule is applied to the set of clones. We propose to define the best clone alternative as the one that Pareto dominates all of its clones. We call this new condition composition-consistency with respect to dominant clone winners.Footnote 3 We show that the Plurality rule is the unique scoring rule that satisfies composition-consistency with respect to dominant clone winners and composition-consistency with respect to non-clone winners (Theorem 2).
Our contribution is twofold. First, we identify the driving forces behind the tension between consistency with respect to varying electorates (captured by reinforcement) and consistency with respect to varying agendas (captured by composition-consistency). Second, we contribute to a line of research on the axiomatization of scoring rules, particularly the Plurality rule. Indeed, Theorems 1 and 2 present new characterizations of the Plurality rule.
1.1 Related literature
A first hint at the failure of scoring rules to satisfy composition-consistency can be found in the contribution of Laslier (1996). The author showed that no efficient rank based social choice rule—a class of social choice rules which include scoring rules—satisfies composition-consistency in a setting with a fixed set of voters. Faithfulness is a weaker condition than efficiency. Thus, our results show that the impossibility prevails if efficiency is replaced with the weaker condition of faithfulness in a setting with a variable set of voters. As mentioned before, Brandl et al. (2016) then provided a first complete proof of the clash of composition-consistency with unanimity (a condition weaker than faithfulness) and population-consistency (a condition weaker than reinforcement). The current study thus adds to this strand of the literature by providing a more in-depth investigation of the tension.
A number of publications studied cloning or composition consistency properties of social choice rules rather than focusing on the relationship between these consistency properties and reinforcement. Tideman (1987) considered a consistency axiom, called independence of clones, where part (ii) of composition-consistency is replaced by the following condition: an alternative that is a member of a set of clones should win if and only if some member of that set of clones wins after a member of the set is removed from the agenda. He proposed a new voting rule called ranked-pairs rule which he showed to be independent of clones in all but a small fraction of preference profiles. Zavist and Tideman (1989) later proposed a modification of the ranked-pairs rule that is independent of clones on the whole domain. Laslier (2000) used a weaker independence of clones criterion in the characterization of a social choice rule known as the essential set. Schulze (2011) showed that the single valued social choice rule called the Schulze method satisfies a clone independence property similar to the condition of Tideman (1987). Freeman et al. (2014) characterized the runoff voting rule called single transferable vote using a clone independence criterion defined for single valued social choice rules.
Taking a different approach, Elkind et al. (2011) call a cloning manipulation by a campaign manager successful if it leads to the highest ranked alternative of the campaign manager to win. Instead of investigating composition-consistency properties of social choice rules, for a number of well-known rules, the authors characterized the preference profiles for which a successful cloning manipulation exists. In a similar vein, Elkind et al. (2012) analyzed the structure of clone sets from a computational social choice perspective.
Another closely related literature is the literature on control by adding alternatives studied by Dutta et al. (2001). The authors also considered the possibility of manipulation by altering the set of alternatives. Unlike ours, in their case, a new alternative added to the agenda does not have to be a clone of an existing alternative. Cloning as a manipulation strategy has certain advantages over introducing an entirely new alternative. The latter is more likely to be risky as the manipulator is more likely to end up with rankings different than his initial expectations. In comparison, the outcome of cloning is likely to be more predictable, and therefore manipulation by cloning may be easier to implement. It is therefore natural to study such a specific type of manipulation strategy.
Finally, this paper adds to the literature that provide axiomatic characterizations of scoring rules. The first axiomatic characterization of the Plurality rule was by Richelson (1978) who showed that the Plurality rule is the unique social choice rule that satisfies neutrality, anonymity, reinforcement, continuity and independence of dominated alternatives.Footnote 4 Ching (1996) showed that continuity is redundant in the characterization of Richelson (1978). Independence of dominated alternatives implies composition-consistency with respect to dominant clone winners. However, the converse does not hold.Footnote 5 Besides, composition-consistency with respect to non-clone winners and independence of dominated candidates are independent. Thus, Theorems 1 and 2 are new characterizations of the Plurality rule. However, the similarity between independence of dominated alternatives and composition-consistency with respect to dominant clone winners confirms that the Plurality rule does significantly better than other scoring rules in the sense that it is not affected when some inessential alternatives (defined in this case as dominated alternatives) are withdrawn from or added to the agenda. Other characterizations of the Plurality rule were provided by Yeh (2008), Sekiguchi (2012), and Kelly and Qi (2016). Yeh (2008) replaced independence of dominated alternatives with efficiency and tops-only.Footnote 6 Sekiguchi (2012) strengthened Yeh (2008)’s result by replacing efficiency with the weaker condition of faithfulness. Kelly and Qi (2016) characterized the rule by neutrality, anonymity, tops-only and a monotonicity property on a domain with a fixed number of voters. The monotonicity axiom of Kelly and Qi (2016) states that, if an alternative is chosen at a preference profile, and if this alternative is moved from second place to the first place in one voter’s ordering, than this alternative should be uniquely chosen in the new preference profile. Our monotonicity axiom is independent from that of Kelly and Qi (2016).Footnote 7 Tops-only is clearly independent of the composition-consistency requirements defined here. Thus, the characterizations given here are independent of the characterizations of Yeh (2008), Sekiguchi (2012) and Kelly and Qi (2016).
2 Basic notation and definitions
Let \({\mathcal {A}}\) be the universal set of alternatives and \(\mathtt {A}\) the set of all finite non-empty subsets of \({\mathcal {A}}\). We refer to each member of \(\mathtt {A}\) as an agenda. Let \({\mathcal {N}}\) be the set of all non-negative integers, and \(\mathtt {N}\) be the set of all finite non-empty subsets of \({\mathcal {N}}\). The elements of \(\mathtt {N}\) will be called electorates. Individuals have strict preferences over the set of alternatives represented by a complete, transitive and anti-symmetric binary relation. The preference relation of voter i over an agenda A is denoted by \(R_{i}(A)\). Given an agenda A in \(\mathtt {A}\) and an electorate N in \(\mathtt {N}\), a preference profile is denoted by \(R_{N}(A)\). The restriction of \(R_{N}(A)\) to a subset \(A'\) of A is denoted by \(R_{N}(A)\vert _{A'}\). The set \({\mathcal {R}}\) collects all possible preference profiles. That is, \({\mathcal {R}}=\cup _{N \in {\mathbb {N}}} \cup _{A \in {\mathbb {A}}} R_{N}(A)\). A social choice rule F is a correspondence that assigns to each preference profile \(R_{N}(A)\) in \({\mathcal {R}}\) a non-empty subset \(F(R_{N}(A))\) of A.
We define three basic axioms.
Let A be an agenda in \(\mathtt {A}\) and \(\pi \) be a permutation on A. Let \(\pi (R_{i}(A))\) be such that for all a, b in A, \(\pi (a) \pi (R_{i}(A))\pi (b)\) if \(a R_{i}(A) b\). Set \(\pi (R_{N}(A))=(\pi (R_{i}(A))_{i \in N})\).
Neutrality. For each preference profile \(R_{N}(A)\) in \({\mathcal {R}}\) and each permutation \(\pi \) on A, \(F(\pi (R_{N}(A)))=\pi (F(R_{N}(A)))\).
Anonymity. For each preference profile \(R_{N}(A)\) in \({\mathcal {R}}\) and each permutation \(\eta \) on N, \(F(R_{N}(A)) = F(R_{\eta (N)}(A))\).
To define the next axiom, let \(\tau (R_{i}(A))\) be voter i’s most preferred alternative at \(R_{i}(A)\).
Faithfulness. For each i in \({\mathcal {N}}\), each A in \({\mathcal {A}}\), \(F(R_{i}(A))=\{\tau (R_{i}(A))\}\).
Next, we define a special class of social choice rules called scoring rules.
2.1 Scoring rules
Let \((s_{m; m},s_{m-1;m}, \ldots , s_{1;m})\) be an m-dimensional vector of real numbers. A simple scoring rule with the associated score vector \((s_{m; m},s_{m-1;m}, \ldots , s_{1;m})\) for m alternatives is a social choice rule such that for each A of cardinality m and each preference profile \(R_{N}(A)\),
where \(r(a,R_{i}(A))\) is one plus the number of alternatives that are ranked lower than a at \(R_{i}(A)\). That is, \(r(a,R_{i}(A))= 1 + \vert \{b \in A: a R_{i} b\}\vert \). Two key features of the definition of a simple scoring rule are as follows. First, we do not assume that the score assigned to an alternative decreases as the rank of the alternative decreases, i.e., it is not assumed that \(s_{m; m} \ge s_{m-1;m} \ge \cdots \ge s_{1;m}\). We only assume that the score vector is a real valued vector. Second, two scoring rules are equivalent if the score vector of one is obtained from the score vector of the other by a positive affine transformation.
The Plurality rule is the simple scoring rule P with the associated score vector \((1,0,0,\ldots ,0)\) for any number of alternatives. Next, let \(F^{s}\) and \(F^{t}\) be simple scoring rules with associated score vectors s and t for m alternatives. The composition of \(F^{s}\) and \(F^{t}\), denoted by \(F^{s} \circ F^{t}\), is a social choice rule such that, for each A of cardinality m, for each profile \(R_{N}(A)\) in \({\mathcal {R}}\) and for each \(a \in A\), \(a \in (F^{s} \circ F^{t})(R_{N}(A))\) if and only if
A scoring rule is a social choice rule that is the composition of a finite number of simple scoring rules, i.e., there exist simple scoring rules \(F^{\alpha }, F^{\alpha -1},\ldots , F^{1}\) such that \(F=F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{1}\).
3 Reinforcement and composition-consistency
We consider two consistency axioms that are very natural for a social choice rule that operates with variable electorates and variable agendas. The first, reinforcement, links the choice of two electorates to the choice of their union. The condition says that if two disjoint electorates have some alternative in common in their choice set, then the choice set of their union should consist of the common choices of the separate groups. Reinforcement rules out the possibility of strategic manipulation by partitioning an electorate into sub-electorates that overlap and it is intuitively appealing.
Reinforcement. For all sets of voters N and M in \(\mathtt {N}\) with \(N \cap M=\emptyset \) and for each agenda A in \(\mathtt {A}\) such that \(F( R_{N}(A)) \cap F(R_{M}(A)) \ne \emptyset \),
Young (1975) showed that a social choice rule satisfies anonymity, neutrality and reinforcement if and only if it is a scoring rule (simple or composite).
Young (1975, Theorem 1): A social choice rule F satisfies neutrality, anonymity and reinforcement if and only if there exists simple scoring rules \(F^{\alpha }, F^{\alpha -1},\ldots , F^{1}\) such that \(F=F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{1}\).
The second consistency condition, composition-consistency, concerns varying agendas. Let \(R_{N}(A)\) in \({\mathcal {R}}\) be a preference profile such that \(A = A' \cup B\) and \(A' \cap B = \{b\}\). We say that B is a set of clones at \(R_{N}(A)\) if the alternatives in B perform identically in pairwise comparisons with alternatives outside the set. That is, if for each a in \(A \setminus B\), for all \(b', b''\) in B and for each i in N, we have
In this case, we say that \(R_{N}(A)\) is obtained from \(R_{N}(A')\) by cloning b.
Example 1
Consider the two preference profiles below. The set \(\{a, {\hat{a}}\}\) constitutes a set of clones at R. In other words, the preference profile R is obtained from \(R'\) by cloning a.
A well-known consistency condition with respect to varying agendas is composition-consistency due to Laffond et al. (1996). The condition states that (i) cloning of an alternative should not affect the winning status of another alternative and (ii) an alternative that is a member of a set of clones wins if and only if it wins after its clones are removed from the agenda and if it is the best alternative among its clones (i.e., if it wins when F is applied to the set of clones).
Composition-consistency. For each preference profile \(R_{N}(A)\) in \({\mathcal {R}}\) at which B is a set of clones with \(A = A' \cup B\) and \(A' \cap B=\{b\}\),
A first observation is that the trivial rule—the rule that selects A at each \(R_{N}(A)\) in \({\mathcal {R}}\)—is the only scoring rule to satisfy composition-consistency.
Proposition 1
The trivial rule is the unique scoring rule that satisfies composition-consistency.
The trivial rule does not satisfy faithfulness. Hence, it immediately follows from Proposition 1 that there exists no scoring rule that satisfies faithfulness and composition-consistency. Dropping faithfulness leads us to the trivial rule as shown in Proposition 1, but this could hardly be called good news. Indeed, the trivial rule does not actually make a selection at a preference profile, it is not decisive. As such, it is not of much interest for social choice theory. We therefore insist on the requirement of faithfulness. The following example helps us see the clash between faithfulness and composition-consistency, and helps us motivate the approach laid out in the next section.
Example 2
Let F be a simple scoring rule that satisfies faithfulness and composition-consistency. Consider the following profiles.
Let \((s_{3;3}, s_{2;3},s_{1;3})\) be the score vector F uses for 3 alternatives. By neutrality and anonymity, \(F(R_{1}, R_{2})=\{a,b\}\). By faithfulness, \(F(R_{3})=\{b\}\). By reinforcement, then, we must have \(F(R)=\{b\}\). Note that \(R'\) is obtained from \((R_{1},R_{2})\) by cloning a. Since \(b \in F(R_{1},R_{2})\), by part (i) of composition-consistency, it must be that \(b \in F(R')\). The total score of b at \(R'\) is \(s_{3;3}+s_{1;3}\), while the total score of a at \(R'\) is \(s_{3;3}+s_{2;3}\). Since \(b \in F(R')\), the total score of b cannot be less than the total score of a. That is, \(s_{3;3}+s_{1;3} \ge s_{3;3}+s_{2;3}\), i.e., \(s_{1;3} \ge s_{2;3}\). Also note that \(R''\) is obtained from R by cloning b. Since \(F(R)=\{b\}\), by part (i) of composition-consistency, \(a \not \in F(R'')\). However, the total score of a at \(R''\) cannot be less than the total scores of b and \(b'\) at \(R''\) since \(s_{1;3} \ge s_{2;3}\). That is, it must be that \(a \in F(R'')\), which leads to a contradiction. Thus, a social choice rule cannot simultaneously satisfy neutrality, anonymity, faithfulness, reinforcement and part (i) of composition-consistency.
A key observation embedded in Example 2 is that part (i) of composition-consistency clashes with faithfulness. A natural question is then whether part (ii) of composition-consistency also leads to such a clash. In the sequel, we investigate the requirements of composition-consistency more closely.
4 The four implications of composition-consistency
A close inspection of composition-consistency reveals that the axiom actually comprises four requirements. In this section, we formulate each implication of composition-consistency as an axiom on its own right.Footnote 8
The first two axioms are implications of part (i) of composition-consistency.
The first, composition-consistency with respect to non-clone losers, states that an alternative a that is not chosen at a preference profile R should not be chosen at any profile \(R'\) that is obtained from R by cloning another alternative b. The anti-plurality rule with the associated score vector \((1,1,1\ldots ,1,0)\) for any finite number of alternatives satisfies composition-consistency with respect to non-clone losers.
Composition-consistency with respect to non-clone losers. For each preference profile \(R_{N}(A)\) in \({\mathcal {R}}\) at which B is a set of clones with \(A = A' \cup B\) and \(A' \cap B=\{b\}\), for each a in \(A\setminus B\),
The second, composition-consistency with respect to non-clone winners, states that an alternative a that is chosen at a preference profile R should still be chosen at any profile \(R'\) that is obtained from R by cloning another alternative b.
Composition-consistency with respect to non-clone winners. For each preference profile \(R_{N}(A)\) in \({\mathcal {R}}\) at which B is a set of clones with \(A = A' \cup B\) with \(A' \cap B=\{b\}\), for each a in \(A\setminus B\),
The next two axioms are implications of part (ii) of composition-consistency.
Composition-consistency with respect to clone losers states that an alternative that is not chosen at a preference profile cannot be chosen after it is cloned. Plurality rule satisfies composition-consistency with respect to non-clone winners and composition-consistency with respect to clone losers.
Composition-consistency with respect to clone losers. For each preference profile \(R_{N}(A)\) in \({\mathcal {R}}\) at which B is a set of clones with \(A = A' \cup B\) with \(A' \cap B=\{b\}\), for each \(b'\) in B,
Composition-consistency with respect to clone winners states that a cloned alternative wins after cloning only if it wins before its clones are added to the agenda and if it wins when F is applied to the set of clones.
Composition-consistency with respect to clone winners. For each preference profile \(R_{N}(A)\) in \({\mathcal {R}}\) at which B is a set of clones with \(A = A' \cup B\) with \(A' \cap B=\{b\}\), for each \(b'\) in B,
It turns out that weakening composition-consistency does not lead to meaningful scoring rules. In fact, as reported in the next proposition, the trivial rule is still the only scoring rule that satisfies combinations of the four conditions.
Proposition 2
The trivial rule is the unique scoring rule that satisfies
-
(a)
composition-consistency with respect to non-clone losers and composition-consistency with respect to non-clone winners.
-
(b)
composition-consistency with respect to non-clone losers and composition-consistency with respect to clone losers.
-
(c)
composition-consistency with respect to clone winners.
An immediate implication of Proposition 2 is that no faithful scoring rule satisfies composition-consistency with respect to clone winners, and the combination of composition-consistency with respect to non-clone losers with composition-consistency with respect to non-clone winners and composition-consistency with respect to clone losers. In fact, as the next proposition shows, there exists no scoring rule which satisfies faithfulness and composition-consistency with respect to non-clone losers by itself.Footnote 9
Proposition 3
There exists no scoring rule that satisfies faithfulness and composition-consistency with respect to non-clone losers.
The results so far show that composition-consistency with respect to non-clone losers and composition-consistency with respect to clone winners are the culprits behind the failure of faithful scoring rules to satisfy composition-consistency. In the next section, we show that the remaining two conditions—composition-consistency with respect to non-clone winners and composition consistency with respect to clone losers—provide strong positive results. Furthermore, we define a weaker version of composition-consistency with respect to clone winners which leads to positive results.
5 Characterizations using the sub-requirements of composition-consistency
In this section, we focus on the last three sub-conditions of composition-consistency individually. First, we show that if a faithful scoring rule satisfies composition-consistency with respect to non-clone winners or composition-consistency with respect to clone losers, then the score vector(s) the rule uses take very specific forms.
Lemma 1
Let F be a scoring rule with \(F=F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{1}\). For each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), each m in \({\mathbb {N}}\), let \(s^{\beta }_{m}=(s^{\beta }_{m;m}, s^{\beta }_{m-1;m},\ldots ,s^{\beta }_{1;m})\) be the score vector associated with the simple scoring rule \(F^{\beta }\).
-
(a)
F satisfies faithfulness and composition-consistency with respect to non-clone winners if and only for each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), each m in \({\mathbb {N}}\), we have \(s^{\beta }_{m}=(x^{\beta }_{m},y^{\beta }_{m}, y^{\beta }_{m},\ldots ,y^{\beta }_{m},z^{\beta }_{m})\) with \(x^{\beta }_{m} \ge y^{\beta }_{m}\) and \(z^{\beta }_{m} \ge y^{\beta }_{m}\).
-
(b)
If F satisfies faithfulness and composition-consistency with respect to clone losers, then, for each \(m \ge 3\), we have \(s^{1}_{1;m} \ge s^{1}_{m-1;m}\).
The class of social choice rules reported in part (a) of Lemma 1 contains scoring rules for which the associated score vector of each \(F^{\beta }\) has the property that \(z^{\beta }_{m} > y^{\beta }_{m}\). Similarly, the class of social choice rules reported in part (b) of the lemma contains scoring rules for which \(s^{1}_{1;m} > s^{1}_{m-1;m}\). A scoring rule for which \(z^{\beta }_{m} > y^{\beta }_{m}\) for each \(\beta \) in \(\{1,2,\ldots ,\alpha \}\) seems odd since an alternative that is bottom ranked by all individuals, for instance, would receive a higher total score than an alternative that is ranked above it by all individuals. Similarly, it is odd to have \(s^{1}_{1;m} > s^{1}_{m-1;m}\) since a bottom ranked alternative would receive a higher total score than an alternative ranked second by all individuals. In other words, such scoring rules fail to meet a very basic requirement of social choice: if an alternative a is chosen at some preference profile, and the preference profile changes by moving a up in one voter’s ranking, then a should continue to be chosen at the new preference profile. We call this consistency requirement monotonicity. To define this consistency requirement formally, let us formalize what it means for an alternative to move up in a voter’s ranking. We say that a preference profile \(R'\) in \({\mathcal {R}}\) is obtained from another preference profile R in \({\mathcal {R}}\) by an improvement of a if and only if there exists i in N and b in A such that \(b \, R_{i}(A) \, a\) and \(a \, R'_{i}(A) \, b\); for all \(c,d \in A \setminus \{a,b\}\), \(c \, R_{i}(A) \, d\) if and only if \(c \, R'_{i}(A) \, d\) and for each j in \(N{\setminus } \{i\}\), all \(c,d \in A\), \(c \, R_{j}(A) \, d\) if and only if \(c \, R'_{j}(A) \, d\).
Monotonicity. For each preference profile \(R_{N}(A)\) in \({\mathcal {R}}\), each a in \(F(R_{N}(A))\), if \(R'_{N}(A)\) in \({\mathcal {R}}\) is obtained from \(R_{N}(A)\) by an improvement of a, then \(a \in F(R'_{N}(A))\).
Monotonicity is a very weak, yet appealing requirement. It ensures that the social choice rule is positively responsive to voters’ preferences. In fact, a scoring rule \(F=F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{1}\) satisfies monotonicity only if the score vector of \(F^{1}\) is strictly monotonically decreasing or if the score vector of every one of \(F^{\alpha }, F^{\alpha -1}, \ldots , F^{1}\) is weakly monotonically decreasing as reported in the next lemma.
Lemma 2
If a scoring rule \(F=F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{1}\) satisfies monotonicity, then at least one of the following holds.
-
(i)
For each m in \({\mathbb {N}}\), each \(k, \ell \le m\) with \(k > \ell \), we have \(s^{1}_{k;m} > s^{1}_{\ell ;m}\).
-
(ii)
For each m in \({\mathbb {N}}\), each \(k, \ell \le m\) with \(k > \ell \), each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), we have \(s^{\beta }_{k;m} \ge s^{\beta }_{\ell ;m}\).
Combined with Lemma 1, Lemma 2 implies that when combined with faithfulness and composition-consistency with respect to non-clone winners, monotonicity singles out the Plurality rule. When combined with faithfulness and composition-consistency with respect to clone losers, on the other hand, monotonicity implies that \(F^{1}\) is the Plurality rule, and hence it leads us to a class of social choice rules that always select a Plurality winner.
Theorem 1
Let F be a scoring rule.
-
(a)
F satisfies faithfulness, composition-consistency with respect to non-clone winners and monotonicity if and only if it is the Plurality rule.
-
(b)
F satisfies faithfulness, composition-consistency with respect to clone losers and monotonicity if and only if for each preference profile \(R_{N}(A) \in {\mathcal {R}}\), we have \(F(R) \subseteq P(R)\), where P is the Plurality rule.
Monotonicity is a weaker condition than positive responsiveness, used frequently in the literature on voting rules, which states that if an alternative is chosen at a preference profile R and another profile \(R'\) is obtained from R by moving a up in one voter’s ordering, than a should be uniquely chosen at the new preference profile. The axiom was used by May (1952) in his characterization of the majority rule. He showed that if the set of alternatives contains two members, an anonymous and neutral social choice rule is positively responsive if and only if it is majority rule.
The Plurality rule satisfies composition-consistency with respect to clone losers. In light of Theorem 1, this implies that a scoring rule that satisfies faithfulness, composition-consistency with respect to non-clone winners and monotonicity also satisfies composition-consistency with respect to clone losers. However, the converse does not hold. To see that, let \(F=B \circ P\), where P is the Plurality rule and B is Borda’s rule, i.e., B is a simple scoring rule with the associated score vector \((m,m-1,\ldots ,2,1)\) for each \(m \in {\mathcal {N}}\). By Theorem 1, we know that this rule satisfies composition-consistency with respect to clone losers. Consider the following profiles.
By neutrality and anonymity, we have \(F(R)=\{a, b\}\). We have \(P(R')=\{a,b\}\), but the Borda scores of a and b at \(R'\) are 5 and 4, respectively. So, \((B \circ P)(R')=\{a\}\). That is, \(F=B \circ P\) does not satisfy composition-consistency with respect to non-clone winners.
As noted before, an immediate implication of Proposition 2 is that composition-consistency with respect to clone winners clashes with faithfulness by itself. A standard approach social choice theory adopts to deal with such impossibilities is to use a weaker version of one of the axioms that clash with each other. An axiom can be weakened by restricting the number of situations in which it applies. This is the approach we follow with regards to composition-consistency with respect to clone winners.Footnote 10
When a winning alternative is cloned, we cannot simply say that it should continue to win regardless of the relationship between the clones. Composition-consistency with respect to clone winners states that when a winning alternative is cloned, the best clone of the alternative should be chosen, where the best clone alternative is defined as the one that is chosen by F when the rule is applied to the set of clones. Such a definition of the best clone is reasonable, but it is not the only way one can reasonably define a consistency axiom with respect to clone winners. We propose to weaken the axiom by defining the best clone alternative as the member of a set of clones that Pareto dominates all of its clones.
Composition-consistency with respect to dominant clone winners. For each preference profile \(R_{N}(A)\) in \({\mathcal {R}}\) at which B is a set of clones with \(A = A' \cup B\) and \(A' \cap B=\{b\}\) and with \(\tau (R_{i}(A)\vert _{B})=\{b\}\) for each \(i \in N\),
The next theorem shows that such a weakening of composition-consistency with respect to clone winners helps us avoid the impossibility of a faithful scoring rule that satisfies composition-consistency with respect to clone winners. In fact, Plurality rule is uniquely characterized if we add composition-consistency with respect to dominant clone winners to the list of axioms in part (a) of Lemma 1.Footnote 11
Theorem 2
A scoring rule satisfies faithfulness, composition-consistency with respect to non-clone winners and composition-consistency with respect to dominant clone winners if and only if it is the Plurality rule.
We have noted before that the Plurality rule satisfies composition-consistency with respect to clone losers. Thus, in light of Theorem 2, we can conclude that if a scoring rule satisfies composition-consistency with respect to non-clone winners and composition-consistency with respect to dominant clone winners, then it also satisfies composition-consistency with respect to clone losers.
6 Concluding remarks
This paper presents a first attempt at dealing with the incompatibility between faithfulness, reinforcement and composition-consistency in a deterministic social choice setting. As reinforcement is a defining feature of scoring rules, the incompatibility in fact tells us that no scoring rule satisfies faithfulness and composition-consistency.
The novelty and main contribution of our study lies in the fact that we weaken composition-consistency into four axioms of consistency. We believe that each of these four axioms is a reasonable axiom of social choice.
We end this section with three additional directions for an extension of the current study. First, in a setting with a fixed number of voters, reinforcement is not a necessary axiom. In such a setting, a characterization of social choice rules that satisfy neutrality, anonymity, composition-consistency and monotonicity is an open question, worth pursuing as all these conditions are appealing requirements of social choice.
Second, composition-consistency with respect to dominant clone winners is not the only weakening of composition consistency with respect to clone winners. One might, for instance, define the best clone alternative as the one that is Condorcet dominant in the set of its clones (i.e., it is preferred by a majority of voters to any of its clones) instead of requiring Pareto dominance. The investigation of the relationship between such an axiom and reinforcement is left for future research.
Third, population-consistency, which is weaker than reinforcement, is compatible with composition-consistency in our setting. Indeed, the Pareto rule satisfies neutrality, anonymity, faithfulness, population-consistency and composition-consistency. Brandl et al. (2016) show that the two axioms characterize the family of all maximal lotteries in a probabilistic social choice setting. The joint implication of population-consistency and composition-consistency in a deterministic social choice setting, however, is an open question.
Notes
This condition is called unanimity. Population-consistency says that whenever an alternative is chosen simultaneously by two electorates, this alternative should also be chosen by the union of the electorates. Brandl et al. (2016) also require that the set of preference profiles where a social choice rule chooses more than one alternative be negligible.
Note that composition-consistency with respect to dominant clone winners does not make a statement about the best clone alternative in situations in which no clone of a winning alternative Pareto dominates all of its clones.
Continuity says that if an alternative is chosen in one problem and the set of voters of another problem contains a sufficiently large replica of the agents in the first problem, then that alternative should also be chosen in the second problem. Independence of dominated alternatives states that removing all Pareto-dominated alternatives should not alter the social choice.
For instance, the unanimous scoring rule that uses the score vector \((2,1,1,\ldots ,1,0)\) for any \(m > 2\) satisfies composition-consistency with respect to dominant clone winners, but not independence of dominated alternatives.
Efficiency says that a Pareto-dominated alternative should not be chosen. Tops-only requires the social choice set to be identical for two choice problems at which the set of top-ranked alternatives are identical.
For instance, the simple scoring rule with the associated score vector \((2,0,\ldots ,0,1)\) satisfies the monotonicity requirement of Kelly and Qi (2016), but not the monotonicity axiom defined here. The simple scoring rule with the associated score vector \((1,1,\ldots ,1,0)\), on the other hand, meets the monotonicity condition defined here, but not that of Kelly and Qi (2016).
The conjunction of the four axioms in this section is not equivalent to composition-consistency.
The proof given for this fact was developed by an anonymous referee to whom I am deeply grateful.
As Proposition 3 shows, composition-consistency with respect to non-clone losers also clash with faithfulness. However, a weaker version of the axiom is not readily available, and hence we do not seek a modification of this axiom.
We show the independence of the axioms used in the theorems in the Appendix.
These are the same profiles in (3).
References
Brandl F, Brandt F, Seedig HG (2016) Consistent probabilistic social choice. Econometrica 84(5):1839–1880
Ching S (1996) A simple characterization of plurality rule. J. Econ. Theory 71(1):298–302
Dutta B, Jackson MO, Le Breton M (2001) Strategic candidacy and voting procedures. Econometrica 69(4):1013–1037
Elkind E, Faliszewski P, Slinko A (2011) Cloning in elections: finding the possible winners. J Artif Intell Res 42:529–573
Elkind E, Faliszewski P, Slinko A (2012) Clone structures in voters’ preferences. In: Proceedings of the 13th ACM conference on electronic commerce, pp 496–513. ACM
Fine B, Fine K (1974a) Social choice and individual rankings I. Rev Econ Stud 41(3):303–322
Fine B, Fine K (1974b) Social choice and individual rankings II. Rev Econ Stud 41:459–475
Freeman R, Brill M, Conitzer V (2014) On the axiomatic characterization of runoff voting rules. In: Twenty-eighth AAAI conference on artificial intelligence
Kelly JS, Qi S (2016) Characterizing plurality rule on a fixed population. Econ Lett 146:39–41
Laffond G, Lainé J, Laslier J-F (1996) Composition-consistent tournament solutions and social choice functions. Soc Choice Welf 13(1):75–93
Laslier J-F (1996) Rank-based choice correspondences. Econ Lett 52(3):279–286
Laslier J-F (2000) Aggregation of preferences with a variable set of alternatives. Soc Choice Welf 17(2):269–282
May KO (1952) A set of independent necessary and sufficient conditions for simple majority decision. Econometrica 20:680–684
Richelson J (1978) A characterization result for the plurality rule. J Econ Theory 19(2):548–550
Schulze M (2011) A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method. Soc Choice Welf 36(2):267–303
Sekiguchi Y (2012) A characterization of the plurality rule. Econ Lett 116(3):330–332
Smith JH (1973) Aggregation of preferences with variable electorate. Econometrica 41(6):1027–1041
Tideman TN (1987) Independence of clones as a criterion for voting rules. Soc Choice Welf 4(3):185–206
Yeh C-H (2008) An efficiency characterization of plurality rule in collective choice problems. Econ Theory 34(3):575–583
Young HP (1974) An axiomatization of Borda’s rule. J Econ Theory 9(1):43–52
Young HP (1975) Social choice scoring functions. SIAM J Appl Math 28(4):824–838
Zavist TM, Tideman TN (1989) Complete independence of clones in the ranked pairs rule. Soc Choice Welf 6(2):167–173
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Z. Emel Öztürk: I am grateful to Patrick Harless for helpful comments. I would also like to thank audiences in the 5th World Congress of the Game Theory Society and participants in seminars in Glasgow and Maastricht.
Appendix
Appendix
The first rule in Table 1 is a social choice rule for which there exists an \(\alpha \) in \({\mathcal {A}}\) such that for each \(R_{N}(A)\) in \({\mathcal {R}}\), \(F_{\alpha }(R_{N}(A))= \{\alpha \}\) if \(\alpha \in \bigcup _{i\in N}\{\tau (R_{i}(A))\}\) and \(F_{\alpha }(R_{N}(A))=P(R_{N}(A))\) otherwise. That is, \(F_{\alpha }\) chooses the fixed alternative \(\alpha \) at each preference profile in which \(\alpha \) is top ranked by at least one individual. The rule selects all Plurality winners at any other preference profile. The second rule is the dictatorial rule \(F_{\text {D}}\). Let \(\succ \) be a strict and complete order on the set of natural numbers. An individual i has a higher priority than individual j if \(i \succ j\). For each \(R_{N}(A)\) in \({\mathcal {R}}\), the dictatorial rule \(F_{\text {D}}\) chooses the most preferred alternative of the individual with the highest priority in N, i.e., \(F_{\text {D}}(R_{N}(A))=\{\tau (R_{i}(A)): i \succ j \text { for each }j \in N \}\). The third rule is the trivial rule defined in Sect. 3. The fourth rule is the top rule \(F_{\text {Top}}\). For each \(R_{N}(A)\) in \({\mathcal {R}}\), the top rule chooses top-ranked alternatives, i.e., \(F_{\text {T}}(R_{N}(A))=\bigcup _{i\in N}\{\tau (R_{i}(A))\}\). The fifth rule is the simple scoring rule with the associated score vector \((2,1,\ldots ,1,0)\) for each \(m \in {\mathbb {N}}\). The sixth rule is the simple scoring rule with the associated score vector \((2,0,\ldots ,0,1)\) for each \(m \in {\mathbb {N}}\). The seventh rule, \(F^{\text {B}}\) is Borda’s rule defined in Sect. 5.
First, we prove Lemma 1.
Lemma 1. Let F be a scoring rule with \(F=F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{1}\). For each \(\beta \)in \(\{1,2,\ldots , \alpha \},\)each m in \({\mathbb {N}},\)let \(s^{\beta }_{m}=(s^{\beta }_{m;m}, s^{\beta }_{m-1;m},\ldots ,s^{\beta }_{1;m})\)be the score vector associated with the simple scoring rule \(F^{\beta }\).
-
(a)
F satisfies faithfulness and composition-consistency with respect to non-clone winners if and only for each \(\beta \)in \(\{1,2,\ldots , \alpha \}\), each m in \({\mathbb {N}}\), we have \(s^{\beta }_{m}=(x^{\beta }_{m},y^{\beta }_{m}, y^{\beta }_{m},\ldots ,y^{\beta }_{m},z^{\beta }_{m})\)with \(x^{\beta }_{m} \ge y^{\beta }_{m}\) and \(z^{\beta }_{m} \ge y^{\beta }_{m}\).
-
(b)
If F satisfies faithfulness and composition-consistency with respect to clone losers, then, for each \(m \ge 3,\)we have \(s^{1}_{1;m} \ge s^{1}_{m-1;m}\).
Proof
Let F be a scoring rule with \(F=F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{1}\). For each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), each m in \({\mathbb {N}}\), let \(s^{\beta }_{m}=(s^{\beta }_{m;m}, s^{\beta }_{m-1;m},\ldots ,s^{\beta }_{1;m})\) be the score vector associated with the simple scoring rule \(F^{\beta }\).
-
(a)
Assume that F satisfies faithfulness and composition-consistency with respect to non-clone winners.
Assume \(m \ge 3\). Consider the following preference profiles.
$$\begin{aligned} R= \begin{array}{cccc} R_{1} &{} R_{2} &{} \ldots &{} R_{m-1} \\ \hline a_{1} &{} a_{2} &{} \ldots &{} a_{m-1} \\ a_{2} &{} a_{3} &{} \ldots &{} a_{1} \\ \vdots &{} \vdots &{} \vdots &{} \vdots \\ a_{m-1} &{} a_{1} &{} \ldots &{} a_{m-2} \\ \end{array} \quad \quad R'= \begin{array}{cccc} R'_{1} &{} R'_{2} &{} \ldots &{} R'_{m-1} \\ \hline a_{1} &{} a_{2} &{} \ldots &{} a_{m-1} \\ a_{m} &{} a_{3} &{} \ldots &{} a_{1} \\ a_{2} &{} \ldots &{} \ldots &{} a_{m} \\ \vdots &{} a_{1} &{} \vdots &{} \vdots \\ a_{m-1} &{} a_{m} &{} \ldots &{} a_{m-2} \\ \end{array} \end{aligned}$$(3)By neutrality and anonymity, \(F(R)=\{a_{1}, a_{2},\ldots , a_{m-1}\}\). At the preference profile \(R'\), \(a_{1}\) and \(a_{m}\) are clones of each other. Thus, by composition-consistency with respect to non-clone winners, we have \(\{a_{2},\ldots , a_{m-1}\} \subseteq F(R')\). That is, for each \(\beta \) in \(\{1,2,\ldots ,\alpha \}\), we have \(\{a_{2},\ldots , a_{m-1}\} \subseteq F^{\beta }(R')\).
For each \(\beta \) in \(\{1,2,\ldots ,\alpha \}\), each k in \(\{1,2,\ldots ,m-2\}\), the total score of \(a_{m-k}\) at \(R'\) is \(\sum ^{k}_{i=1}s^{\beta }_{i;m} + \sum ^{m}_{i=k+2}s^{\beta }_{i;m}\). Since \(\{a_{2},\ldots , a_{m-1}\} \subseteq F(R')\), the total scores of \(a_{2},a_{3}, \ldots , a_{m-1}\) at \(R'\) must be the same. The equality of the total scores of \(a_{m-1}\) and \(a_{m-2}\) implies
$$\begin{aligned} s^{\beta }_{1;m}+s^{\beta }_{3;m}+\ldots +s^{\beta }_{m;m}=s^{\beta }_{1;m}+s^{\beta }_{2;m}+s^{\beta }_{4;m}+\ldots +s^{\beta }_{m;m}\text{. } \end{aligned}$$That is, \(s^{\beta }_{3;m}=s^{\beta }_{2;m}\). A similar calculation using the total scores of \(a_{m-2}\) and \(a_{m-3}\) yields \(s^{\beta }_{3;m}=s^{\beta }_{4;m}\). Iterated use of the total scores of \(a_{m-3}, \ldots ,a_{2}\) yields \(s^{\beta }_{2;m}=s^{\beta }_{3;m}=\ldots =s^{\beta }_{m-1;m}\). That is, each \(s^{\beta }_{m}\) takes the form \((x^{\beta }_{m},y^{\beta }_{m},y^{\beta }_{m},\ldots ,y^{\beta }_{m},z^{\beta }_{m})\), where \(x^{\beta }_{m},y^{\beta }_{m},z^{\beta }_{m} \in {\mathbb {R}}\).
To see that \(x^{\beta }_{m} \ge y^{\beta }_{m}\) and \(z^{\beta }_{m} \ge y^{\beta }_{m}\), consider the following preference profiles.
$$\begin{aligned} {\hat{R}} = \begin{array}{ccc} {\hat{R}}_{1} &{} {\hat{R}}_{2} \\ \hline a &{} b \\ b &{} a \\ \end{array} \quad \quad {\hat{R}}' = \begin{array}{cc} {\hat{R}}'_{1} &{} {\hat{R}}'_{2} \\ \hline a &{} b \\ a_{1} &{} a_{1} \\ \vdots &{} \vdots \\ a_{m-2} &{} a \\ b &{} a_{m-2} \\ \end{array} \quad \quad {\tilde{R}} = \begin{array}{cc} {\tilde{R}}_{1} &{} {\tilde{R}}_{2} \\ \hline a_{1} &{} a_{1} \\ a_{2} &{} a_{2} \\ \vdots &{} \vdots \\ a_{m} &{} a_{m} \\ \end{array} \end{aligned}$$By neutrality and anonymity, \(F({\hat{R}})=\{a,b\}\). The preference profile \({\hat{R}}'\) is obtained from \({\hat{R}}\) by cloning a. The total scores of a, b and \(a_{m-2}\) at \({\hat{R}}'\) are, respectively, \(x^{\beta }_{m} + y^{\beta }_{m}\); \(x^{\beta }_{m} + z^{\beta }_{m}\) and \(y^{\beta }_{m} + z^{\beta }_{m}\). By composition-consistency with respect to non-clone winners, we must have \(b \in F({\hat{R}}')\), which implies that \(x^{\beta }_{m} + z^{\beta }_{m} \ge y^{\beta }_{m} + z^{\beta }_{m}\) and \(x^{\beta }_{m} + z^{\beta }_{m} \ge x^{\beta }_{m} + y^{\beta }_{m}\), i.e., \(x^{\beta }_{m} \ge y^{\beta }_{m}\) and \(z^{\beta }_{m} \ge y^{\beta }_{m}\).
-
(b)
Assume that F satisfies faithfulness and composition-consistency with respect to clone losers.
Let \(m \ge 3\). Consider the following profiles.
$$\begin{aligned} R= \begin{array}{cc} R_{1} &{} R_{2} \\ \hline a_{1} &{} a_{m} \\ a_{2} &{} a_{1} \\ \vdots &{} \vdots \\ a_{m} &{} a_{m-1} \\ \end{array} \quad \quad R'= \begin{array}{cc} R'_{1} &{} R'_{2} \\ \hline a_{1} &{} a_{m} \\ a_{2} &{} a^{1}_{m} \\ \vdots &{} \vdots \\ a_{m-1} &{} a^{m-2}_{m} \\ a_{m} &{} a_{1} \\ a^{1}_{m} &{} a_{2} \\ a^{2}_{m} &{} \\ \vdots &{} \vdots \\ a^{m-2}_{m} &{} a_{m-1} \\ \end{array} \end{aligned}$$Suppose, for a contradiction, that \(s^{1}_{m-1;m} > s^{1}_{1;m}\). Then, \(a_{m} \not \in F(R)\) since the total score of \(a_{1}\) at R is higher than the total score of \(a_{m}\) according to the score vector of \(F^{1}\). The preference profile \(R'\) is obtained from R by adding \(m-2\) clones of \(a_{m}\). The total score of \(a_{m}\) at \(R'\) is equal to the total score of \(a_{1}\). Similarly, for each \(k \in \{1,2,\ldots ,m-2\}\), the total score of \(a^{k}_{m}\) is equal the total score of \(a_{k+1}\). Thus, at least one of \(a_{m}, a^{1}_{m}, \ldots , a^{m-1}_{m}\) will be chosen at \(R'\), a contradiction with composition-consistency with respect to clone losers. Thus, it must be that \(a_{m} \in F(R)\). That is, \(s^{1}_{1;m}\ge s^{1}_{m-1;m}\).
\(\square \)
Proposition 1. The trivial rule is the unique scoring rule that satisfies composition-consistency.
Proof
It is easy to verify that the trivial rule satisfies the axioms. Conversely, let F be a scoring rule that satisfies composition-consistency. By Lemma 1, there exist simple scoring rules \(F^{\alpha }, F^{\alpha -1}, \ldots , F^{1}\) with \(F=F^{\alpha } \circ F^{\alpha -1}\circ \cdots \circ F^{1}\) such that for each m in \({\mathbb {N}}\) and for each \(\beta \) in \(\{1,2,\ldots ,\alpha \}\), the score vector associated with \(F^{\beta }\) for m alternatives takes the form \((x^{\beta }_{m},y^{\beta }_{m}, y^{\beta }_{m},\ldots ,y^{\beta }_{m},z^{\beta }_{m})\) with \(x^{\beta }_{m} \ge y^{\beta }_{m}\) and \(z^{\beta }_{m} \ge y^{\beta }_{m}\).
We will first show that F must be the trivial rule for 2 alternatives. Consider the following preference profiles for \(m>3\).Footnote 12
Assume that F is not the trivial rule for 2 alternatives.
Case 1. Assume that \(F(R'\vert _{\{a_{1},a_{m}\}})=\{a_{1}\}\). Let \(R''\) be a preference profile obtained from \(R'\) by swapping \(a_{1}\) and \(a_{m}\) at \(R'_{1}\). That is,
The preference profile \(R''\) is obtained from R by cloning \(a_{1}\). Since \(F(R'|_{\{a_{1},a_{m}\}} =\{a_{1}\}\), there must be some \(\gamma \) in \(\{1,2,\ldots ,\alpha \}\) such that \(s^{\gamma }_{2;2} > s^{\gamma }_{1;2}\) and \(s^{\beta }_{2;2} = s^{\beta }_{1;2}\) for each \(\beta < \gamma \). Since \(m > 3\), it must be that \(F^{\gamma }(R''\vert _{\{a_{1},a_{m}\}})=\{a_{1}\}\). Then, \(F(R''\vert _{\{a_{1},a_{m}\}})=\{a_{1}\}\) by definition of a scoring rule. By composition-consistency, then, \(F(R'')=\{a_{1},a_{2},\ldots ,a_{m-1}\}\). On the other hand, for each \(F^{\beta }\), the total score of \(a_{m}\) at \(R''\) is equal to the total score of \(a_{2}\) at \(R''\). Hence, it must be that \(a_{m} \in F(R'')\), a contradiction.
Case 2. Assume that \(F(R'\vert _{\{a_{1},a_{m}\}})=\{a_{m}\}\). Let \(R'''\) be a preference profile obtained from \(R'\) by swapping \(a_{1}\) and \(a_{m}\) at \(R'_{2}\). That is,
The preference profile \(R'''\) is obtained from R by cloning \(a_{1}\). A similar reasoning to the above yields \(F(R''\vert _{\{a_{1},a_{m}\}})=\{a_{m}\}\). So, by composition-consistency, \( F(R''')=\{a_{2},\ldots ,a_{m-1}, a_{m}\}\). For each \(F^{\beta }\), the total score of \(a_{1}\) at \(R'''\) is equal to the total score of \(a_{m-1}\) at \(R'''\). So, it must be that \(a_{1} \in F(R''')\), a contradiction. Thus, F must be the trivial rule for \(m=2\), i.e., \(F(R'\vert _{\{a_{1},a_{m}\}})=\{a_{1}, a_{m}\}\).
Now, assume that F is the trivial rule for \(m \ge 2\). We will show that F must be the trivial rule for \(m+1\). To see that, consider the following profiles.
Since F is the trivial rule for m alternatives, we have \(F({\hat{R}}) = \{a_{1},\ldots ,a_{m}\}\). The preference profile \({\hat{R}}'\) is obtained from \({\hat{R}}\) by cloning \(a_{m}\). Since F is the trivial rule for two alternatives, we have \(F({\hat{R}}'|_{\{a_{m},a_{m+1}\}} = \{a_{m}, a_{m+1}\}\). Thus, by composition-consistency, we have \(F({\hat{R}}) = \{a_{1},\ldots ,a_{m},a_{m+1}\}\), i.e., F is the trivial rule for \(m+1\) alternatives. This proves that F is the trivial rule for all m in \({\mathbb {N}}\). \(\square \)
Proposition 2. The trivial rule is the unique scoring rule that satisfies
-
(a)
composition-consistency with respect to non-clone losers and composition-consistency with respect to non-clone winners.
-
(b)
composition-consistency with respect to non-clone losers and composition-consistency with respect to clone losers.
-
(c)
composition-consistency with respect to clone winners.
Proof
Let F be a scoring rule.
-
(a)
Let F satisfy composition-consistency with respect to non-clone losers and composition-consistency with respect to non-clone winners. By Lemma 1, there exist simple scoring rules \(F^{\alpha }, F^{\alpha -1}\), \(\ldots , F^{1}\) with \(F=F^{\alpha } \circ F^{\alpha -1}\circ \cdots \circ F^{1}\) such that for each m in \({\mathbb {N}}\) and for each \(\beta \) in \(\{1,2,\ldots ,\alpha \}\), the score vector associated with \(F^{\beta }\) for m alternatives takes the form \((x^{\beta }_{m},y^{\beta }_{m}, y^{\beta }_{m},\ldots ,y^{\beta }_{m},z^{\beta }_{m})\) with \(x^{\beta }_{m} \ge y^{\beta }_{m}\) and \(z^{\beta }_{m} \ge y^{\beta }_{m}\).
Let \(m \ge 3\). Assume. without loss of generality, that \(y^{\beta }_{m} = 0\) for each \(\beta \) in \(\{1,2,\ldots , \alpha \}\). There are four possible cases: \(x^{1} >0\) and \(z^{1} >0\); \(x^{1} >0\) and \(z^{1} = 0\); \(x^{1} =z^{1} = 0\) and \(x^{1} = 0\) and \(z^{1} > 0\).
First, assume that \(x^{1} >0\) and \(z^{1} >0\). Consider the following profiles.
$$\begin{aligned} R= \begin{array}{cc} R_{1} &{} R_{2} \\ \hline a_{1} &{} a_{m} \\ a_{2} &{} a_{3} \\ \vdots &{} \vdots \\ \cdot &{} a_{1} \\ a_{m} &{} a_{2} \end{array} \quad \quad R'= \begin{array}{cc} R'_{1} &{} R'_{2} \\ \hline a_{1} &{} a_{m} \\ a_{2} &{} a'_{m} \\ \vdots &{} \vdots \\ \cdot &{} \cdot \\ a_{m} &{} a_{1} \\ a'_{m} &{} a_{2} \end{array} \end{aligned}$$At R, the total scores of \(a_{1}, a_{2}\) and \(a_{m}\) are, respectively, \(x^{1}\), \(z^{1}\) and \(x^{1} + z^{1}\), whereas all other alternatives receive a total score of zero. Thus, \(F^{1}(R)=\{a_{m}\}\), i.e., \(F(R)=\{a_{m}\}\). The preference profile \(R'\) is obtained from R by cloning \(a_{m}\) once. By composition-consistency with respect to non-clone losers, we must have \(F(R) \subseteq \{a_{m},a'_{m}\}\). However, the total score of \(a_{1}\) is the same as the total score of \(a_{m}\) at \(R'\), whereas the total score of \(a_{2}\) is the same as the total score of \(a'_{m}\). That is, we have either \(a_{1} \in F(R)\) or \(a_{2} \in F(R)\) or both, a contradiction.
Next, assume that \(x^{1} >0\) and \(z^{1} = 0\). Consider the following profiles.
$$\begin{aligned} R= \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} R_{1} &{} R_{2} &{} R_{3} &{} R_{4} &{} R_{5} \\ \hline a_{1} &{} a_{1} &{} a_{1} &{} a_{2} &{} a_{2} \\ a_{2} &{} a_{2} &{} a_{2} &{} a_{1} &{} a_{1} \\ \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots \\ a_{m} &{} a_{m} &{} a_{m} &{} a_{m} &{} a_{m} \end{array} \quad \quad R'= \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} R'_{1} &{} R'_{2} &{} R'_{3} &{} R'_{4} &{} R'_{5} \\ \hline a_{1} &{} a'_{1} &{} a''_{1} &{} a_{2} &{} a_{2} \\ a'_{1} &{} a_{1} &{} a_{1} &{} a_{1} &{} a_{1} \\ a''_{1} &{} a''_{1} &{} a'_{1} &{} a''_{1} &{} a'_{1} \\ \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots \\ a_{m} &{} a_{m} &{} a_{m} &{} a_{m} &{} a_{m} \end{array} \end{aligned}$$We have \(F(R)=\{a_{1}\}\) since \(F^{1}(R)=\{a_{1}\}\). The preference profile \(R'\) is obtained from R by adding two clones of \(a_{1}\). Thus, by composition-consistency with respect to non-clone losers, it must be that \(a_{2} \not \in F(R')\). However, \(F(R')=\{a_{2}\}\) since \(F^{1}(R')=\{a_{2}\}\), a contradiction. The case in which \(x^{1} =0\) and \(z^{1} > 0\) is symmetric to the previous case, and hence is omitted. Thus, we have proven that \(F^{1}\) must be the trivial rule. But then, F is equivalent to \(F^{\alpha } \circ F^{\alpha -1}\circ \cdots \circ F^{2}\). The reasoning above implies that \(F^{2}\) must also be the trivial rule. Iterated application of the proof implies that F must be the trivial rule.
-
(b)
Assume that F satisfies composition-consistency with respect to non-clone losers and composition-consistency with respect to clone losers. Let \(F=F^{\alpha } \circ F^{\alpha -1}\circ \cdots \circ F^{1}\) and \(s^{\beta }_{m}=(s^{\beta }_{m;m},\ldots ,s^{\beta }_{1;m})\) be the score vector associated with \(F^{\beta }\) for m alternatives.
Let us first assume that \(m\ge 3\). Let R be a preference profile with one voter as follows.
$$\begin{aligned} R= \begin{array}{c} \\ a_{1} \\ a_{2} \\ \vdots \\ a_{m-1} \\ a_{m} \\ \end{array} \end{aligned}$$This preference profile will be kept fixed for the rest of the proof.
Step 1. We will first show that we cannot have \(F(R)=\{a_{1}\}\) or \(F(R)=\{a_{m}\}\).
Suppose, for a contradiction, that \(F(R)=\{a_{1}\}\), i.e., that F satisfies faithfulness. Consider the following profiles.
$$\begin{aligned} {\hat{R}}= \begin{array}{ccccc} {\hat{R}}_{1} &{} {\hat{R}}_{2} &{} \ldots &{} {\hat{R}}_{m} &{} {\hat{R}}_{m+1}\\ \hline a_{1} &{} a_{2} &{} \ldots &{} a_{m} &{} a_{m} \\ a_{2} &{} a_{3} &{} \ldots &{} a_{1} &{} a_{2} \\ \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots \\ a_{m} &{} a_{1} &{} \ldots &{} a_{m-1} &{} a_{m-1} \\ \end{array} \quad \quad {\hat{R}}'= \begin{array}{ccccc} {\hat{R}}'_{1} &{} {\hat{R}}'_{2} &{} \ldots &{} {\hat{R}}'_{m} &{} {\hat{R}}'_{m+1}\\ \\ \hline a_{1} &{} a_{2} &{} \ldots &{} a_{m} &{} a'_{m} \\ a_{2} &{} a_{3} &{} \ldots &{} a'_{m} &{} a_{m} \\ &{} &{} \ldots &{} a_{1} &{} a_{2} \\ \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots \\ a_{m-1} &{} a_{m} &{} \ldots &{} \cdot &{} \cdot \\ a_{m} &{} a'_{m} &{} \ldots &{} \cdot &{} \cdot \\ a'_{m} &{} a_{1} &{} \ldots &{} a_{m-1} &{} a_{m-1} \\ \end{array} \end{aligned}$$By neutrality and anonymity, we have \(F({\hat{R}}_{1},{\hat{R}}_{2},\ldots ,{\hat{R}}_{m})=\{a_{1},a_{2},\dots ,a_{m}\}\). The faithfulness of F implies that \(F({\hat{R}}_{m+1})=\{a_{m}\}\). By reinforcement, then, we have \(F({\hat{R}})=\{a_{m}\}\). The preference profile \({\hat{R}}'\) is obtained from \({\hat{R}}\) by cloning \(a_{m}\) once. By composition-consistency with respect to non-clone losers, we have \(a_{2}, a_{3},\ldots , a_{m-1} \not \in F({\hat{R}}')\). For each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), the total scores of \(a_{2}\) and \(a'_{m}\) at \({\hat{R}}'\) are both
$$\begin{aligned} s^{\beta }_{1;m} + s^{\beta }_{2;m} + \ldots + s^{\beta }_{m+1;m+1}\text{. } \end{aligned}$$(4)That is, for each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), we have \(a'_{m} \in F^{\beta }({\hat{R}}')\) if and only if \(a_{2} \in F^{\beta }({\hat{R}}')\). But then this would imply that \(a_{2} \in F({\hat{R}}')\), which we know is not true. It must therefore be that \(F({\hat{R}}')=\{a_{m}\}\), i.e., \(a_{m} \in F^{1}({\hat{R}}')\) and \(a'_{m} \not \in F^{1}({\hat{R}}')\). Using the score vector of \(F^{1}\), the total score of \(a_{m}\) at \({\hat{R}}'\) is
$$\begin{aligned} s^{1}_{2;m+1} + s^{1}_{3;m+1} + \cdots + 2s^{1}_{m;m+1} + s^{1}_{m+1;m+1}\text{. } \end{aligned}$$(5)Since \(a_{m} \in F^{1}({\hat{R}}')\) and \(a'_{m} \not \in F^{1}({\hat{R}}')\), the sum in (5) must be larger than the sum in (4) for \(\beta =1\). That is, \(s^{1}_{m;m+1} > s^{1}_{1;m+1}\).
Moreover, \(F(R)=\{a_{1}\}\) implies \(F(\breve{R})=\{a_{1}\}\) for any \(\breve{R}\) obtained from R by cloning one of \(a_{2},\ldots ,a_{m}\) once. That is, it must be that \(a_{1} \in F^{1}(\breve{R})\), i.e., \(s^{1}_{m+1;m+1} \ge s^{1}_{m;m+1}\).
We have thus shown that, for each number of alternatives \(m > 3\),
$$\begin{aligned} s^{1}_{m;m} \ge s^{1}_{m-1;m} > s^{1}_{1;m}\text{. } \end{aligned}$$Next, consider the following profiles with \(m >3\).
$$\begin{aligned} {\tilde{R}}= \begin{array}{cc} {\tilde{R}}_{1} &{} {\tilde{R}}_{2} \\ \hline a_{1} &{} a_{m} \\ a_{2} &{} a_{1} \\ \vdots &{} \vdots \\ a_{m} &{} a_{m-1} \\ \end{array} \quad \quad {\tilde{R}}'= \begin{array}{cc} {\tilde{R}}'_{1} &{} {\tilde{R}}'_{2} \\ \hline a_{1} &{} a_{m} \\ a_{2} &{} a^{1}_{m} \\ \vdots &{} \vdots \\ a_{m-1} &{} a^{m-2}_{m} \\ a_{m} &{} a_{1} \\ a^{1}_{m} &{} a_{2} \\ a^{2}_{m} &{} \\ \vdots &{} \vdots \\ a^{m-2}_{m} &{} a_{m-1} \\ \end{array} \end{aligned}$$Since \(s^{1}_{m-1;m} > s^{1}_{1;m}\), the total score of \(a_{1}\) at \({\tilde{R}}\) is greater than the total score of \(a_{m}\) at \({\tilde{R}}\). Thus, we have \(a_{m} \not \in F^{1}({\tilde{R}})\), i.e., \(a_{m} \not \in F({\tilde{R}})\). The preference profile \({\tilde{R}}'\) is obtained from \({\tilde{R}}\) by adding \(m-2\) clones of \(a_{m}\). By composition-consistency with respect to clone losers, it must be that \(a_{m}, a^{1}_{m}, \ldots , a^{m-2}_{m} \not \in F({\tilde{R}}')\). However, the total score of \(a_{m}\) at \({\tilde{R}}'\) is equal to the total score of \(a_{1}\). Similarly, for each \(k \in \{1,2,\ldots ,m-2\}\), the total score of \(a^{k}_{m}\) is equal the total score of \(a_{k+1}\). Thus, at least one of \(a_{m}, a^{1}_{m}, \ldots , a^{m-2}_{m}\) will be chosen at \({\tilde{R}}'\), a contradiction.
This shows that we cannot have \(F(R)=\{a_{1}\}\). The impossibility of \(F(R)=\{a_{m}\}\) can be proven similarly, and hence is omitted.
Step 2. Assume that there exists \(k \in \{1, 2, \ldots , m-1\}\) such that \(a_{k} \not \in F(R)\). Let us further assume that \(a_{k}\) is the highest ranked alternative among those that are not chosen by F at R. Let \(R'\) be a preference profile obtained from R by adding \(m-k\) clones of \(a_{k}\), whereas \(R''\) is a preference profile obtained from R by adding \(m-k\) clones of \(a_{m}\) as follows (for convenience, we reproduce R below).
$$\begin{aligned} R= \begin{array}{c} \\ a_{1} \\ a_{2} \\ \vdots \\ a_{m-1} \\ a_{m} \\ \end{array} \quad \quad R'= \begin{array}{c} \\ a_{1} \\ a_{2} \\ \vdots \\ a_{k} \\ a^{1}_{k} \\ \vdots \\ a^{m-k}_{k} \\ a_{k+1} \\ \vdots \\ a_{m} \\ \end{array} \quad \quad R''= \begin{array}{c} \\ a_{1} \\ a_{2} \\ \vdots \\ a_{k} \\ a_{k+1} \\ \vdots \\ a_{m} \\ a^{1}_{m} \\ \vdots \\ a^{m-k}_{m}\\ \end{array} \end{aligned}$$Since \(a_{k} \not \in F(R)\), by composition-consistency with respect to clone losers, \(a_{k}, a^{1}_{k}, \ldots , a^{m-k}_{k} \not \in F(R')\). Moreover, \(R'\) and \(R''\) both have \(m'=2m-k\) alternatives, and the scores of \(a_{k}, \ldots ,a_{m}\) at \(R''\) are the same as the scores of \(a_{k}, a^{1}_{k}, \ldots , a^{m-k}_{k}\), respectively. Thus, we have \(a_{k}, \ldots ,a_{m} \not \in F(R'')\).
There are 3 possibilities: \(F(R'') \cap \{a_{1},a_{2},\ldots , a_{k-1}\}= \{a_{1},a_{2},\ldots , a_{k-1}\}\) or \(F(R'') \subset \{a_{1},a_{2},\ldots , a_{k-1}\}\) or \(F(R'') \cap \{a_{1},a_{2},\ldots , a_{k-1}\}= \emptyset \).
Case 1. Assume \(F(R'') \cap \{a_{1},a_{2},\ldots , a_{k-1}\}= \{a_{1},a_{2},\ldots , a_{k-1}\}\). Consider the following profiles.
$$\begin{aligned} {\bar{R}}= \begin{array}{cc} {\bar{R}}_{1} &{} {\bar{R}}_{2} \\ \hline a_{1} &{} a_{k} \\ a_{2} &{} a_{2} \\ \vdots &{} \vdots \\ a_{k-2} &{} a_{k-2} \\ a_{k-1} &{} a_{1} \\ a_{k} &{} a_{k-1} \\ a_{k+1} &{} a^{2}_{m} \\ \vdots &{} \vdots \\ a^{1}_{m} &{} a_{m} \\ a^{2}_{m} &{} a_{k+1} \\ \vdots &{} \vdots \\ a^{m-k}_{m} &{} a_{m-1} \\ a_{m} &{} a^{1}_{m} \\ \end{array} \quad \quad {\bar{R}}'= \begin{array}{cc} {\bar{R}}'_{1} &{} {\bar{R}}'_{2} \\ \hline a_{1} &{} a_{k} \\ a_{2} &{} a^{1}_{k} \\ \vdots &{} \vdots \\ a_{k-1} &{} a^{k-2}_{k} \\ a^{1}_{k} &{} a_{2} \\ \vdots &{} \vdots \\ a_{k} &{} a_{1} \\ a^{k-2}_{k} &{} a_{k-1} \\ a_{k+1} &{} a^{2}_{m} \\ \vdots &{} \vdots \\ a^{1}_{m} &{} a_{m} \\ a^{2}_{m} &{} a_{k+1} \\ \vdots &{} \vdots \\ a^{m-k}_{m} &{} a_{m-1} \\ a_{m} &{} a^{1}_{m} \\ \end{array} \end{aligned}$$Since F is a scoring rule, \(F(R'') \cap \{a_{1},a_{2},\ldots , a_{k-1}\}= \{a_{1},a_{2},\ldots , a_{k-1}\}\) implies that \(F({\bar{R}}_{1})=\{a_{1},a_{2},\ldots , a_{k-1}\}\) and \(F({\bar{R}}_{2})= \{a_{k},a_{2},\ldots , a_{k-2},a_{1}\}\). Thus, by reinforcement, we have \( F({\bar{R}})= F({\bar{R}}_{1}) \cap F({\bar{R}}_{2})=\{a_{1},a_{2},\ldots , a_{k-2}\}\). The preference profile \({\bar{R}}'\) is obtained from \({\bar{R}}\) by adding \(k-2\) clones of \(a_{k}\). Composition-consistency with respect to clone losers and composition-consistency with respect to non-clone losers imply \(a_{k-1},a_{k}, a^{1}_{k},\ldots ,a^{k-2}_{k},a_{m},\ldots ,a^{m-k}_{m} \not \in F({\bar{R}}')\). But, the total score of \(a_{k}\) at \({\bar{R}}'\) is the same as the total score of \(a_{1}\). Similarly, for each \(\ell \in \{1,2,\ldots ,k-2\}\), the total score of \(a^{\ell }_{k}\) is the same as the total score of \(a_{\ell +1}\). That is, either \(a_{k-1}\), \(a_{k}\) or at least one clone of \(a_{k}\), or \(a_{m}\) or at least one clone of \(a_{m}\) will be chosen by F at \({\bar{R}}'\), a contradiction.
Case 2. Assume \(F(R'') \subset \{a_{1},a_{2},\ldots , a_{k-1}\}\), i.e., there exists \(a_{t} \in \{a_{1},a_{2},\ldots , a_{k-1}\}\) such that \(a_{t} \not \in F(R'')\). But then, following the same logic in Step 1, we can find a preference profile \(R'''\) in which we have wither \(F(R'') \cap \{a_{1},a_{2},\ldots , a_{t-1}\}= \{a_{1},a_{2},\ldots , a_{t-1}\}\) or \(F(R'') \subset \{a_{1},a_{2},\ldots , a_{t-1}\}\) or \(F(R'') \cap \{a_{1},a_{2},\ldots , a_{k-1}\}= \emptyset \). If \(F(R'') \subset \{a_{1},a_{2},\ldots , a_{t-1}\}\), i.e., there exists \(a_{\ell } \in \{a_{1},a_{2},\ldots , a_{t-1}\}\) such that \(a_{\ell } \not \in F(R''')\). Iterated application yields that there exists a number of alternatives \(m'\) and a preference profile such that
$$\begin{aligned} R^{IV}= \begin{array}{c} \\ a_{1} \\ \vdots \\ a_{m} \\ a^{1}_{m} \\ \vdots \\ a_{m'}\\ \end{array} \end{aligned}$$where \(F(R^{IV}) \subseteq \{a_{1},a^{1}_{m},\ldots , a_{m'}\}\). Since \(R^{IV}\) is obtained from R by cloning some alternatives step by step, composition-consistency with respect to clone losers and composition-consistency with respect to non-clone losers together imply either \(F(R)=\{a_{1}\}\) or \(F(R)=\{a_{1},a_{m}\}\). We have already ruled out the first case, so assume \(F(R)=\{a_{1},a_{m}\}\) and consider the following profiles.
$$\begin{aligned} {\check{R}}= \begin{array}{cc} {\check{R}}_{1} &{} {\check{R}}_{2} \\ \hline a_{1} &{} a_{m} \\ a_{2} &{} \vdots \\ \vdots &{} \vdots \\ a_{m-1} &{} a_{1} \\ a_{m} &{} a_{2} \\ \end{array} \quad \quad {\check{R}}'= \begin{array}{cc} {\check{R}}'_{1} &{} {\check{R}}_{2} \\ \hline a_{1} &{} a_{m} \\ a_{2} &{} a'_{m}\\ \vdots &{} \vdots \\ a_{m} &{} a_{1} \\ a'_{m} &{} a_{2} \end{array} \end{aligned}$$Since F is a scoring rule, \(F(R)=\{a_{1},a_{m}\}\) implies that \(F({\check{R}}_{1})=\{a_{1},a_{m}\}\) and \(F({\check{R}}_{1})=\{a_{2},a_{m}\}\). Thus, by reinforcement, \(F({\check{R}}) = \{a_{m}\}\). The preference profile \({\check{R}}'\) is obtained from \({\check{R}}\) by cloning \(a_{m}\) once. By composition-consistency with respect to non-clone losers, it must be that \(a_{1}, a_{2},\ldots ,a_{m-1} \not \in F({\check{R}}')\). However, the total score of \(a_{m}\) at \({\check{R}}'\) is equal to the total score of \(a_{1}\) at \({\check{R}}'\), and the total score of \(a'_{m}\) at \({\check{R}}'\) is equal to the total score of \(a_{2}\) at \({\check{R}}'\). Thus, one or both of \(a_{1}\) and \(a_{2}\) will be chosen at \({\check{R}}'\), a contradiction.
Case 3. Assume that \(F(R'') \cap \{a_{1},a_{2},\ldots , a_{k-1}\}= \emptyset \). Then, it must be that \(F(R'') \subseteq \{ a^{1}_{m},\ldots ,a^{m-k}_{m}\}\).
Consider the following profiles with \(m'=2m-k\) alternatives.
$$\begin{aligned} {\dot{R}}= \begin{array}{cc} {\dot{R}}_{1} &{} {\dot{R}}_{2} \\ \hline a_{1} &{} a^{m-k}_{m} \\ a_{2} &{} a_{2} \\ \vdots &{} \vdots \\ a_{m} &{} a_{m} \\ a^{1}_{m} &{} a^{1}_{m} \\ a^{2}_{m} &{} a^{2}_{m} \\ \vdots &{} \vdots \\ a^{m-k}_{m} &{} a_{m-1} \\ \end{array} \quad \quad {\dot{R}}'= \begin{array}{cc} {\dot{R}}'_{1} &{} {\dot{R}}'_{2} \\ \hline a_{1} &{} a^{m-k}_{m} \\ a_{2} &{} {}^{1}a^{m-k}_{m} \\ \vdots &{} \vdots \\ a_{m} &{} \\ a^{1}_{m} &{} \\ a^{2}_{m} &{} \\ \vdots &{} \vdots \\ a^{m-k}_{m} &{} a_{1} \\ {}^{1}a^{m-k}_{m} &{} a_{2} \\ \vdots &{} \vdots \\ {}^{2m-k-1}a^{m-k}_{m} &{} a_{m'-1} \\ \end{array} \end{aligned}$$(6)We have already ruled out the possibility that \(F(R'')=\{a^{m-k}_{m}\}\). Thus, by reinforcement, it must be that \(F({\dot{R}})\subseteq \{a^{1}_{m},\ldots , a^{m-k-1}_{m} \}\), i.e., \(a^{m-k}_{m} \not \in F({\dot{R}})\). The preference profile \({\dot{R}}'\) is obtained from \({\dot{R}}\) by adding \(2m-k-1\) clones of \(a^{m-k}_{m}\). By composition-consistency with respect to clone losers, \(a^{m-k}_{m} ,{}^{1}a^{m-k}_{m} ,\ldots , {}^{2m-k-1}a^{m-k}_{m} \not \in F({\dot{R}}')\). However, every clone of \(a^{m-k}_{m}\) has the same score as one other alternative, i.e., at least one clone of \(a^{m-k}_{m}\) will be chosen by F at \({\dot{R}}'\), a contradiction.
We have therefore shown that, for \(m \ge 3\), F has to be the trivial rule, i.e., for each \(\beta \in \{1,2,\ldots ,\alpha \}\), we must have
$$\begin{aligned} s^{\beta }_{1;m} = s^{\beta }_{2;m} = \ldots = s^{\beta }_{m;m}\text{. } \end{aligned}$$Finally, let \(m=2\) and consider the following profiles.
$$\begin{aligned} R= \begin{array}{c} a_{1} \\ a_{2} \\ \end{array} \quad \quad R'= \begin{array}{c} a_{1} \\ a_{2} \\ a_{3} \\ \end{array} \end{aligned}$$Assume, without loss of generality, that \(a_{1} \not \in F(R)\). The preference profile \(R'\) is obtained from R by cloning \(a_{2}\). Thus, by composition-consistency with respect to non-clone losers, it must be that \(a_{1} \not \in F(R')\). But this contradicts the fact that F is the trivial rule for \(m\ge 3\) alternatives. So, F must be the trivial rule for 2 alternatives, i.e., F is the trivial rule.
-
(c)
We will first show that a simple scoring rule satisfies composition-consistency with respect to clone winners if and only if it is the trivial rule. We will focus on the only if part. Let F be a simple scoring rule with the associated score vector \(s_{m}=(s_{m;m},s_{m-1;m},\ldots ,s_{1;m})\) for m alternatives.
Consider the following profiles.
$$\begin{aligned} R = \begin{array}{c} R_{1} \\ \hline a_{1} \\ a_{2} \\ \end{array} \quad \quad R' = \begin{array}{cc} R'_{1} \\ \hline a_{1} \\ a'_{1} \\ a_{2} \\ \end{array} \quad \quad R'' = \begin{array}{cc} R''_{1} \\ \hline a_{1} \\ a''_{1} \\ a'_{1} \\ a_{2} \\ \end{array} \quad \quad R''' = \begin{array}{cc} R''_{1} \\ \hline a_{1} \\ a'''_{1} \\ a''_{1} \\ a'_{1} \\ a_{2} \\ \end{array} \end{aligned}$$First assume that F is unanimous, i.e., \(F(R)=\{a_{1}\}\). The preference profiles \(R', R''\) and \(R'''\) are obtained from R by cloning \(a_{1}\) once. By composition-consistency with respect to clone winners, we have \(a_{1} \in F(R''')\) and \(a'''_{1} \not \in F(R''')\), that is, it must be that \(s_{5:5} > s_{4,;5}\).
Next, consider the following profiles.
$$\begin{aligned} {\hat{R}}= \begin{array}{cccc} {\hat{R}}_{1} &{} {\hat{R}}_{2} &{} {\hat{R}}_{3} &{} {\hat{R}}_{4} \\ \hline a &{} b &{} c &{} d \\ b &{} c &{} d &{} a \\ c &{} d &{} a &{} b \\ d &{} a &{} b &{} c \end{array} \quad \quad {\hat{R}}' = \begin{array}{cccc} {\hat{R}}'_{1} &{} {\hat{R}}'_{2} &{} {\hat{R}}'_{3} &{}{\hat{R}}'_{4} \\ \hline a &{} b &{} c &{} d \\ a' &{} c &{} d &{} a' \\ b &{} d &{} a' &{} a \\ c &{} a &{} a &{} b \\ d &{} a' &{} b &{} c \end{array} \quad \quad {\hat{R}}'' = \begin{array}{c} {\hat{R}}''_{1} \\ \hline a_{1} \\ a_{2} \\ a_{3} \\ \end{array} \quad \quad {\hat{R}}''' = \begin{array}{c} R'''_{1} \\ \hline a_{1} \\ a'_{1} \\ a''_{1} \\ a_{2} \\ a_{3} \\ \end{array} \end{aligned}$$By neutrality and anonymity, \(F(R)=\{a,b,c,d\}\). The preference profile \(R'\) is obtained from R by cloning a. Neutrality and anonymity imply \(F(R'\vert _{\{a,a'\}})=\{a,a'\}\). Thus, by composition-consistency with respect to clone winners, we have \(a,a' \in F(R')\). The score of \(a'\) at \(R'\) is \(s_{4;4}+s_{1;5}+s_{3;5}+s_{4;5}\). The score of d at \(R'\) is \(s_{1;5}+s_{3;5}+s_{4;5}+s_{5;5}\). Since \(a'\in F(R')\), it must be that \(s_{4;5} \ge s_{5;5}\), a contradiction. Thus, F cannot be unanimous.
A similar reasoning rules out the possibility that \(F(R)=\{a_{2}\}\). Then, F must be the trivial rule for 2 alternatives.
Finally, assume that F is the trivial rule for \(k \ge 2\) alternatives. We will show that F must be the trivial rule for \(k+1\) alternatives. Consider the following profiles.
$$\begin{aligned} {\tilde{R}} = \begin{array}{c} {\tilde{R}}_{1} \\ \hline a_{1} \\ \vdots \\ a_{k} \\ \end{array} \quad \quad {\tilde{R}}^{1}= \begin{array}{c} {\tilde{R}}'_{1} \\ \hline a_{1} \\ a'_{1} \\ \vdots \\ a_{k} \\ \end{array} \quad \quad {\tilde{R}}^{k} = \begin{array}{c} {\tilde{R}}'_{1} \\ \hline a_{1} \\ \vdots \\ a_{k} \\ a_{k+1} \end{array} \end{aligned}$$Since F is the trivial rule for k alternatives, we have \(F({\tilde{R}})=\{a_{1},a_{2},\ldots , a_{k}\}\). The preference profile \({\tilde{R}}^{1}\) is obtained from \({\tilde{R}}\) by cloning \(a_{1}\) once. By composition-consistency with respect to clone winners and the fact that F is the trivial rule for 2 alternatives, we have \(a'_{1} \in F({\tilde{R}}^{1})\). Then, we have \(a_2 \in F({\tilde{R}}^{k})\) since F is a scoring rule. A similar reasoning implies that \(a_{1}, a_{2}, \ldots , a_{k-1} \in F({\tilde{R}}^{k})\). Moreover, the preference profile \({\tilde{R}}^{k}\) is obtained from \({\tilde{R}}\) by cloning \(a_{k}\) once. Again, by composition-consistency with respect to clone winners and the fact that F is the trivial rule for 2 alternatives, we have \(a_{k}, a_{k+1} \in F({\tilde{R}}^{k})\), i.e., F is the trivial rule for \(k+1\) alternative.
Thus, we have proven that F is the trivial rule.
\(\square \)
Proposition 3. There exists no scoring rule that satisfies faithfulness and composition-consistency with respect to non-clone losers.
Proof
Suppose, seeking a contradiction, that F is a simple scoring rule that satisfies faithfulness and composition-consistency with respect to non-clone losers.
First, assume that \(m=3\). Assume, without loss of generality, that the score vector of F for three alternatives is \((s_{3;3},s_{2;3},s_{1;3})=(1,s,0)\). By faithfulness, we have \(s<1\). Take \(\alpha <1/2\). Consider the following profile.
That is, R is a preference profile where fraction \(\alpha /2\) of all voters have preference relation \(R_{1}\), fraction \(\alpha /2\) of all voters have preference relation \(R_{2}\) and so on. By faithfulness, we have \(F(R\vert _{\{a,b\}})=\{b\}\). By composition-consistency with respect to non-clone losers, we have \(a \not \in F(R)\). By neutrality, then, we have \(F(R)=\{b,b'\}\). The score of a at R is \(\alpha \), whereas the score of b at R is \(1/2s + (1-\alpha )/2\). The score of a must be less than that of b, i.e., we have \(\alpha < 1/2s + (1-\alpha )/2\), i.e., \(s>3\alpha -1\). Since \(\alpha \) can be arbitrarily close to 1/2, it follows that \(s \ge 1/2\).
Next, let \(m=4\). For \(\alpha <1/2\), consider the following preference profile.
Let \((s_{4;4},s_{3;4},s_{2;4},s_{1;4})=(1,{\hat{s}},t, 0)\) be the score vector of F for four alternatives. By faithfulness, we have \({\hat{s}}, t <1\). We know from the above that \(F \vert _{\{a,b,c\}}=\{b\}\). Hence, by composition-consistency with respect to non-clone losers, we have \(a,c \not \in F(R')\). By neutrality, then, we have \(F(R')=\{b,b'\}\). Thus, the total score of a at \(R'\) must be less than the total score of b at \(R'\), i.e., \(\alpha + t (1-\alpha ) < {\hat{s}}/2 + t\alpha /2 + (1-\alpha )/2\), i.e., \(3\alpha -1 +2t -3\alpha t < {\hat{s}}\). Since \(\alpha \) can be arbitrarily close to 1/2, it follows that \({\hat{s}} \ge 1/2(1+t)\). That is, it must be that \({\hat{s}} > t\).
Finally, let \(\beta < 1/3\), \(\epsilon >0\) and consider the preference profiles below.
By neutrality and anonymity, we have \(F({\hat{R}}^{2}\vert _{\{a,b,c\}})=\{a,b,c\}\). By faithfulness, we have \(F({\hat{R}}^{1}\vert _{\{a,b,c\}})=\{a\}\). Let \({\hat{R}}=({\hat{R}}^{1},{\hat{R}}^{2})\). By reinforcement, then, we have \(F({\hat{R}}\vert _{\{a,b,c\}})=\{a\}\). Thus, by composition-consistency with respect to non-clone losers, we have \(b \not \in F({\hat{R}})\). The total score of b at \({\hat{R}}\) is
whereas the total score of a is
Subtracting the total score of b from that of a yields
If \(\epsilon \) is chosen so that \(\epsilon < \beta ({\hat{s}} - t)/2(1-{\hat{s}})\), the total score of a is less than the total score of b.
The total score of c at \({\hat{R}}\) is
Subtracting the total score of b from that of c yields
which is negative when \(\beta \) is small enough.
Finally, the total score of \(c'\) at \({\hat{R}}\) is
which is less than the total score of b. Hence, \(b \in F({\hat{R}})\), a contradiction. \(\square \)
Lemma 2. If a scoring rule \(F=F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{1}\)satisfies monotonicity, then at least one of the following holds.
-
(i)
For each m in \({\mathbb {N}}\), each \(k, \ell \le m\)with \(k > \ell \), we have \(s^{1}_{k;m} > s^{1}_{\ell ;m}\).
-
(ii)
For each m in \({\mathbb {N}}\), each \(k, \ell \le m\)with \(k > \ell ,\)each \(\beta \)in \(\{1,2,\ldots , \alpha \}\), we have \(s^{\beta }_{k;m} \ge s^{\beta }_{\ell ;m}\).
Proof
Let \(F=F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{1}\) be a scoring rule that satisfies monotonicity. Let \(m \ge 2\). Let \(k, \ell \le m\) with \(k > \ell \). Consider the following profiles.
By neutrality and anonymity, we have \(F(R)=\{a_{1},a_{2},\ldots , a_{m}\}\). The preference profile \(R'\) is obtained from R by swapping \(a_{m-k+1}\) and \(a_{m-\ell +1}\), i.e., by an improvement of \(a_{m-\ell +1}\). Thus, by monotonicity, we must have \(a_{m-\ell +1} \in F(R')\). For each \(\beta \in \{1,2,\ldots , \alpha \}\), the total score of \(a_{m-\ell +1}\) at \(R'\) is
whereas the total score of \(a_{m-k+1}\) at \(R'\) is
The total score of any other alternative \(a_{t} \not \in \{a_{m-k+1}, a_{m-\ell +1}\}\) at \(R'\) is
Since \(a_{m-\ell +1} \in F(R')\), one of the following two must be correct:
-
(i)
\(s^{1}_{k;m} > s^{1}_{\ell ;m}\), i.e., \(F^{1}(R')=\{a_{m-\ell +1}\}\), i.e., \(F(R')=\{a_{m-\ell +1}\}\) or
-
(ii)
for each \(\beta \in \{1,2,\ldots , \alpha \}\)
$$\begin{aligned} s^{1}_{1;m}+\ldots +s^{1}_{k;m} + \ldots + s^{1}_{k;m} + \ldots s^{\beta }_{m;m} \ge s^{\beta }_{1;m}+\ldots +s^{\beta }_{\ell ;m} + \ldots + s^{\beta }_{\ell ;m} + \ldots s^{\beta }_{m;m}\text{, } \end{aligned}$$i.e., \(s^{\beta }_{k;m} \ge s^{\beta }_{\ell ;m}\).
\(\square \)
Theorem 1. Let F be a scoring rule.
-
(a)
F satisfies faithfulness, composition-consistency with respect to non-clone winners and monotonicity if and only if it is the Plurality rule.
-
(b)
F satisfies faithfulness, composition-consistency with respect to clone losers and monotonicity if and only if for each preference profile \(R_{N}(A) \in {\mathcal {R}},\)we have \(F(R) \subseteq P(R)\), where P is the Plurality rule.
Proof
-
(a)
It is straightforward to show that the Plurality rule satisfies the axioms. Thus, we prove the ‘only if’ part. Let F be a scoring rule that composition-consistency with respect to non-clone winners and monotonicity. Let \(F=F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{1}\) where for each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), \(F^{\beta }\) is a simple scoring rule.
Faithfulness implies that F is the Plurality rule for 2 alternatives. Assume that \(m \ge 3\). By Lemma 1, we know that, for each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), the score vector takes the form \(s^{\beta }_{m}=(x^{\beta }_{m},y^{\beta }_{m},\ldots ,y^{\beta }_{m},z^{\beta }_{m})\) with \(x^{\beta }_{m} \ge y^{\beta }_{m}\) and \(z^{\beta }_{m} \ge y^{\beta }_{m}\). That is, part (ii) of Lemma 2 must be true: for each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), \(x^{\beta }_{m} \ge y^{\beta }_{m} \ge z^{\beta }_{m}\). Combined with the fact that \(z^{\beta }_{m} \ge y^{\beta }_{m}\), this means that for each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), we have \(y^{\beta }_{m} = z^{\beta }_{m}\). By faithfulness, there exist a \(\beta \) in \(\{1,2,\ldots , \alpha \}\) such that \(x^{\beta }_{m} > y^{\beta }_{m}\) and \(x^{\gamma }_{m} = y^{\gamma }_{m}\) for each \(\gamma < \beta \). Thus, F must be the Plurality rule.
-
(b)
Let F be a scoring rule such that \(F(R) \subseteq P(R)\) for each R in \({\mathcal {R}}\). First note that the Plurality rule satisfies composition-consistency with respect to clone losers. Let R and \(R'\) be two preference profiles in \( {\mathcal {R}}\), where \(R'\) is obtained from R by cloning alternatives that are not chosen by F at R. We have \(P(R') = P(R)\). That is, \(F(R') \subseteq P(R') \subseteq P(R)\), i.e., F satisfies composition-consistency with respect to clone losers.
Next, let F be a social choice rule that satisfies the axioms. That is, by Theorem 1 in Young (1975), F is a scoring rule that satisfies faithfulness, composition-consistency with respect to non-clone winners and monotonicity. Faithfulness implies that F is the Plurality rule for 2 alternatives. Assume \(m\ge 3\). We know by Lemma 1 that, for each \(m \ge 3\), we have \(s^{1}_{1;m} \ge s^{1}_{m-1;m}\). That is, option (ii) in Lemma 2 must be true: for each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), we have \(x^{\beta }_{m} \ge y^{\beta }_{m} \ge z^{\beta }_{m}\). Thus, we must have \(s^{1}_{1;m} = s^{1}_{2;m}=\ldots = s^{1}_{m-1;m}\). By faithfulness, we have \(s^{1}_{m;m} \ge s^{1}_{m-1;m}\). That is, \(F^{1}\) is either the trivial rule or the Plurality rule. If it is the Plurality rule, then we are done.
Assume instead that \(F^{1}\) is the trivial rule. But then F is equivalent to \(F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{2}\). The same proof then implies that \(F^{2}\) is either the trivial rule or the Plurality rule. If \(F^{2}\) is also the trivial rule, then F is equivalent to \(F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{3}\). Since F is faithful, there must be a \(\beta \) in \(\{1,2,\ldots , \alpha \}\) such that \(F^{\beta }\) is the Plurality rule and \(F^{\gamma }\) is the trival rule for each \(\gamma <\beta \). Thus, we have \(F(R) \subseteq P(R)\).
\(\square \)
Theorem 2. A scoring rule satisfies faithfulness, composition-consistency with respect to non-clone winners and composition-consistency with respect to dominant clone winners if and only if it is the Plurality rule.
Proof
It is straightforward to verify that the Plurality rule satisfies the axioms. Conversely, let F be scoring rule that satisfies faithfulness, composition-consistency with respect to non-clone winners and composition-consistency with respect to dominant clone winners.
By Lemma 1, we know that \(F=F^{\alpha } \circ F^{\alpha -1} \circ \cdots \circ F^{1}\) such that for each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), each m in \({\mathbb {N}}\), we have \(s^{\beta }_{m}=(x^{\beta }_{m},y^{\beta }_{m},\ldots ,y^{\beta }_{m},z^{\beta }_{m})\) with \(x^{\beta }_{m} \ge y^{\beta }_{m}\) and \(z^{\beta }_{m} \ge y^{\beta }_{m}\).
Faithfulness implies that F coincides the Plurality rule for \(m=2\).
Assume that \(m \ge 2\). Consider the following profiles.
For each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), the total score of \(a_{1}\) and \(a_{m}\) at R is \(x^{\beta }_{m} + z^{\beta }_{m}\). Every other alternative has a total score of \(2y^{\beta }\). We have \(a_{1}, a_{m} \in F(R)\) since \(x^{\beta }_{m} \ge y^{\beta }_{m}\) and \(z^{\beta }_{m} \ge y^{\beta }_{m}\). The preference profile \(R'\) is obtained from R by cloning \(a_{m}\) once. Moreover, \(a_{m}\) Pareto dominates its clone \(a'_{m}\) at \(R'\). Thus, by composition-consistency with respect to dominant clone winners, we must have \(a_{m} \in F(R')\). By composition-consistency with respect to non-clone winners, on the other hand, we must have \(a_{1} \in F(R')\). That is, the total scores of \(a_{1}\) and \(a_{m}\) at \(R'\) must be the same.
For each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), the total score of \(a_{m}\) at \(R'\) is \(x^{\beta }_{m+1} + y^{\beta }_{m+1}\). The total score of \(a_{1}\) at \(R'\) is \(x^{\beta }_{m+1} + z^{\beta }_{m+1}\). So, we have, \(y^{\beta }_{m+1}=z^{\beta }_{m+1}\). Thus, we have shown that, for each \(m \ge 3\), each \(\beta \) in \(\{1,2,\ldots , \alpha \}\), we have \(s^{\beta }_{m}=(x^{\beta }_{m},y^{\beta }_{m},\ldots ,y^{\beta }_{m},y^{\beta }_{m})\). By faithfulness, there exists a \(\beta \) in \(\{1,2,\ldots , \alpha \}\) such that \(x^{\beta }_{m} > y^{\beta }_{m}\) with \(x^{\gamma }_{m} = y^{\gamma }_{m}\) for each \(\gamma < \beta \). That is, F is the Plurality rule. \(\square \)
Rights and permissions
Open Access This 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/.
About this article
Cite this article
Öztürk, Z.E. Consistency of scoring rules: a reinvestigation of composition-consistency. Int J Game Theory 49, 801–831 (2020). https://doi.org/10.1007/s00182-020-00711-7
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-020-00711-7