Approval voting and Shapley ranking

Abstract

Approval voting allows electors to list any number of candidates and their final scores are obtained by summing the votes cast in their favor. Equal-and-even cumulative voting instead follows the One-person-one-vote principle by endowing each elector with a single vote that may be distributed evenly among several candidates. It corresponds to satisfaction approval voting, introduced by Brams and Kilgour (in: Fara et al (eds) Voting power and procedures. Essays in honor of Dan Fesenthal and Moshé Machover, Springer, Heidelberg, 2014) as an extension of approval voting to a multiwinner election. It also corresponds to the concept of Shapley ranking, introduced by Ginsburgh and Zang (J Wine Econ 7:169–180, 2012) as the Shapley value of a cooperative game with transferable utility. In the present paper, we provide an axiomatic foundation for Shapley ranking and analyze the properties of the resulting social welfare function.

Which candidate ought to be elected in a single-member constituency if all we take into account is the order in which each of the electors ranks the candidates?… At the very outset of the argument, we try to move from the is to the ought and to jump the unbridgeable chasm between the universe of science and that of morals. (Black 1958, p. 55)

1 Introduction

Approval voting is a method that was studied formally in the 1970 s by Weber (1977) and Brams and Fishburn (1978).¹ Given a set of candidates, electors have the possibility of listing any number of candidates whom they consider to be “good for the job.” The method simply consists in assigning to each candidate a score equal to the number of electors who have listed that candidate.² The winners are those with the largest scores. Beyond being a voting method, rational collective preferences are derived from approval voting as in Borda’s (1781) method of marks and other scoring methods.

Approval voting has its supporters, starting with Brams and Fishburn, but also its opponents, i.e., Saari and van Newenhizen (1988).³ Approval voting not been implemented very often, except in some scientific societies such as the American Mathematical Society or the Institute of Electrical and Electronics Engineers. A few other exceptions exist, such as the election of the UN Secretary General.⁴ Several experiments have been conducted, in particular by Baujard and Igersheim (2010) following the 2002 and 2007 French presidential elections.

In what follows, we make a distinction between voting, ranking and ordering. Voting is the procedure by which electors submit ballots. Ranking aggregates the electors’ choices by assigning a score to each candidate.⁵ And a ranking leads to an ordering, which is the ordinal relation on the set of candidates induced by the ranking.

Under approval voting, the number of candidates an elector is allowed to list is not limited a priori and listing additional candidates imposes no direct “cost” on electors. If an elector adds a candidate to her ballot, it has no impact on the scores of the other candidates. Furthermore, electors who list several candidates carry more weight. In that sense, approval voting violates the One-person-one-vote principle often emphasized by the advocates of political equality. That principle is satisfied by equal-and-even cumulative voting (also called block approval voting) whereby an elector’s vote is divided evenly among the candidates she lists. For instance, if an elector lists three candidates, each gets 1/3 of a vote instead of 1. Hence, an elector’s vote weights less the larger the number of candidates on her ballot and electors have an incentive to limit the sizes of their ballots: Adding a candidate reduces the chances that those already present will be elected. If the objective of an elector is to see elected one of the candidates that she places high in her preferences, she will tend to submit a limited number of candidates among which she is comparatively indifferent. Cumulative voting typically is used in multiwinner elections when electors can spread a fixed number of votes—usually equal to the number of seats to be filled—over one or more candidates.⁶

Electors are assumed to have preferences over candidates. More precisely, we assume that each elector orders the candidates from the most preferred to the least preferred and draws a line somewhere to partition the set of candidates into two sublists, as if her preferences were dichotomous. A ballot reveals that that the candidates above the line are strictly preferred to those below it. Hence, two electors who order the candidates identically may well draw the line at different places. If an elector’s preferences are incomplete, the candidates whom she cannot order would just not appear on her ballot.⁷ However, even if approval voting is compatible with incomplete preferences, we maintain the assumption of completeness. Furthermore, we leave open the possibility of dichotomous preferences whereby electors are indifferent within and outside their ballots. Under the assumption of dichotomous preferences, Mongin and Maniquet (2015) prove that approval voting induces a non-dictatorial social welfare function that satisfies the Pareto criterion and independence of irrelevant alternatives (IIA). That result does not contradict Arrow’s impossibility theorem because assuming dichotomous preferences definitely restricts the domain of individual preferences.⁸

The assumption of dichotomous preferences is, however, far too strong. The candidates listed by an elector are in some sense relatively “close” to each other, but assuming indifference within and outside ballots is not plausible. That assumption is even less plausible for the candidates that an elector does not list. In the present paper, we assume only that electors strictly prefer the candidates they list to those they do not list, an assumption that is an integral part of the definition of a ballot. Notice that, under dichotomous preferences, approval voting is equivalent to Borda’s method (1781), which, for each elector, allocates 1 to the candidates listed in her ballot and 0 to the others. The absence of information on electors’ preferences is a fundamental difficulty when electors are asked to name candidates without ordering them. It is so for approval voting as well as for any other method that limits the number of candidates an elector can list, including plurality voting.

Equal-and-even cumulative voting corresponds to the concept of Shapley ranking, defined by Ginsburgh and Zang (2012) as the Shapley value of a transferable utility game derived from approval ballots. It also corresponds to the concept of satisfaction approval voting introduced by Brams and Kilgour (2014). Even if those scholars limit that aggregation method to multiwinner elections, nothing actually prevents applying it to single-winner elections. In the present paper, we provide an axiomatic foundation for equal-and-even cumulative voting based on the one-person-one-vote principle. We then move from ranking to ordering and look at the properties of the induced social welfare function.

The paper is organized as follows. Approval and equal-and-even cumulative voting are introduced in Sect. 1 using the concept of a ballot profile that specifies, for each subset of candidates, the number of electors who support it. Ranking games associated with ballot profiles are introduced in Sect. 2. Their Shapley values are shown to coincide with the ranking derived from equal-and-even cumulative voting. The resulting “Shapley ranking” is then axiomatized in terms of ballot profiles by reference to Shapley’s axioms wherein efficiency is translated into the one-man-one-vote principle. Section 3 looks at the properties of the orderings derived from approval and Shapley rankings, in a social choice perspective. The last section is devoted to concluding remarks.

2 Approval, fractional, plurality and majority voting

Consider a set $N$ of n candidates with $n \ge 2.$⁹ There can be any number of electors. Electors have preferences over candidates: $i \succ_{h} j$ reads elector h prefers candidate i to candidate${j}$ and $i \sim_{h} j$ reads elector h is indifferent between candidates i and${j}$. The weak preference relation $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{ \succ }_{h}$ represents the preferences of elector h. Preferences are assumed to be rational: $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{ \succ }_{h}$ is a complete, transitive and reflexive binary relation (a complete preorder) over N. A preference profile specifies a preference ordering for each elector.

2.1 Approval voting

Under approval voting, electors are asked to list the candidates of whom they approve. We denote by $N_{h} \subset N$ the approval set or ballot of elector h, which is the set of candidates submitted by h. We assume that $N_{h} \ne \emptyset$ for all h, but do not exclude $N_{h} = N.$ The choice of elector h can be identified as an n-tuple $q_{h} \in \{ 0,1\}^{n}$ with $q_{ih} = 1$ if and only if $i \in N_{h} .$ If M denotes the set of electors, a ballot profile can be arranged in a $n \times m$ matrix whose rows are attributed to candidates and columns to electors. Alternatively, a ballot profile can be written as a mapping $\pi$ that associates to each (nonempty) subset $S \subset N$ of candidates (there are $2^{n} - 1$ such subsets), the number of electors whose approval set coincides with that subset: $\pi (S) = \left| {\{ h \in M\left| {\,N_{h} = S\,} \right.\} } \right|.$ A one-to-one relation exists between ballot profiles and the matrix representation, knowing that the number of electors is obtained by summing the $\pi (S).$ The set of admissible ballot profiles on a set N of candidates is given by

$$ \varPi (N) = \left\{ {\pi \in {\mathbb{N}}^{{2^{n} - 1}} /0\,\left| {\;\pi (S) \le n\;\;{\text{for}}\;{\text{all}}\;S \subset N,\;S \ne \emptyset \,} \right.} \right\}, $$

where ${\mathbb{N}}$ = {0, 1, 2,…} denotes the set of nonnegative integers. Notice that the profile (0, 0,…, 0) is excluded because electors are assumed to submit nonempty ballots.

Example 1

Consider the four-candidate situation described by the following ballot profile: $\pi (1) = \pi (1,2) = \pi (2,3) = \pi (2,3,4) = 1,\;\pi (3,4) = 2,$ and $\pi (S) = 0$ for all other subset S.¹⁰ Hence, we have six electors and their ballots are $N_{1} = \{ 1\} ,\;$$N_{2} = \{ 1,2\} ,$$N_{3} = \{ 2,3\} ,$$N_{4} = N_{5} = \{ 3,4\}$ and $N_{6} = \{ 2,3,4\} .$ The associated matrix is given by

The approval score of candidate i is the number of electors who have listed that candidate

$$ AR_{i} (N,\pi ) = \sum\limits_{S:\;i \in S} {\pi (S)} \quad \left( {i = \, 1, \, \ldots , n} \right). $$

(1)

It is obtained by summing along each row of the representative matrix Q. In Example 1, the approval scores are given by (2, 3, 4, 3). It leads to the following ordering: $3 \succ 2 \sim 4 \succ 1.$

2.2 Equal-and-even cumulative voting

Under equal-and-even cumulative voting, each of the candidates listed by elector h receives a fraction $1/n_{h}$, where $n_{h}$ is the size of elector h’s ballot. The scores are obtained by summing the fractions allocated to each candidate

$$ SR_{i} (N,\pi ) = \sum\limits_{S:\;i \in S} {\frac{1}{s}\,\pi (S)} \quad \left( {i = \, 1, \ldots ,n} \right). $$

(2)

Equation (2) coincides with the concept of Shapley ranking introduced by Ginsburgh and Zang (2012) and with the concept of satisfaction approval voting introduced by Brams and Kilgour (2014).

Table 1 shows the scores obtained in Example 1. The ordering resulting from Shapley ranking is $3 \succ 1 \succ 2 \succ 4.$ It places candidate 1 on top. Not surprisingly, it differs from the ordering $3 \succ 2 \sim 4 \succ 1$ that results from approval ranking. Both orderings obviously coincide in the case of two candidates. Example 1 shows that they may not coincide beyond two candidates. The following example illustrates a situation wherein the two orderings do coincide.

Table 1 AR and NR scores in Example 1

Example 2

Consider a situation with three candidates and five electors whose approval sets are $N_{1} = \{ 1\} ,\;N_{2} = \{ 1,2\} ,\;N_{3} = \{ 2,3\} ,\;N_{4} = \{ 1,3\} \;{\text{and}}\;N_{5} = \{ 1,2,3\} .$ The scores are given in Table 2. In both cases, candidate 1 comes in first, while the other two obtain the same score: $1 \succ 2 \sim 3.$

Table 2 AR and NR scores in Example 2

Notice that by normalizing the scores given by (2), we obtain the probabilities that a particular candidate is elected under the random dictatorship procedure.¹¹ Each of the m electors is asked to identify a subset of candidates, knowing that an elector will first be chosen at random and that the winner will be chosen at random in her approval set. The resulting probabilities are then proportional to the scores

$$ {\text{Prob}}\,[i\;{\text{is}}\;{\text{elected}}] = \frac{1}{m}\;\sum\limits_{{h:\;i \in N_{h} }} {\frac{1}{{n_{h} }}} = \frac{1}{m}\;SR_{i} (N,\pi ). $$

In Example 1 (see Table 1), the probabilities are given by (0.25, 0.22, 0.30, 0.22). In Example 2 (see Table 2), they are given by (0.47, 0.27, 0.27).

2.3 Plurality and majority voting

A number of voting rules in which electors are allowed to submit only one candidate are special cases of approval voting. Those are the cases of plurality and majority voting. The two methods are well defined only in the absence of indifference in individual preferences. Each elector has then a unique most preferred candidate and candidates are ordered according to their approval scores given by (1) or, equivalently, by (2). In plurality voting, the winners are the candidates with the largest approval score. In majority voting, the winner is the candidate with an approval score exceeding half the number of electors. The latter therefore is not a decisive method. The following example shows that a candidate who appears first in a majority of electors’ preferences may be defeated under approval voting and equal-and-even cumulative voting. It illustrates how voting by approval reveals some information on electors’ intensities of preferences.

Example 3

Consider a situation with four candidates and five electors whose preferences are given by $1 \succ_{1} 3 \succ_{1} 2 \succ_{1} 4,\;\;1\, \succ_{2} 2 \succ_{2} 3 \succ_{2} 4,\;\;1 \succ_{3} 2 \succ_{3} 4 \succ_{3} 3,\;\;2 \succ_{4} 3 \succ_{4} 4 \succ_{4} 1$ and $2 \succ_{5} 4 \succ_{5} 1 \succ_{5} 3.$ The first candidate has a majority: he comes on top of 3 out of 5 orderings.¹² Now assume that the electors submit the following ballots: $N_{1} = \{ 1,3\} ,$$N_{2} = \{ 1,2\} ,\;N_{3} = \{ 1,2,4\} ,\;N_{4} = \{ 2,3\}$ and $N_{5} = \{ 2,4\} .$ Table 3 shows the resulting scores. Candidate 2 gets the largest score in both cases.

Table 3 AR and NR scores in Example 3

When some electors are indifferent between candidates, plurality and majority voting are not well defined because some electors may have several most preferred candidates. If that is the case for an elector, she has to make a selection and we could assume that the candidate that she submits is drawn at random from among her top candidates. Denoting by $N_{h}$ the subset of most preferred candidates of elector h, each one is assigned a probability equal to $1/n_{h}$ and the score of a candidate is then given by the sum of the probabilities that his name be submitted. In that case, plurality voting and equal-and-even cumulative voting give rise to the same result.

3 Shapley ranking

3.1 Ranking games

We first recall the definition of a ranking games introduced by Ginsburgh and Zang (2012). In our voting context, the players are the candidates. Given a ballot profile $(N,\pi ),$ we define the transferable utility game$(N,w)$ whose characteristic function associates with each subset S of candidates, the number of electors whose approval set is included in S

$$ w(S) = \sum\limits_{T \subset S} {\pi (T)} \;\;{\text{for}}\;{\text{all}}\;S \subset N. $$

(3)

The term $w(S)$ is the number of electors who are exclusively supporting some candidates in S. In particular, $w(i)$ is the number of electors who have listed only candidate i and $w(N)$ is the total number of electors. A ranking game’s solution provides a ranking of candidates by specifying for each of them a score equal to a fraction of the total number of electors. The characteristic function associated to Example 1 is given by

$$ \begin{aligned} & w(1) = 1,\;w(2) = 0,\;w(3) = 0,\;w(4) = 0, \\ & w(1,2) = 2,\;w(1,3) = 1,\;w(1,4) = 1,\;w(2,3) = 1,\;w(2,4) = 0,\;w(3,4) = 1, \\ & w(1,2,3) = 3,\;w(1,2,4) = 2,\;w(1,3,4) = 2,\;w(2,3,4) = 3, \\ & w(1,2,3,4) = 5. \\ \end{aligned} $$

We denote by G(N) the set of all characteristic functions on a given set of N players. It can be identified to the vector space ${\mathbb{R}}^{{2^{n} - 1}} .$ In proving the uniqueness of his value, Shapley (1953) shows that the $2^{n} - 1$unanimity games defined for all $T \subset N$ by

$$ u_{T} (S) = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if}}\;T \subset S} \hfill \\ 0 \hfill & {{\text{otherwise}}.} \hfill \\ \end{array} } \right. $$

form a basis of the vector space G(N): For any characteristic function v, there exists a unique collection $(\alpha_{T} \left| {\,T \subset N,\,T \ne \emptyset )} \right.$ of $2^{n} - 1$ real numbers such that

$$ v(S) = \sum\limits_{T \subset N} {\alpha_{T} (N,v)\,u_{T} (S)} = \sum\limits_{T \subset S} {\alpha_{T} (N,v)} \;\;{\text{for}}\;{\text{all}}\;S \subset N. $$

(4)

The coefficients $\alpha_{T}$ are known as the Harsanyi dividends (dividends for short) (see Harsanyi 1959). The following proposition follows immediately from (3) and (4).

Proposition 1

The dividends of the ranking game $(N,w)$ associated with the ballot profile $(N,\pi )$ coincide with the ballot profile: $\alpha_{S} (N,w) = \pi (S)\;\;{\text{for}}\;{\text{all}}\;S \subset N.$

Hence, because (4) is invertible, a one-to-one relation exists between a ranking game and its ballot profile. The subset $RG(N) \subset G(N)$ of all ranking games on a set N generated by the set of ballot profiles $\varPi (N)$ forms a remarkable class of games. The characteristic functions defining ranking games are monotonic (increasing), convex (thereby superadditive) and take values in ${\mathbb{N}}$. They are positive in the sense that their dividends all are non-negative.¹³ Furthermore, the set $RG(N)$ is closed under addition: starting from any two ballot profiles $(N,\pi^{\prime})$ and $(N,\pi^{\prime \prime } )$ on a common set of candidates, and their associated ranking games $(N,v^{\prime})$ and $(N,v^{\prime \prime } ),$ the ranking game $(N,v^{\prime} + v^{\prime\prime})$ is associated with the ballot profile $(N,\pi^{\prime} + \pi^{\prime\prime}).$¹⁴

3.2 The Shapley value of a ranking game

Ginsburgh and Zang (2012) prove that the Shapley value of a ranking game coincides with equal-and-even cumulative voting as defined by (2); hence, the term “Shapley ranking”.

Proposition 2

The Shapley ranking associated with a ballot profile $(N,\pi )$ is the Shapley value of the associated ranking games $(N,w):$ $SR_{i} (N,\pi ) = SV_{i} (N,w),\;\;i = 1, \ldots ,n.$

Proof

Following Harsanyi (1959), the Shapley value of a game $(N,v)$ is given by the uniform distribution of its dividends

$$ SV_{i} (N,v) = \sum\limits_{T:\;i \in T} {\frac{1}{t}} \;\alpha_{T} (N,v)\quad \left( {i = 1, \ldots ,n} \right). $$

The identity then follows from Proposition 1.□

3.3 Axiomatization of Shapley ranking

For a given set N, we denote by P(N) the set of permutations of N. For a given subset $S \subset N,$pS denotes the image of S under the permutation $p \in P(N).$ For a given set function v on N, the function pv is defined by $pv(pS) = v(S)\;{\text{for}}\;{\text{all}}\;S \subset N.$ The following axioms are the translations of Shapley’s axioms in terms of ballot profiles. They apply to the ranking rules $\varphi :\varPi (N) \to {\mathbb{R}}^{n}$ defined on the set of ballot profiles.

One-person-one-vote (Efficiency) The scores add-up to the number of electors:

$$ \sum\limits_{i \in N} {\varphi_{i} (N,\pi ) = } \sum\limits_{S \subset N} {\pi (S)} . $$

Neutrality :

(Anonymity) If candidates’ names are permuted, scores are permuted accordingly:

$$ {\text{For}}\;{\text{all}}\;p \in P(N)\;{\text{and}}\;i \in N,\;\;\varphi_{pi} (N,p\pi) = \varphi_{i} (N,\pi). $$

Null candidate :

(Null player) Candidates appearing on no ballot get a zero score:

$$ \pi (S) = 0\;{\text{for}}\;{\text{all}}\;S \subset N\;{\text{such}}\;{\text{that}}\;i \in S\;\; \Rightarrow \;\;\varphi_{i} (N,\pi ) = 0. $$

Additivity :

The score associated with a sum of ballot profiles on a common set of candidates is equal the sum of the scores associated with each ballot profile: For any two ballot profiles $\pi^{\prime}\;{\text{and}}\;\pi^{\prime \prime }$ on N, $\varphi (N,\pi^{\prime} + \pi^{\prime \prime } ) = \varphi (N,\pi^{\prime}) + \varphi (N,\pi^{\prime \prime } ).$

Additivity makes sense here because the set $\varPi (N)$ of all possible ballot profiles is closed under addition. The four axioms are natural requirements and characterize Shapley ranking.

Proposition 3

Shapley ranking is the unique ranking rule defined on $\varPi (N)$ that satisfies One-person-one-vote, Neutrality, Null candidate and Additivity.

Proof

Shapley ranking obviously satisfies the four axioms. Now, consider a ranking rule φ satisfying all four axioms. Any ballot profile π on N can be decomposed as a sum of elementary ballot profiles $\pi = \sum\nolimits_{T \subset N} {\pi_{T} }$, where

$$ \begin{aligned} \pi_{T} (S) & = \pi (T)\quad {\text{if}}\;S = T, \\ & = 0\quad \quad \,\,\,\,{\text{if}}\;S \ne T. \\ \end{aligned} $$

By the Null candidate axiom, we have:

$$ \varphi (N,\pi_{T} ) = 0\;\;{\text{for}}\;{\text{all}}\;i \notin T. $$

Combining the One-person-one-vote and the Neutrality axioms, we have

$$ \varphi (N,\pi_{T} ) = \frac{\pi (T)}{t}\;\;{\text{for}}\;{\text{all}}\;i \in T. $$

We then obtain (3) by using Additivity. □

It is easily seen that approval ranking obtains by replacing the One-person-one-vote axiom by an axiom specifying that the scores add-up to the number of votes (One-person-many-votes).

4 From ranking to ordering

Approval and Shapley orderings are derived from approval and Shapley rankings. They generally differ, as shown in Example 1. They coincide in the two extreme voting situations when either $n_{h} = 1$ for all h or $n_{h} = n$ for all h. In the first situation, analogous to plurality voting, $AR_{i} = SR_{i}$ for all i. In the second situation, $AR_{i} = m$ and $SR_{i} = m/n$ for all i, where m is the number of electors.

Referring to the underlying individual preferences, approval and Shapley orderings are two social welfare functions that assign collective preferences to individual preferences. What are their properties and how do they compare with one another? Not surprisingly, we will see that little can be said outside the case of dichotomous preferences.

4.1 Individual preferences

Consider the following three possible assumptions on individual preferences.

A1:

$i \in N_{h} \;\;{\text{and}}\;\;j\not \in N_{h}$ implies $i \succ_{h} j.$

A2:

$i,j \in N_{h}$ implies $i \sim_{h} j.$

A3:

$i,j \in N\backslash N_{h}$ implies $i \sim_{h} j.$

A1 is part of the definition of approval voting. The other two assumptions are less natural and far too restrictive, especially A3. The three assumptions together characterize dichotomous preferences.

4.2 From individual to collective preferences

The validity of four properties will be considered, Pareto, Independence of irrelevant alternatives, Condorcet and Monotonicity, on the basis of the approval sets $(N_{1} , \ldots ,N_{m} )$ submitted by electors.

The Pareto principle requires that unanimity be reflected in collective preferences. Here is a formulation that allows electors to be indifferent between candidates.

Pareto principle:

If candidate i is preferred to candidate j by all electors, then j cannot be collectively preferred to i

Under dichotomous preferences, candidate i is preferred to candidate j by all electors if and only if $i \in N_{h} \;{\text{and}}\;j\not \in N_{h} \;$ for all $h \in M.$ Clearly, approval and Shapley ranking both satisfy the Pareto principle under dichotomous preferences. It remains true assuming only A1.

Proposition 4

Under assumption A1, both approval and Shapley orderings satisfy the Pareto principle.

Proof

Consider two candidates i and j such that $i \succ_{h} j$ for all $h \in M.$ For each elector h, three cases define a partition in three subsets of the set of electors.

• (a) $i \in N_{h} \;{\text{and}}\;j \notin N_{h} \;\; \to \;\;h \in M_{1} ,$

• (b) $i,j \in N_{h} \;\; \to \;\;h \in M_{2} ,$

• (c) $i,j \notin N_{h} \;\; \to \;\;h \in M\backslash (M_{1} \cup M_{2} ).$

The difference in approval scores is then equal to $m_{1} \ge 0.$ Nothing excludes a situation wherein M₁ is empty. The difference in Shapley scores is non-negative as well. Indeed, referring to the representative matrix Q that describes electors’ ballots, we have

$$ SR_{i} - SR_{j} = \sum\limits_{{h \in M_{1} }} {\frac{{q_{hi} }}{{b_{h} }}} , $$

where $b_{h} = \sum\limits_{l \in N} {q_{hl} } > 0\;\;{\text{for}}\;{\text{all}}\;h \in M$ by assumption. □

The axiom of independence of irrelevant alternatives (IIA for short) was introduced by Arrow (1951). It may be considered as a natural requirement, although it generally is not satisfied in the absence of restrictions on individual preferences. Consider two preference profiles with a common set of electors, on a common set of candidates, and two candidates i and j.

IIA:

If electors have the same preferences regarding i and j in both profiles, the collective preferences regarding i and j derived from the two profiles must be identical

Arrow’s impossibility theorem states that, without restrictions on preferences (axiom of Unrestricted domain), dictatorship is the only social welfare function that satisfies the Pareto principle and IIA. It is easy to show that, under dichotomous preferences, approval voting satisfies IIA.¹⁵ Indeed, consider two ballot profiles $(N^{\prime}_{1} , \ldots ,N^{\prime}_{m} )$ and $(N_{1}^{\prime \prime } , \ldots ,N_{m}^{\prime \prime } ),$ along with the associated representative matrices $Q^{\prime }$ and $Q^{\prime \prime }$. If electors have the same preferences regarding i and j, the rows i and j of the matrices $Q^{\prime }$ and $Q^{\prime \prime }$ are identical and therefore $AR^{\prime}_{i} = AR_{i}^{\prime \prime }$ and $AR^{\prime}_{j} = AR_{j}^{\prime \prime } .$ Shapley ranking does not satisfy IIA, whether preferences are dichotomous or not, because of the strong interdependence that characterizes it. That is confirmed by the following example.

Example 4

Consider two ballot profiles on a set of three candidates and five electors, represented by the matrices $Q^{\prime }$ and $Q^{\prime \prime }$. Assume that the electors have the same preferences regarding both candidates.

In $Q^{\prime }$ candidate 2 has a higher Shapley score than candidate 1. The order is reversed in $Q^{\prime \prime }$.

The Condorcet principle often is considered to be a voting property. A candidate is a Condorcet winner if he never loses in duels (Condorcet 1785). No Condorcet winner may emerge, but if such a candidate exists, one could argue that he should be elected.

Condorcet principle:

The set of Condorcet winners, if non-empty, should be on top of the collective preferences.

Few aggregation methods satisfy that principle. If individual preferences were known (like in Borda’s count), one could first check whether a Condorcet winner exists and eventually elect him. If preferences are assumed to be dichotomous, the result of a duel between two candidates depends only on their approval scores. Hence, a candidate is a Condorcet winner if he has the highest approval score.¹⁶ Shapley ranking does not satisfy the Condorcet principle, as shown in Example 1 wherein candidates 2 and 3 are Condorcet winners but neither is elected under Shapley ranking. Example 3 confirms that, outside dichotomous preferences, approval and Shapley rankings both fail to satisfy the Condorcet principle. However, both rankings are exempt from cycles.¹⁷

What happens to collective preferences when the preferences of a single elector change? Answering that question is the object of the following axiom.

Monotonicity:

Consider a preference profile such that candidate i is collectively preferred to j. If an elector who prefers j to i changes his mind in favor of candidate i, candidate i must remain collectively preferred to candidate j.

Proposition 5

Under assumption A1, both approval ordering and Shapley ordering satisfy Monotonicity.

Proof

Assume that $i \succ j$ while $j \succ_{k} i$ for some $k \in M.$ There are three possible cases.

• (a) $j \in N_{k} \;{\text{and}}\;i \notin N_{k} ,$

• (b) $i,j \in N_{k} ,$

• (c) $i,j \notin N_{k} .$

Assume that elector k changes his mind and now prefers i to j. We denote by $N^{\prime}_{k}$ his modified approval set. In (a), we have three possible cases.

• (a1) $N^{\prime}_{k} = N_{k} \backslash j,$

• (a2) $N^{\prime}_{k} = N_{k} \cup i,$

• (a3) $N^{\prime}_{k} = (N_{k} \cup i)\backslash j.$

In (b), two cases are possible.

• (b1) $N^{\prime}_{k} = N_{k} \backslash j,$

• (b2) $N^{\prime}_{k} = N_{k} .$

In (c), two cases also are possible.

• (c1) $N^{\prime}_{k} = N_{k} \cup i,$

• (c2) $N^{\prime}_{k} = N_{k} .$

Consider, first, approval voting. Initially, we have AR_i > AR_j. In cases (b2) and (c2), AR_i and AR_j remain unchanged. In cases (a1) and (b1), AR_i is unaffected while AR_j decreases by 1. In cases (a2) and (c1), AR_j is unaffected while AR_i increases by 1. In case (a3), AR_i increases by 1 and AR_j decreases by 1. Hence, $AR^{\prime}_{i} > AR^{\prime}_{j} .$ Consider now Shapley ranking. Initially, we have SR_i > SR_j. In cases (b2) and (c2), SR_i and SR_j remain unchanged. In cases (a1), SR_i is unaffected while SR_j decreases by $1/n_{k} .$ In case (a2), SR_j decreases by $1/n_{k} (1 + n_{k} )$ while SR_i increases by $1/(1 + n_{k} ).$ In case (b1), SR_j decreases by $1/n_{k}$ while SR_i increases by $1/n_{k} (n_{k} - 1).$ In case (c1), SR_j is unaffected while SR_i increases by $1/(1 + n_{k} ).$ In case (a3), SR_i increases by $1/n_{k}$ and SR_j decreases by $1/n_{k} .$ Hence, $SR^{\prime}_{i} > SR^{\prime}_{j} .$□

5 Concluding remarks

Approval voting has its advantages and drawbacks like any other preference aggregation method, although most of its advantages cannot be formalized. The same conclusion applies to equal-and-even cumulative voting. However, equal-and-even cumulative voting may be preferable to approval voting because under the former, electors have an incentive to limit the number of candidates they decide to retain. Furthermore, if an elector lists several candidates, it is likely that the candidates retained will be “close” to each other in terms of preferences, in which assuming that electors are indifferent between the candidates listed in their ballots becomes more plausible. It would be interesting to conduct experiments within approval balloting in order to evaluate the effect of fractional votes.