On two voting systems that combine approval and preferences: fallback voting and preference approval voting

Abstract

Preference approval voting (PAV) and fallback voting (FV) are two voting rules that combine approval and preferences, first introduced by Brams and Sanver (in: Brams, Gehrlein and Roberts (eds) The mathematics of preference, choice and order, Springer, Berlin, 2009). Under PAV, voters rank the candidates and indicate which ones they approve of; with FV, they rank only those candidates they approve of. In this paper, we further develop the work of Brams and Sanver (2009) by exploring some other normative properties of FV and PAV. We show among other things that FV and PAV satisfy and fail the same criteria; they possess two properties that AV does not: Pareto optimality and the fact of always electing the absolute Condorcet winner when he exists. To provide a practical comparison, we evaluate the probabilities of satisfying the Condorcet majority criteria for three-candidate elections and a considerably large electorate, examining FV and PAV alongside other voting rules. Our findings indicate that PAV outperforms the Borda rule in this regard. Furthermore, we observe that in terms of agreement, FV and PAV align more closely with scoring rules than with approval voting. Our analysis is performed under the impartial anonymous culture assumption.

1 Introduction

When it comes to single-winner elections, the literature and practical applications primarily revolve around two major categories of voting rules. These can be broadly classified as scoring rules based on rankings and rules based on evaluation or approval. Scoring rules (SCR) typically require voters to rank the candidates, either all of them or a subset. Based on these rankings, candidates receive points according to their positions. The candidate with the highest total score, as determined by the rule in question, is declared the winner. Among the most well-known SCR are the plurality rule (PR), the negative plurality rule (NPR), and the Borda rule (BR).¹ Approval voting (AV), popularized by Brams and Fishburn (1978), has gained significant popularity: this rule simplifies the voting process by allowing voters to express their approval for the candidates they find acceptable. Under AV, each voter has the freedom to approve as many candidates as they desire. The candidate(s) who receive the highest number of approvals are declared the winner(s). AV has garnered attention as a viable alternative to SCR in various contexts; its simplicity and intuitive nature have contributed to its appeal among both scholars and practitioners. As a result, numerous organizations have adopted AV for their decision-making processes (see Regenwetter & Tsetlin, 2004).

Numerous studies have extensively analyzed the merits and limitations of both SCR and AV. Prominent works, such as those by Felsenthal (2012) and the comprehensive Handbook of Approval Voting edited by Laslier and Sanver (2010), delve into these voting rules and offer insights into their strengths and weaknesses. The objective of such analyses is to provide valuable information and insights to the public and decision-makers, facilitating informed discussions and considerations regarding the selection or implementation of an appropriate voting rule in the context of electoral reform. Through rigorous analysis and empirical evidence, they aim to inform public opinion and provide decision-makers with valuable guidance in choosing the “best" voting rule suited to their specific needs and goals.

Norris (1997) points out, following a long tradition of analysis of the influence (real or supposed) of voting systems on political systems, that an electoral reform is never trivial; because, depending on the society in which it is implemented, it can lead to unstable political systems, result in strong political polarization, give the role of kingmaker to certain groups, or favor certain types of candidates. Indeed, any electoral reform should be driven by well-defined objectives and necessitate thoughtful deliberations regarding both its goals and the normative criteria that the chosen voting rule should meet. In addition, it is crucial that the voting rule implemented is simple and easily understandable for voters. A voting system that is complex or difficult to understand may discourage voter participation and undermine the legitimacy of the electoral process. Simplicity and transparency in the voting rule help ensure that voters can easily grasp the mechanics of the system, have confidence in the process, and make informed choices. Unfortunately, no clear consensus seems to emerge in the literature on the possible superiority of one rule over the others. Arguments in favor of different voting rules are diverse and numerous, reflecting the complexity and multifaceted nature of the topic. Given this lack of consensus, one potential solution is to seek a compromise between the families of voting rules. This is the choice that Brams and Sanver (2009) and Sanver (2010) seem to have made.

Brams and Sanver (2009) and Sanver (2010) introduced two voting rules reconciling ranking-based decisions with approval-based decisions²: Preference approval voting (PAV) and fallback voting (FV). Under PAV, voters rank all the running candidates and distinguish the ones they approve of from those they disapprove of. If there is no more than one alternative with the majority of approvals (greater than half of the number of voters), PAV picks the AV winner; when more than one candidate is approved by more than half of the electorate, PAV picks the one who is preferred by the majority among them; in case of a majority cycle among these candidates, it picks the one with the highest number of approvals among them. Under FV, voters first indicate all the candidates they approve of (this can range from no candidates to all), and then they rank only these candidates; each level of rankings (of the approved candidates) is considered, and if at a given level a majority of voters agree on one highest-ranked candidate, this candidate is the FV winner.³ The procedures implemented under PAV or FV to determine the winner are defined in such a way as to satisfy both the principle of the “most approved” and that of the “most preferred.” However, the above informal definitions of PAV and FV do not appear to take into account situations where ties may arise; in fact, there is no reference made to any tie-breaking rules. Further discussion on this point will be provided in Sect. 2. Formal definitions of PAV and FV are provided later.

Brams and Sanver (2009) have highlighted several desirable properties and drawbacks of FV and PAV. They showed among other things that FV, PAV, and AV may all give different winners for the same profile; a unanimously approved candidate may not be an FV or a PAV winner; a least-approved candidate may be an FV or PAV winner; a PAV winner may be different from the winners under BR; FV and PAV may fail to pick the Condorcet winner when he exists. Given the limited number of properties considered, the analysis of Brams and Sanver (2009) does not allow a clear judgement on the superiority or not of PAV and FV compared to AV or SCR. It is striking to note that since PAV and FV were introduced, almost no work has addressed these rules, contrary to the case for AV or SCR.⁴ In this paper, our objective is to conduct a comprehensive analysis of the properties of PAV and FV in order to gain deeper insights into these voting rules. Our aim is to draw meaningful conclusions about the strengths and limitations of PAV and FV based on our analysis. Can we say that these rules are a “good” compromise between AV and SCR? Are they better? If the answer is yes, then the choice of PAV or FV as a replacement for SCR or AV would then be justified, and these rules would therefore be recommendable for real-world use.

To achieve our goal, this paper is structured into two phases. The first phase focuses on extending the analysis of FV and PAV based on the groundwork laid by Brams and Sanver (2009). We delve into additional properties of FV and PAV, exploring their performance in relation to other desirable properties commonly used in evaluating voting rules. Many of these properties have been extensively studied in the normative evaluation of SCR and AV. On this basis, we believe that it will henceforth be easier to decide on a comparison between PAV, FV, and these rules. It is fair to say that we cannot here review, in an exhaustive way, all the normative properties encountered in the literature. The properties on which we base our study are the following: the Condorcet principle, social acceptability, efficient compromise, Pareto optimality, cancellation, reinforcement, homogeneity, clone independence, and the independence criterion. When these criteria are satisfied, they guarantee a certain consistency between individual preferences and the collective choice. Each of these criteria will be presented in detail later. Before delving into our analysis, it is important to provide a brief overview of some of the properties we will be discussing. The Condorcet principle allows us, on the one hand, to ensure that when a Condorcet winner (a candidate preferred to any other candidate by more than half of the voters) exists, then that candidate is elected; on the other hand, it allows us to avoid the election of the Condorcet loser (a candidate to whom more than half of the voters prefer any other candidate) when he exists. Social acceptability suggests that a candidate should be elected when the number of voters who rank him among the half of the candidates they prefer is at least as large as the number of voters who rank him in the least preferred half. The efficient compromise principle advocates the election of candidate(s) receiving the highest quantity of support at some efficient level of quality, the quality of support being defined in terms of a candidate’s rank in the order of voters’ preferences. As we will see later, the non-satisfaction of some of these properties is presented in the literature as unacceptable for a democratic voting rule. It follows that the choice of a voting rule is consequential. We show among other things that FV and PAV are Pareto optimal, and that they always elect the absolute Condorcet winner when such a candidate exists⁵; and we determine the conditions under which these rules satisfy the reinforcement criterion, and under which they are not vulnerable to the no-show paradox. From our analysis, it appears that FV and PAV satisfy and respect some of the properties that AV fails.

A great deal of work has been done in recent years on the probability of AV electing the Condorcet winner (or the Condorcet loser) when he exists. In this sense, these studies have made notable comparisons between AV and the three most popular SCR (PR, NPR, and BR). We can quote in this respect the works of Diss et al. (2010), El Ouafdi et al. (2020), Gehrlein and Lepelley (1998), Gehrlein and Lepelley (2015), and Gehrlein et al. (2016). The second part of this paper will lead in a similar direction. This will provide us with the opportunity to conduct a comparative evaluation of AV, FV, PAV, and SCR. First, for voting situations with three candidates and an electorate tending to infinity, we evaluate the probabilities of agreement between AV, FV, and PAV; this analysis is extended to the three scoring rules PR, NPR, and BR. We are also interested in the probabilities of satisfaction or violation of the Condorcet criteria. One advantage that FV and PAV have over AV is their reliance on the principle of “most preferred” candidates. This advantage becomes particularly evident when it comes to electing the Condorcet winner, should one exist. It will therefore be necessary to be aware of the amplitude of this advantage. To do so, our calculations adopt the impartial and anonymous culture assumption. This assumption will be defined later. Our computation analysis teaches us that for three-candidate elections, the combination of approvals and rankings in FV and PAV brings them closer to SCR in terms of agreement, as opposed to AV; furthermore, they perform better in terms of compliance with the Condorcet criteria than some SCR.

The rest of the paper is organized as follows: Sect. 2 is devoted to basic definitions. Section 3 presents our results on the properties of FV and PAV. We provide our probabilistic results in Sect. 4. Section 5 concludes.

2 Notation and definitions

Consider a set of n ($n\ge 2$) non-abstaining individuals $N=\{1,2,\ldots ,i,\ldots ,n\}$ who vote sincerely on $\mathcal {C}=\{a,b,c,\ldots ,m\}$ a set of m ($m\ge 3$) candidates. It is assumed that the rankings provided by the voters on $\mathcal {C}$ are asymmetric, meaning that there are no ties in the rankings. Furthermore, we assume that the approvals of the voters are monotonic with respect to their rankings. This means that if a voter approves a and ranks b ahead of a, this implies that he also approves b. For example, the ranking $\underline{a}\succ \underline{b}\succ c$ (or simply $\underline{a}\underline{b}c$) means that a is ranked ahead of b which is ahead of c, and a and b are both approved while c is disapproved.

As voters’ inputs are both rankings and approvals, a voting situation is therefore a $\kappa$-tuple $\pi =(n_{1},n_{2},\ldots ,n_{t},\ldots ,n_{\kappa })$ that indicates the total number $n_t$ of voters for each of the $\kappa$ rankings on $\mathcal {C}$ such that $\sum \limits _{t=1}^{\kappa }n_{t}=n$; given the assumptions made above, $\kappa =(m+1)!$. Given $\pi$, we denote by $n_{ab}(\pi )$ (or simply $n_{ab}$) the number of voters who rank a before b. Candidate a is majority-preferred to b if $n_{ab}>n_{ba}$. We say that candidate a is the Condorcet winner if $n_{ab}>n_{ba}~~\forall b\in \mathcal {C}\setminus \{a\}$; candidate a is the Condorcet loser if $n_{ab}<n_{ba}~~\forall b\in \mathcal {C}{\setminus }\{a\}$. A candidate a is an absolute Condorcet winner (resp. an absolute Condorcet loser) if he is ranked first (resp. last) by more than half of the voters.

Given the rankings and approvals of the voters, we denote by $S^{l}(a,\pi )$ or simply $S^{l}(a)$ the total number of approvals of candidate a when rankings of level l are considered ($l=1,2,\ldots ,m$); we say that candidate a is majority-approved at level l if $S^{l}(a)>\frac{n}{2}$.

Let us now define each of the voting rules under consideration here.

Approval voting (AV)::

Under this rule, voters can vote for (approve of) as many candidates as they wish. We denote by $\textbf{AV}(a,\pi )$ the total number of approvals for candidate a given $\pi$. Candidate a is the AV winner if $\textbf{AV}(a,\pi )>\textbf{AV}(b,\pi )~~\forall b\in \mathcal {C}{\setminus }\{a\}$. Notice that $\textbf{AV}(a,\pi )=S^{m}(a)$.

Preference approval voting (PAV)::

According to Brams and Sanver (2009), PAV is determined by two rules and proceeds as follows:

• Rule 1: The PAV winner is the AV winner if

  • a. no candidate receives a majority of approval votes (i.e., is approved by more than half of the electorate);

  • b. exactly one candidate receives a majority of approval votes.

• Rule 2: In the case that two or more candidates receive a majority of approval votes,

  • a. the PAV winner is the one among these candidates who is preferred by a majority to every other majority-approved candidate.

  • b. In the case of a cycle among the majority-approved candidates, then the AV winner among them is the PAV winner.

Fallback voting (FV)::

Following Brams and Sanver (2009), FV proceeds as follows:

• 1. Voters indicate all candidates of whom they approve, who may range from one candidate (since we only consider non- abstaining voters) to all candidates. Voters rank only those candidates of whom they approve.

• 2. The highest-ranked candidate of all voters is considered. If a majority of voters agree on one highest-ranked candidate, this candidate is the FV winner. The procedure stops, and we call this candidate a level 1 winner.

• 3. If there is no level 1 winner, the next-highest-ranked candidate of all voters is considered.⁶ If a majority of voters agree on one candidate as either their highest- or their next-highest-ranked candidate, this candidate is the FV winner. If more than one candidate receives majority approval, then the candidate with the largest majority is the FV winner. The procedure stops, and we call this candidate a level 2 winner.

• 4. If there is no level 2 winner, the voters descend—one level at a time—to lower and lower ranks of approved candidates, stopping when, for the first time, one or more candidates are approved of by a majority of voters, or no more candidates are ranked. If exactly one candidate receives majority approval, this candidate is the FV winner. If more than one candidate receives majority approval, then the candidate with the largest majority is the FV winner. If the descent reaches the lowest rank of all voters and no candidate is approved of by a majority of voters, the candidate with the most approval is the FV winner.

It is worth noting that the definitions of PAV and FV that we have just presented do not explicitly address situations where ties occur. This is especially true in cases where the number of voters is even. In such situations, it becomes necessary to describe a method for resolving ties. Various tie-breaking methods can be considered, including the random tie-breaking method suggested by Sanver (2010). However, there may be several issues associated with the use of a tie-breaking rule. For the same situation, different tie-breaking rules can lead to different results. The use of a tie-breaking rule can result in the violation of certain normative properties; or it may lack transparency, making it difficult for voters and stakeholders to comprehend and evaluate the decision-making process which can undermine the legitimacy and acceptance of the outcome. Then, the use of a tie-breaking rule should be carefully evaluated, taking into account its impact on normative properties, necessity, subjectivity, potential manipulation, and transparency. In the context of this paper, it is not necessary to explore in a particular way the cases where ties can occur.

Since the second part of the paper will have to include the three most popular scoring rules, let us define them at the outset here.

Plurality rule (PR)::

This rule picks the candidate who is the most ranked at the top. We denote by $\textbf{PR}(a,\pi )$ the plurality score of candidate a. Notice that $\textbf{PR}(a,\pi )=S^{1}(a)$. Candidate a is the PR winner if $\textbf{PR}(a,\pi )>\textbf{PR}(b,\pi )~~\forall b\in \mathcal {C}{\setminus }\{a\}$.

Negative plurality rule (NPR)::

Under this rule, the winner is determined based on the candidate who receives the fewest last-place rankings from the voters. We denote by $\textbf{NPR}(a,\pi )$ the number of last places (the negative plurality score) of candidate a; this candidate is the NPR winner if $\textbf{NPR}(a,\pi )<\textbf{NPR}(b,\pi )~~\forall b\in \mathcal {C}{\setminus }\{a\}$.

Borda rule (BR)::

BR gives $K - t$ points to a candidate each time she is ranked tth; $\textbf{BR}(a,\pi )$, the Borda score of a candidate, is the sum of the points received. Candidate a is the BR winner if $\textbf{BR}(a,\pi )>\textbf{BR}(b,\pi )~~\forall b\in \mathcal {C}{\setminus }\{a\}$.

In the context of a single-winner election, it is possible for multiple candidates to obtain the same score under AV, PR, NPR, or BR. In such situations, a tie-break rule becomes necessary to determine the winner among the candidates with equal scores. In this paper, the setting is such that we will not need to use a tie-break rule.

We can now review the properties of FV and PAV.

3 Normative properties of FV and PAV

As previously mentioned, Sanver (2010) and Brams and Sanver (2009) have identified and analyzed several properties of FV and PAV. They showed that these rules are monotonic; more precisely, they are approval-monotonic and rank-monotonic. A voting rule is approval-monotonic (resp. rank-monotonic) if a class of voters, by approving of a new candidate (resp. by raising a candidate in their ranking)—without changing their approval of other candidates—never hurts that candidate and may help the candidate get elected. In this section, we will review additional properties that FV and PAV may either satisfy or fail to satisfy. By examining these properties, we aim to gain a comprehensive understanding of the behavior and performance of FV and PAV as voting rules. This analysis will provide insights into their advantages and limitations in comparison to other voting systems.

3.1 Condorcet principle

We know that AV may fail to pick the (absolute) Condorcet winner when he exists (see Felsenthal, 2012). According to Brams and Sanver (2009), FV and PAV may fail to elect the Condorcet winner when he exists; through Propositions 1 and 2, we refine this result.

Proposition 1

When AV selects the Condorcet winner, this candidate is also the PAV winner, but the reverse is not always true.

Proof

By definition, PAV always elects the AV winner under Rule 1; this may not be the case under Rule 2. So, for the proof, we only need to focus on Rule 2. Assume that candidate a is both the Condorcet winner and the AV winner. Let us also assume that candidate b ($b\ne a$) is the PAV winner under Rule 2; this means that (i) $\textbf{AV}(b,\pi )>\frac{n}{2}>\textbf{AV}(a,\pi )$ or (ii) $\textbf{AV}(a,\pi )>\frac{n}{2}$ and $\textbf{AV}(b,\pi )>\frac{n}{2}$. It is obvious that (i) clearly contradicts that a is the AV winner. By definition, b cannot win under (ii) since $n_{ab}>n_{ba}$, so a wins. Thus, if AV selects the Condorcet winner, this is also the case for PAV. Let us exhibit a profile to show that the reverse is not always true. Consider the following profile with three candidates and 11 voters:

$$\begin{aligned} 5:\underline{a}\succ \underline{b}\succ c~~~~~~~~ 5:\underline{b}\succ a\succ c~~~~~~~~ 1:\underline{c}\succ \underline{a}\succ b \end{aligned}$$

With this profile, it easy to see that b is the AV winner, while a is both the Condorcet winner and the PAV winner. $\square$

Proposition 2

FV and PAV always elect the absolute Condorcet winner when he exists.

Proof

Assume that candidate a is the absolute Condorcet winner. As he is ranked first by more than half of the voters, $\textbf{AV}(a,\pi )>\frac{n}{2}$ and $n_{ab}> n_{ba}$ for all $b\in \mathcal {C}{\setminus }\{a\}$. Under PAV, if a is the only one to be majority-approved, he is obviously elected; if there are more candidates majority-approved, a is elected since he is the Condorcet winner. So, PAV always elects the absolute Condorcet winner. Since a is the absolute Condorcet winner we get $S^{1}(a)>\frac{n}{2}$: by definition, he is the FV winner. So, FV always elects the absolute Condorcet winner. $\square$

The fact is that when there is an absolute Condorcet winner, this candidate is the winner under FV, PAV, and PR. As noted further in the paper, FV and PAV exhibit insensitivity to certain paradoxes in domains where an absolute Condorcet winner exists. The story is quite different on the domain where there is an (absolute) Condorcet loser. We know that AV can elect the (absolute) Condorcet loser (see Felsenthal, 2012). We also know from Kamwa (2019) that PAV may pick the Condorcet loser when he exists. To our knowledge, nothing is known concerning FV. Propositions 3 tells us more on this.

Proposition 3

FV and PAV may elect the (absolute) Condorcet loser when he exists. When PAV elects the (absolute) Condorcet loser, this candidate is also the AV winner but the reverse is not true. When FV elects the absolute Condorcet loser, this candidate is also the AV winner, but the reverse is not always true.

Proof

Consider the following profile with three candidates and 11 voters.

$$\begin{aligned} 5:\underline{a}\succ b\succ c~~~~~~~~ 3:\underline{b}\succ c\succ a~~~~~~~~ 3:\underline{c}\succ b\succ a \end{aligned}$$

With this profile it is easy to see that a is the absolute Condorcet loser and that he is the AV winner, the FV winner, and the PAV winner. So, FV and PAV may elect the (absolute) Condorcet loser when he exists.

By definition, PAV can elect a (absolute) Condorcet loser only under Rule 1; as Rule 1 of PAV is equivalent to AV, it follows that for a given profile, if PAV elects the (absolute) Condorcet loser, he is also the AV winner. In the following profile, a is both the absolute Condorcet loser and the AV winner but b is the PAV winner.

$$\begin{aligned} 5:\underline{a}\succ b\succ c~~~~~~ 3:\underline{a}\succ c\succ b~~~~~~ 5:\underline{b}\succ \underline{c}\succ \underline{a}~~~~~~ 4:\underline{c}\succ b\succ a \end{aligned}$$

Assume that candidate a is the absolute Condorcet loser; it follows that $S^{l}(a)<\frac{n}{2}$ for $1\le l\le m-1$. Candidate a cannot be the FV winner on this range. He can only be elected at $l=m$; if so, this means that if he receives the highest score of AV, then he is also the AV winner. The above profile is sufficient to show that the reverse is not true since a is both the absolute Condorcet loser and the AV winner, while c is the FV winner. $\square$

3.2 Efficient compromise

The efficient compromise axiom was introduced by Özkal-Sanver and Sanver (2004) as a trade-off between the quantity and quality of support that a candidate may receive; the quantity refers to the number of voters supporting a candidate, and the quality of support is defined in terms of a candidate’s rank in the order of voters’ preferences. According to Merlin et al. (2019), for any profile, the efficient compromises are candidates receiving the highest quantity of support at some efficient level of quality. A voting rule is said to satisfy the efficient compromise axiom if and only if it always picks efficient compromises. Following Özkal-Sanver and Sanver (2004), the plurality rule meets the efficient compromise; this is also the case for the q-approval fallback bargaining⁷ for any $q\in \{1,2,\ldots ,n\}$, while the Borda rule and all the Condorcet consistent rules do not. What is more, Merlin et al. (2019) showed that if the set of efficient compromises contains only one candidate, all the scoring rules will pick this candidate. Proposition 4 tells us that AV and PAV may fail the efficient compromise axiom except on the domain where there is an absolute majority winner.

Proposition 4

FV, PAV, and AV do not satisfy the efficient compromise axiom. FV and PAV always satisfy the efficient compromise axiom over the domain where there is an absolute Condorcet winner.

Proof

To show that FV, PAV, and AV do not meet the efficient compromise axiom, let us consider the following profile⁸ with four candidates $\{a,b,c,d\}$ and seven voters;

$$\begin{aligned}{} & {} 1:\underline{a}\succ \underline{b}\succ d\succ c \quad \quad 2:\underline{a}\succ c\succ d\succ b \quad \quad 2:\underline{b}\succ c\succ d\succ a \\{} & {} 1:\underline{c}\succ \underline{b}\succ d\succ a \quad \quad 1:\underline{d}\succ c\succ b\succ a \\ \end{aligned}$$

With this profile, the reader can check that $\{a,c,d\}$ is the set of efficient compromises, while b is the winner under AV, FV, and PAV.

Notice that if an absolute Condorcet winner exists, he is also an efficient compromise. As previously mentioned, when an absolute Condorcet winner exists, both FV and PAV are equivalent to PR. Given that PR satisfies the efficient compromise axiom, it will select the absolute Condorcet winner, just like FV and PAV. $\square$

3.3 Social (un)acceptability

In the search for a certain consensus around a candidate, Mahajne and Volij (2018) have introduced the concept of social acceptability. They say that a candidate is socially acceptable if the number of voters who rank him among their most preferred half of the candidates is at least as large as the number of voters who rank him among the least preferred half. Mahajne and Volij (2018) showed that there always exist at least one socially acceptable candidate in any profile; and they show that there exists a unique scoring rule that always elects such a candidate, the half accepted-half rejected rule (HAHR).⁹ In contrast to a socially acceptable candidate, a candidate is said to be socially unacceptable if the number of individuals who rank him among their least preferred half of the candidates is at least as large as the number of voters who rank him among the most preferred half.

Proposition 5

AV, FV, and PAV may not select a socially acceptable candidate, and they may select a socially unacceptable candidate. Following Proposition 2, within the domain where an absolute Condorcet winner exists, FV and PAV always select a socially acceptable candidate and never select a socially unacceptable candidate.

Proof

Consider the following profile with three candidates and six voters.

$$\begin{aligned} 2:\underline{a}\succ c\succ b~~~~~~~~~~~ 1:\underline{a}\succ \underline{b}\succ c~~~~~~~~~~~ 1:\underline{b}\succ a\succ c~~~~~~~~~~~ 2:\underline{c}\succ \underline{b}\succ a \end{aligned}$$

In this profile, a is a socially acceptable candidate, while b is socially unacceptable, and b is the winner under AV, FV, and PAV.

It is obvious that when he exists, an absolute Condorcet winner is also a socially acceptable candidate. By Proposition 2, FV and PAV always select this candidate. Such a candidate cannot be socially unacceptable; he is still elected in the presence of a socially unacceptable candidate. But this may not be the case for AV: to see this, just add a voter with $\underline{a}\succ \underline{b}\succ c~$; it follows that a is the absolute majority winner and therefore socially acceptable, while the AV winner is b. $\square$

3.4 Cancellation property

Before going further, let us raise a point about PAV. By definition, Rule 2 of PAV relies on pairwise comparisons to decide the winner; but what if all the majority duels between the majority-approved candidates end up in tie? In such a case, should all candidates be declared elected, or only the one(s) with the highest AV score? This situation does not seem to have been taken into account by Brams and Sanver (2009). In such a scenario, not choosing all the candidates involved implies a violation of the cancellation criterion. The cancellation condition requires that when all the majority comparisons end up in a tie, all the candidates should be selected (Young, 1974). Admittedly, it is a bit difficult to apply the cancellation property to AV, because this rule does not fundamentally depend on rankings. Proposition 6 tells us that FV and PAV fail the cancellation criterion and that this also the case for AV when it is based on rankings.

Proposition 6

AV, FV, and PAV do not meet the cancellation property.

Proof

Consider the following profile with three candidates and four voters.

$$\begin{aligned} 2:\underline{a}\succ \underline{b}\succ c~~~~~~~~~~~ 2:\underline{c}\succ \underline{b}\succ a \end{aligned}$$

We can see in this profile that all the pairwise comparisons end up in ties, while candidate b is the winner of AV, FV, and PAV. So, AV, FV, and PAV fail the cancellation property.$\square$

3.5 Pareto optimality

In a given voting situation, candidate a Pareto dominates candidate b if all the voters strictly prefer a to b. A candidate is said to be Pareto-optimal if there is no other candidate that dominates him. According to Felsenthal (2012), the election of a candidate a is not tolerable when there is another candidate b that all voters rank before him. Felsenthal (2012) drives the point home by arguing that a voting rule that can elect a Pareto-dominated candidate should be disqualified no matter how low the frequency. A voting rule meets the Pareto criterion if for all voting profiles it never elects a Pareto-dominated candidate. According to Felsenthal (2012), AV may elect a Pareto-dominated candidate. Proposition 7 tells us that this is not the case for FV and PAV.

Proposition 7

FV and PAV meet the Pareto criterion.

Proof

Given $\pi$, assume that a is the PAV winner and that he is Pareto-dominated by b. As b Pareto-dominates a, if a voter approves a, this is also the case for b; it follows that $\textbf{AV}(b,\pi )\ge \textbf{AV}(a,\pi )$, and b is majority-preferred to a since $n_{ba}=n$. If a wins under Rule 1i of PAV, this means that $\textbf{AV}(b,\pi )<\textbf{AV}(a,\pi )<\frac{n}{2}$ which contradicts $\textbf{AV}(b,\pi )\ge \textbf{AV}(a,\pi )$. If a wins under Rule 1ii of PAV, this leads to $\textbf{AV}(a,\pi )>\frac{n}{2}$ and $\textbf{AV}(b,\pi )<\frac{n}{2}$ which contradicts $\textbf{AV}(b,\pi )\ge \textbf{AV}(a,\pi )$. If a wins under Rule 2 of PAV, the following three cases can be considered: (i) $\textbf{AV}(a,\pi )>\frac{n}{2}$, $\textbf{AV}(b,\pi )>\frac{n}{2}$, and $n_{ab}>n_{ba}$, or (ii) $\textbf{AV}(a,\pi )>\frac{n}{2}>\textbf{AV}(b,\pi )$, $\textbf{AV}(c,\pi )>\frac{n}{2}$, and $n_{ac}>n_{ca}$ for $c\in \mathcal {C}{\setminus }\{a,b\}$, or (iii)$\textbf{AV}(a,\pi )>\textbf{AV}(b,\pi )>\frac{n}{2}$. It turns out that (i) contradicts $n_{ba}=n$ while (ii) and (iii) contradict $\textbf{AV}(b,\pi )\ge \textbf{AV}(a,\pi )$. Thus, b cannot win: PAV meets the Pareto criterion.

Given $\pi$, assume that a is the FV winner and that he is Pareto-dominated by b. By definition, as b Pareto-dominates a, we get $S^{1}(b)>S^{1}(a)$, and $S^{l}(b)\ge S^{l}(a)$ for all $l>1$. That candidate a wins at a level l implies that $\frac{n}{2}>S^{l}(a)> S^{l}(b)$ or $S^{l}(a)>\frac{n}{2}> S^{l}(b)$ or $S^{l}(a)> S^{l}(b)>\frac{n}{2}$; these conditions all contradict that $S^{l}(b)\ge S^{l}(a)$. So, b cannot be the winner: FV never elects a Pareto-dominated candidate. $\square$

3.6 The reinforcement condition

According to the reinforcement condition¹⁰ (Myerson, 1995), when an electorate is divided in two disjoint groups of voters $N_1$ ($\vert N_{1}\vert =n_{1}$) and $N_2$ ($\vert N_{2}\vert =n_{2}$) such that $N_{1}\cap N_{2}=\emptyset$ and $N_{1}\cup N_{2}=N$ ($\vert N\vert =n_{1}+n_{2}=n$), and the winner is the same for each group, this outcome will remain unchanged when both groups of voters are merged. It is known that AV, PR, NPR, and BR meet the reinforcement condition (see Felsenthal, 2012). Proposition 8 tells us that FV and PAV do not meet the reinforcement condition, and it characterizes when this is (not) the case.

Proposition 8

Assume that an electorate is divided in two disjoint groups of voters $N_1$ and $N_2$ such that the winner is the same for each group.

• Considering that PAV is defined by four rules (Rule 1i, Rule 1ii, Rule 2i, and Rule 2ii), it always meets the reinforcement criterion if the winner in each of the two groups of voters is determined by Rule 1i or Rule 1ii; this is also the case when the winner is determined in one group by Rule 1i and in the other group by Rule 1ii. In the other cases, PAV may fail the reinforcement condition.

• FV meets the reinforcement condition if the winner in each group is determined at the same level of rankings. In the other cases, it may fail the reinforcement condition.

Proof

See Appendix. $\square$

3.7 Homogeneity

Given the voting outcome on a voting profile, if duplicating this profile $\lambda$ times ($\lambda >1$, $\lambda \in \mathbb {N}$) changes the result, we say that the homogeneity property is not satisfied. The violation of the homogeneity property is a major challenge for collective decision rules (Nurmi, 2004). It is obvious that AV is homogeneous since duplicating a population also duplicates the approvals in the same magnitude. Proposition 9 tells us the same thing concerning FV and PAV.

Proposition 9

FV and PAV are homogeneous.

Proof

Suppose we duplicate a profile $\pi$, $\lambda$ times. On the resulting profile, given a candidate x, we have $S^l(x,\lambda \pi )=\lambda S^l(x,\pi )$, $\textbf{AV}(x,\lambda \pi )=\lambda \textbf{AV}(x,\pi )$, and $n_{xy}(\lambda \pi )=\lambda n_{xy}(\pi )$. It then follows that if a candidate wins under FV at level l in $\pi$, he also wins at the same level in $\lambda \pi$; we reach the same conclusion with PAV. Thus, duplicating a profile does not change the outcome under FV and PAV. $\square$

3.8 The no-show paradox and the truncation paradox

The no-show paradox describes a situation under which some voters may do better to abstain than to vote since abstaining may result in the victory of a more preferable or desirable candidate (Doron & Kronick, 1977; Fishburn & Brams, 1983). The plurality rule, the Borda rule, and approval voting are among the few voting rules not vulnerable to the no-show paradox (Felsenthal, 2012). It is known that the vulnerability of a voting rule to the no-show paradox leads to its vulnerability to the truncation paradox, but the reverse is not always true (Nurmi, 1987). The truncation paradox occurs when some voters may reach a more preferred outcome by submitting a sincere but incomplete ranking (Fishburn & Brams, 1983, 1984). According to Brams (1982), AV is sensitive to the truncation paradox; this is also the case for NPR and BR but not for PR.¹¹ Proposition 10 characterizes the vulnerability of FV and PAV to the no-show paradox.

Proposition 10

PAV is vulnerable to the no-show paradox only when the winner is determined by Rule 2i. FV is not vulnerable to the no-show paradox only when the winner is determined at level $l=1$ or $l=m$. Thus, FV and PAV are vulnerable to the truncation paradox.

Proof

See Appendix. $\square$

3.9 Independence of clones

Following Tideman (1987), a proper subset S containing two or more candidates is a set of clones if no voter ranks any candidate outside of S as either tied with any element of S or between any two elements of S. A voting rule is said to be independent of clones if and only if the following two conditions are met when clones are on the ballot:

• 1. A candidate that is a member of a set of clones wins if and only if some member of that set of clones wins after a member of the set is eliminated from the ballot.

• 2. A candidate that is not a member of a set of clones wins if and only if that candidate wins after any clone is eliminated from the ballot.

Tideman (1987) shows that AV is not generally independent of clones. Nonetheless, he points out that applying the concept of clones to AV is somewhat problematic because clones are defined in terms of voters’ rankings. This problem does not arise with FV and PAV, which are defined in terms of rankings. As Tideman (1987) points out, when talking about clones in an approval setting, it is obvious that if a voter approves a candidate a and not his clone b, that voter will approve b if a withdraws; based on this, he showed that AV is not independent of clones. Since there are situations in which FV or PAV coincide with AV, it follows that in these situations FV and PAV may be vulnerable to cloning.

Proposition 11

FV and PAV are not independent of clones. Nonetheless, they are independent of clones on the domain where there is an absolute Condorcet winner.

Proof

To show that FV and PAV are not independent of clones, let us consider the following profile:

$$\begin{aligned} 4:\underline{a}\succ b\succ c~~~~~~~~~~~ 3:\underline{b}\succ c\succ a~~~~~~~~~~~ 2:\underline{c}\succ b\succ a \end{aligned}$$

In this profile, candidate a is the AV, FV, and PAV winner. Candidates b and c are clones; if one of them withdraws, the other becomes the winner for each rule given that if a voter approves candidate b and not his clone c, that voter will approve c if b withdraws. So, FV and PAV are not independent of clones.

Now, let us assume that there is absolute Condorcet winner, say candidate a; following Proposition 2, this candidate is elected by both FV and PAV. The withdrawal of one or more candidates (clones) does not change candidate a’s status as the absolute Condorcet winner; Proposition 2 applies and a remains the winner. Thus, over the domain where there is an absolute Condorcet winner, FV and PAV are independent of clones. $\square$

3.10 Independence criterion and spoiler effect

According to Sanver (2010), a social choice satisfies the independence criterion if and only if it does not admit any spoiler; a spoiler is a candidate $x\notin \mathcal {C}$ such that its presence as an alternative can change the social choice without x being chosen. Sanver (2010) showed that under FV, for any number of voters, there may be a spoiler who is approved by only one voter; under PAV, a candidate is a spoiler only if he is socially qualified as good.

Proposition 12

(Sanver, 2010) AV satisfies the independence criterion while PAV and FV fail it.

The independence criterion as introduced by Sanver (2010) obviously reminds us of the spoiler effect even though these two concepts differ in their definitions. In single-winner elections, the spoiler effect occurs if the removal of a non-winning candidate (called a spoiler) changes the election result (Kaminski, 2018; Miller, 2017): a spoiler turns a winner into a non-winner and a non-winner into a winner. The independence criterion assumes that the spoiler is a new candidate (introduced without any chance of winning), while the classical conception of the spoiler assumes that it is an element of the original set of candidates. It is therefore obvious that a conjunction of Propositions 11 and 12 leads to Proposition 13.

Proposition 13

AV, PAV, and FV are sensitive to the spoiler effect.

We are now going to summarize all the above results in Table 1. In this table, we recap our findings about PAV, AV, and FV, as well as those of Brams and Sanver (2009) and Sanver (2010); besides FV and PAV, we include PR, NPR, and BR. The fact that these rules satisfy or do not satisfy one of the criteria retained here comes from results of the literature (see Nurmi, 1987; 1999; Felsenthal, 2012). In Table 1, a “Yes” means that the voting rule meets the supposed criterion¹² and a “No” means it does not.

Table 1 Normative properties of the rules

On the basis of the normative criteria used in our analysis, it appears that FV and PAV satisfy and fail the same criteria; they possess two properties that AV does not: Pareto optimality and the fact of always electing the absolute Condorcet winner when he exists. AV, for its part, meets two criteria that FV and PAV do not: reinforcement and non-vulnerability to the no-show paradox. Approval-based rules, compared to score-based rules, satisfy fewer criteria. Another way to compare these sets of rules would be to check the frequencies for the criteria they violate. This is what we try to do in the next section, with particular attention to the Condorcet criteria.

4 Computational analysis

Our aim in this section is to evaluate, for voting situations with three candidates and electorates tending to infinity, the probabilities of some voting events. We have chosen to only present here the main messages that stand out from our calculations, while relegating the details of our calculation approach to Appendix 3.¹³ So, we formally define, for three-candidate elections, the preferences and voting rules in Appendix 3.1. The impartial and anonymous culture assumption that we assume for our computations is presented in Appendix 3.2.

In our calculations, we focus on the following voting events, already described above:

• the agreement between the rules;

• FV and PAV may pick the least-approved candidate;

• FV or PAV may not pick a unanimously approved candidate;

• the satisfaction (resp. the violation) of the Condorcet winner criterion (resp. the Condorcet loser criterion).

We extend our analysis to the three popular scoring rules (PR, NPR, and BR) and consider comparisons with FV and PAV. This extension is justified by the fact that we have pointed out above that, in some configurations, FV is very close to PR.

Concerning the agreement between the rules under consideration, Table 2 summarizes the probabilities we obtained.

Table 2 Limiting probabilities of agreement

It turns out that among the rules under consideration, BR is the one with the highest probability of agreement with each of the other rules. In at least $66\%$ of the cases, FV agrees with each of the other rules, and it tends to agree more with PAV ($74.75\%$) than with AV ($73.14\%$), and more with NPR ($70.77\%$) than with PR ($66.03\%$). PAV tends to more agree with PR ($79.93\%$) than with AV ($67.15\%$) or with NPR ($65.56\%$). Not surprisingly, AV tends to agree more with FV and PAV than with scoring rules. Regarding scoring rules, PR and BR tend to agree the most with PAV. The general observation derived from Table 2 suggests that the combination of approvals and rankings in FV and PAV tends to align them more closely with scoring rules rather than AV, particularly in terms of agreement.

Brams and Sanver (2009) showed that for the same preference profile, AV, FV, and PAV can elect completely different candidates. From our computations, we found that for the same voting profile, PAV, AV, and FV elect the same winner in about $58.86\%$ of cases; they therefore diverge in about $41.13\%$ of cases.

When it comes to the election of a least-approved candidate, this occurs in $8.07\%$ of cases under PAV while it occurs in $4.95\%$ of cases under FV. FV would therefore be almost half as likely to elect a least-approved candidate than PAV. This result would tend to confirm the fact that in terms of agreement, AV coincides more with FV than PAV. Another point of dissonance between FV, PAV, and AV appears when FV and PAV do not elect a unanimously approved candidate. We found that in almost $18.89\%$ of the cases, PAV may not elect a unanimously approved candidate, while this is the case in only $8.58\%$ of the cases for FV.

According to Ju (2010) and Xu (2010), when voters have dichotomous preferences, AV always elects the Condorcet winner when he exists. This is not always the case when voters have rather strict preferences or when indifference is allowed, as shown by Diss et al. (2010), Gehrlein and Lepelley (1998), Gehrlein and Lepelley (2015), and Kamwa (2019). Considering three-candidate elections with a certain degree of indifference under the extended impartial culture condition,¹⁴ Diss et al. (2010) and Gehrlein and Lepelley (2015) conclude that AV is more likely to elect the Condorcet winner than both PR and NPR; BR performs better than AV. Gehrlein and Lepelley (2015) and El Ouafdi et al. (2020) reach a quite similar conclusion when considering the extended impartial anonymous culture condition.¹⁵ When it comes to electing the absolute Condorcet winner when he exists, El Ouafdi et al. (2020) show in their framework that AV does less well than BR but better than NPR.¹⁶

Almost nothing is known about the propensity of FV and PAV to elect the Condorcet winner (resp. the Condorcet loser) when he exists. Kamwa (2019) investigates the limiting Condorcet efficiency of PAV in three-candidate elections while assuming the extended impartial culture condition; he finds that PAV tends to perform better than AV. Considering the framework developed in this paper, we compute the Condorcet efficiency of AV, FV, PAV, PR, NPR, and BR and their propensity to elect the absolute Condorcet winner when he exists. We do the same job for the election of the Condorcet loser and of the absolute Condorcet loser. Our results are summarized in Table 3. In this table, we denote by $\mathcal{C}\mathcal{E}(R)$ (resp. $\mathcal{C}\mathcal{L}(R)$) the Condorcet efficiency (resp. the probability of electing the Condorcet loser) given the voting rule R; and we define $\mathcal {ACE}(R)$ and $\mathcal {ACL}(R)$ similarly.

Table 3 Voting rules and the limiting probabilities of the Condorcet principle

It emerges that PAV is the best-performing rule in terms of Condorcet efficiency; it is followed by BR. FV performs better than AV but worse than PR. Interestingly, within our framework, AV emerges as the rule with the lowest Condorcet efficiency, indicating that it performs worse than scoring rules in this context. The fact that AV performs worse than PR and NPR here contrasts with what Diss et al. (2010), Gehrlein and Lepelley (2015), and El Ouafdi et al. (2020) achieve in their different settings. As for electing the absolute Condorcet winner when he exists, AV performs worse than BR but better than NPR. This conclusion is in agreement with what El Ouafdi et al. (2020) obtain in their setting.

Table 3 also tells us that in our analytical framework, AV is the rule most likely to elect the Condorcet loser when he exists; it does less well than PR and NPR. This result contrasts with what El Ouafdi et al. (2020) or Gehrlein et al. (2016) achieve in their respective frameworks. With a limiting probability of nearly $0.01\%$, PAV performs significantly better than FV whose probability is raised to nearly $3\%$. Regarding the election of an absolute Condorcet loser, our results show that among our rules, AV is the most likely to elect such a candidate; PAV performs better than FV which performs better than PR.

To refine the comparisons, we may assess more closely how each of the probabilities in Table 3 reacts to the proportion $\alpha =\frac{n_{1}+n_{2}+n_{3}+n_{4}+n_{5}+n_{6}}{n}$ of voters who approve only one candidate. When $\alpha =1$, AV and PR are equivalent. For some values of $\alpha$, we report in Table 4 the probabilities $\mathcal{C}\mathcal{E}(R,\alpha )$, $\mathcal {ACE}(R,\alpha )$, $\mathcal{C}\mathcal{L}(R,\alpha )$, and $\mathcal {ACL}(R,\alpha )$ as functions of $\alpha$.

Table 4 Some computed values of $\mathcal{C}\mathcal{E}(R,\alpha )$, $\mathcal {ACE}(R,\alpha )$, $\mathcal{C}\mathcal{L}(R,\alpha )$, and $\mathcal {ACL}(R,\alpha )$

Table 4 demonstrates that the probabilities vary depending on the value of $\alpha$. We note that for $\alpha =1$, $\mathcal{C}\mathcal{E}(AV,1)=\mathcal{C}\mathcal{E}(FV,1)=\mathcal{C}\mathcal{E}(PAV,1)=\mathcal{C}\mathcal{E}(PR,1)$, and $\mathcal {ACE}(AV,1)=1$. In the scenario where the electorate consists solely of voters who approve exactly one candidate, PR, AV, PAV, and FV exhibit identical performance according to the (absolute) Condorcet winner criterion. PAV appears to surpass all other rules in terms of Condorcet efficiency for $0\le \alpha <3/4$; for $3/4\le \alpha \le 1$, BR dominates over other rules. PR tends to dominate FV for $0\le \alpha <1/2$, while we get the reverse for $1/2\le \alpha \le 1$. PR dominates AV for all $\alpha$; AV is also dominated by NPR for $0\le \alpha <1/2$. As for electing the absolute Condorcet winner, AV tends to dominate NPR for $\alpha \ge 1/3$, and it dominates BR for $\alpha \ge 2/3$.

For any value of $\alpha$, NPR appears to be the rule most likely to elect the Condorcet loser. It appears that $\mathcal{C}\mathcal{L}(AV,\alpha )$ decreases with $\alpha$ while $\mathcal{C}\mathcal{L}(PAV,\alpha )$ increases with $\alpha$. $\mathcal{C}\mathcal{L}(FV,\alpha )$ tends to increase for $\alpha$, going from 0 to reach its maximum at $\alpha =1/2$, then decreases. $\mathcal{C}\mathcal{L}(PR,\alpha )$ and $\mathcal{C}\mathcal{L}(NPR,\alpha )$ tend to grow for $0\le \alpha <1/2$, then to decrease for $1/2\le \alpha <1$. For $\alpha =1$, we find that AV, PR, FV, and PAV have the same probability to elect the Condorcet loser. For $0\le \alpha \le 1/2$, AV appears to be the rule most likely to elect an absolute Condorcet loser; over this interval, $\mathcal {ACL}(AV,\alpha )$ tends to decrease with $\alpha$. We also note that for $0\le \alpha \le 1/2$, FV and PAV never elect an absolute Condorcet loser. For $1/2<\alpha <1$, PR is the most likely to elect an absolute Condorcet loser; it is followed by AV, while PAV performs better than FV. For $\alpha =1$, AV, FV, PAV, and PR have the same probability (about $2.47\%$) of electing the absolute Condorcet loser.

5 Concluding remarks

The first objective of this paper was to further develop the analysis of Brams and Sanver (2009) regarding the normative properties of FV and PAV. This is how we managed to show that FV and PAV are Pareto optimal as they never elect a Pareto-dominated candidate; FV and PAV are also homogeneous; FV and PAV always elect the absolute Condorcet winner when he exists; and that on the domain where there is an absolute Condorcet winner, these rules always elect a socially acceptable candidate, they never elect a socially unacceptable candidate, and they are resistant to manipulation by clones. Nonetheless, these rules do not meet the cancellation property or the reinforcement criterion, and they are vulnerable to the no-show paradox and to the truncation paradox. We managed to find some conditions under which these rules always meet the reinforcement criterion or are not sensitive to the no-show paradox. It turns out that FV and PAV satisfy and fail the same criteria; they possess two properties that AV does not: Pareto optimality and the fact of always electing the absolute Condorcet winner when he exists. AV, for its part, meets two criteria that FV and PAV do not: the reinforcement criterion and non-vulnerability to the no-show paradox.

Even if, by definition, there is a certain advantage of FV and PAV over AV regarding the respect of the Condorcet majority criteria, we wanted to measure the extent of this advantage. Thus, for voting situations with three candidates, we calculated the probabilities that these rules would elect the (absolute) Condorcet winner or the (absolute) Condorcet loser. Our analysis shows that in terms of the election of the Condorcet winner, PAV performs better than BR which dominates FV. When it comes to electing the absolute Condorcet winner, PAV and FV dominate BR, AV, and PR. To prevent the election of an (absolute) Condorcet loser, FV and PAV perform better than AV and PR.

Our analysis shows that FV and PAV tend to deliver on the promise of being rules that could reconcile the advocates of score rules with those of approval voting. FV and PAV share the simplicity that characterizes AV, yet with scoring rules they share the constraint of ranking candidates, which can be a daunting task when there is a large number of candidates.

Appendices

Appendices

1.1 Appendix 1: Proof of Proposition 8

Assume that an electorate is divided into two disjoint groups of voters $N_1$ ($\vert N_{1} \vert =n_{1}$) and $N_2$ ($\vert N_{2}\vert =n_{2}$) such that $N_{1}\cap N_{2}=\emptyset$ and $N_{1}\cup N_{2}=N$ ($\vert N \vert =n_{1}+n_{2}=n$).

1.1.1 PAV and the reinforcement criterion

We know that AV is equivalent to Rule 1 of PAV; since AV meets the reinforcement condition, it follows that PAV meets the reinforcement condition if the winner in each group is elected by Rule 1i or 1ii. To complete the proof, let us show that this is no longer the case in the other configurations. So, consider the following profiles:

Profile 1	Profile 2		Profile 3
$1:\underline{a}\succ b\succ c$	$1:\underline{a}\succ \underline{b}\succ c$;	$2:\underline{a}\succ c\succ b$;	$2:\underline{a}\succ \underline{b}\succ c$;	$2:\underline{c}\succ \underline{a}\succ b$;
$3:\underline{b}\succ \underline{a}\succ c$	$1:\underline{c}\succ \underline{a}\succ b$;	$2:\underline{c}\succ \underline{b}\succ a$;	$1:\underline{b}\succ \underline{c}\succ a$;	$1:\underline{b}\succ \underline{c}\succ \underline{a}$
$2:\underline{c}\succ b\succ a$	$1:\underline{b}\succ c\succ a$;

Profile 4	Profile 5	Profile 6	Profile 7
$1:\underline{a}\succ c\succ b$	$1:\underline{a}\succ \underline{c}\succ \underline{b}$	$2:\underline{a}\succ \underline{b}\succ c$;	$2:\underline{a}\succ \underline{c}\succ b$;	$1:\underline{b}\succ \underline{a}\succ \underline{c}$;
$1:\underline{b}\succ c\succ a$	$1:\underline{b}\succ \underline{a}\succ \underline{c}$	$1:\underline{b}\succ \underline{c}\succ a$;	$2:\underline{b}\succ \underline{a}\succ c$;	$1:\underline{b}\succ \underline{c}\succ \underline{a}$
$2:\underline{c}\succ \underline{a}\succ \underline{b}$	$1:\underline{c}\succ a\succ b$	$1:\underline{b}\succ \underline{c}\succ \underline{a}$;	$3:\underline{c}\succ \underline{b}\succ \underline{a}$
		$2:\underline{c}\succ \underline{a}\succ b$;

It is easy to check that a is elected in each of the seven profiles: through Rule 1ii in Profile 1, through Rule 2i in Profiles 2, 4, and 5, through Rule 2ii in Profiles 3, 6, and 7. When Profiles 1 and 2 are merged, b wins; this is also the case when Profiles 1 and 3 are merged. When Profiles 2 and 3 or Profiles 4 and 5 or Profiles 6 and 7 are merged, c wins. It follows from the profiles above that if a candidate wins with Rule 1 (1i or 1ii) in one group of voters and with Rule 2 (2i or 2ii) in another group, he may not win when both groups are merged. We reach the same conclusion if a candidate wins with Rule 2i in one group of voters and with Rule 2ii in an other group, or when a candidate wins through Rule 2i (resp. 2ii) in both groups of voters.

We can give a summary that reflects whether or not the criterion is met as follows:

		$N_2$
		Rule 1i	Rule 1ii	Rule 2i	Rule 2ii
$N_1$	Rule 1i	Yes	Yes	No	No
	Rule 1ii	Yes	Yes	No	No
	Rule 2i	No	No	No	No
	Rule 2ii	No	No	No	No

Thus, PAV always meets the criterion if the winner in each of the two groups of voters is determined by Rule 1i or Rule 1ii or both. In the other cases, PAV may fail the reinforcement condition.

1.1.2 FV and the reinforcement criterion

Assume that candidate a is the FV winner at level l in both groups $N_1$ and $N_2$. Let us denote by $S^{l}_{j}(a)$ the l-level score of a in group j ($j=1,2$). We distinguish two cases:

(i):

at l, a is the only majority-approved candidate in each group. This means for all other candidate b, we get $S^{l}_{1}(a)>\frac{n_{1}}{2}\ge S^{l}_{1}(b)$ and $S^{l}_{2}(a)>\frac{n_{2}}{2}\ge S^{l}_{2}(b)$. Consider the profile obtained when both populations are merged and assume that b wins at a given level r. It is obvious that we get a contradiction for $r\ge l$ since $S^{l}_{1}(a)+S^{l}_{2}(a)>\frac{n}{2}\ge S^{l}_{1}(b)+S^{l}_{2}(b)$. Since it is assumed that a is the only majority-approved candidate in each group at l, it follows that for all $r<l$, we get $S^{r}_{j}(a)\le \frac{n_{j}}{2}<S^{l}_{j}(a)$ and $S^{r}_{j}(b)\le S^{l}_{j}(b)\le \frac{n_{j}}{2}$. Therefore, when both groups are merged, it is impossible at level r for b to be majority-approved or to score more than a. So, if a is the only majority-approved candidate in each group at a given level l, he remains elected when both groups are merged.

(ii):

At l, a has the greatest score among the majority-approved candidates in each group. This means that $S^{l}_{1}(a)> S^{l}_{1}(b)>\frac{n_{1}}{2}\ge S^{l}_{1}(c)$ and $S^{l}_{2}(a)> S^{l}_{2}(b)>\frac{n_{2}}{2}\ge S^{l}_{2}(c)$. What we have in (i) implies that c can never win when the two groups merge.

To complete the proof, let us use some profiles to show that when the same FV winner is determined in two groups at two different levels, he may not remain elected when both groups merge.

Profile 1	Profile 2
$2:\underline{a}\succ \underline{b}\succ c$	$1:\underline{a}\succ \underline{b}\succ c$;	$1:\underline{b}\succ c\succ a$;
$1:\underline{a}\succ \underline{b}\succ c$	$2:\underline{a}\succ b\succ c$;	$1:\underline{c}\succ b\succ a$;
$2:\underline{b}\succ c\succ a$	$2:\underline{b}\succ \underline{a}\succ c$;

In Profile 1, a wins at the first level since $S^{1}(a)=3$, $S^{1}(b)=2$, and $S^{1}(c)=0$; he also wins with Profile 2 at level 2 since $S^{1}(a)=S^{1}(b)=3$, $S^{1}(c)=1$, $S^{2}(a)=5$, $S^{2}(b)=4$, and $S^{2}(c)=1$. When both profiles are merged, b wins since $S^{1}(a)=6$, $S^{1}(b)=5$, $S^{1}(c)=1$, $S^{2}(a)=8$, $S^{2}(b)=18$, and $S^{2}(c)=1$. So, FV may fail the reinforcement criterion when the winner in both groups is elected at two different levels of preferences.

1.2 Appendix 2: Proof of Proposition 10

1.2.1 PAV is vulnerable to the No-Show paradox only when the winner is determined by Rule 2i

It is known that AV is not vulnerable to the No-Show paradox (see Felsenthal, 2012); as Rule 1 of PAV is equivalent to AV, it follows that under Rule 1, PAV is not vulnerable to the No-Show paradox.

Consider a voting situation where candidate a is PAV winner. Assume a group of $\beta$ voters ($\beta \ge 1$) who decide to not show up in order to favor a more preferred candidate b. Obviously, if these voters do not approve of candidate a in the original profile, the maneuver is futile. Suppose now that these voters approve candidate a in the original profile. When they abstain, the AV score of each candidate they approved decreases by $\beta$. Let us discuss each of the possible configurations.

Consider the configuration where candidate a was the winner under Rule 2i. First, let us assume that b was not among the majority-approved candidates ($\textbf{AV}(b,\pi )<\frac{n}{2}$) and that he wins after abstention. After abstention, $\textbf{AV}(b,\pi )-\beta <\frac{n-\beta }{2}$; b cannot win if $\textbf{AV}(a,\pi )-\beta >\frac{n-\beta }{2}$; if $\textbf{AV}(b,\pi )-\beta <\frac{n-\beta }{2}$, b wins if $\textbf{AV}(b,\pi )-\beta >\textbf{AV}(a,\pi )-\beta$ which is equivalent to $\textbf{AV}(b,\pi )>\textbf{AV}(a,\pi )$: this contradicts $\textbf{AV}(a,\pi )>\frac{n}{2}$. So, it not possible to favor b. Let us now assume that b was among the majority-approved candidates ($\textbf{AV}(b,\pi )>\frac{n}{2}$) and that he wins after abstention. It is obvious after abstention that b cannot win if $\textbf{AV}(a,\pi )-\beta >\frac{n-\beta }{2}$. After abstention, if $\textbf{AV}(a,\pi )-\beta <\frac{n-\beta }{2}$, two cases are possible:

• If $\textbf{AV}(a,\pi )>\textbf{AV}(b,\pi )$, it is not possible to favor b; let us show how. Given $\textbf{AV}(a,\pi )>\textbf{AV}(b,\pi )$, if $\textbf{AV}(b,\pi )-\beta >\frac{n-\beta }{2}$ and b wins, this means that $\textbf{AV}(b,\pi )>\textbf{AV}(a,\pi )$; we get a contradiction. For $\textbf{AV}(b,\pi )-\beta <\frac{n-\beta }{2}$, b wins if $\textbf{AV}(b,\pi )-\beta >\textbf{AV}(a,\pi )-\beta$ which is tantamount to $\textbf{AV}(b,\pi )>\textbf{AV}(a,\pi )$: we get a contradiction.

• If $\textbf{AV}(a,\pi )<\textbf{AV}(b,\pi )$:

  • It is possible to favor b since it is possible to get $\textbf{AV}(b,\pi )-\beta >\frac{n-\beta }{2}$ such that b wins as illustrated by the following profile with three candidates and 19 voters.

    $$\begin{aligned}{} & {} 1:\underline{a}\succ b\succ c \quad \quad 6:\underline{b}\succ a\succ c\quad \quad 3:\underline{c}\succ a\succ b \\{} & {} 4:\underline{a}\succ \underline{b}\succ c\quad \quad 3:\underline{b}\succ \underline{a}\succ c\quad \quad 2:\underline{c}\succ \underline{a}\succ b \end{aligned}$$

    In this profile, $\textbf{AV}(a,\pi )=10$, $\textbf{AV}(b,\pi )=13$, and $\textbf{AV}(c,\pi )=5$. Candidates a and b are majority-approved, and a wins since $n_{ab}=10>n_{ba}=9$. Assume that the three voters with $\underline{b}\succ \underline{a}\succ c$ abstain. In the new profile $\pi '$ with 16 voters, the scores are $\textbf{AV}(a,\pi ')=7$, $\textbf{AV}(b,\pi ')=10$, and $\textbf{AV}(c,\pi ')=5$: b wins since he is now the only majority-approved candidate.

  • It is possible to favor b since it is possible to get $\textbf{AV}(b,\pi )-\beta <\frac{n-\beta }{2}$ such that b wins, as illustrated by the following profile with three candidates and 18 voters.

    $$\begin{aligned}{} & {} 1:\underline{a}\succ b\succ c\quad \quad 3:\underline{b}\succ a\succ c\quad \quad 5:\underline{c}\succ a\succ b \\{} & {} 4:\underline{a}\succ \underline{b}\succ c\quad \quad 4:\underline{b}\succ \underline{a}\succ c\quad \quad 1:\underline{c}\succ \underline{a}\succ b \end{aligned}$$

    In this profile, $\textbf{AV}(a,\pi )=10$, $\textbf{AV}(b,\pi )=11$, and $\textbf{AV}(c,\pi )=6$. Candidates a and b are majority-approved, and a wins since $n_{ab}=11>n_{ba}=7$. Assume that the four voters with $\underline{b}\succ \underline{a}\succ c$ abstain. In the new profile $\pi '$ with 14 voters, the scores are $\textbf{AV}(a,\pi ')=6$, $\textbf{AV}(b,\pi ')=7$, and $\textbf{AV}(c,\pi ')=6$: no candidate is majority-approved, then b wins since he gets the highest AV score.

Consider now the configuration where candidate a was the winner under Rule 2ii. If b was not among the majority-approved candidates, the same reasoning as above applies, and b cannot win after abstention. Let us assume that b was among the majority-approved candidates; as a wins, this means that he has the greatest AV scores among the majority-approved candidates ($\textbf{AV}(a,\pi )>\textbf{AV}(b,\pi )$). Candidate b may win after abstention if the new scores are such that $\frac{n-\beta }{2}<\textbf{AV}(a,\pi )-\beta <\textbf{AV}(b,\pi )-\beta$ or $\textbf{AV}(a,\pi )-\beta<\frac{n-\beta }{2}<\textbf{AV}(b,\pi )-\beta$; in each case, these conditions lead to $\textbf{AV}(a,\pi )<\textbf{AV}(b,\pi )$, which is a contradiction. Thus, PAV is vulnerable to the No-Show paradox only when the winner is determined by Rule 2i.

1.2.2 FV is not vulnerable to the No-Show paradox only when the winner is determined at level $l=1$ or $l=m$

When the FV winner is determined at $l=1$, any abstention of voters who do not rank this winner first does not affect the approval of the level $l=1$. So, for $l=1$, the No-Show paradox never occurs.

Let us assume that a is the FV winner at level $l=m$ and that a group of $\beta$ voters try to favor a more preferred candidate b by abstaining. Assume at $l=m$ that a is the only majority-approved candidate, which means that $S^{m}(a)>\frac{n}{2}>S^{m}(b)$; after abstention, we may get (i) $S^{m}(a)-\beta >\frac{n}{2}$ and $S^{m}(b)-\beta <\frac{n}{2}$ or (ii)$S^{m}(a)-\beta <\frac{n}{2}$ and $S^{m}(b)-\beta <\frac{n}{2}$. Candidate a remains the winner under (i); candidate b wins under (ii) if $S^{m}(a)-\beta <S^{m}(b)-\beta$ which is equivalent to $S^{m}(a)<S^{m}(b)$: this contradicts that a was the only majority-approved candidate. Let us now assume that a and b are among the majority-approved candidates; since a wins, this means that $S^{m}(a)>S^{m}(b)>\frac{n}{2}$. After truncation, we can get $S^{m}(a)-\beta>S^{m}(b)-\beta >\frac{n}{2}$ or $\frac{n}{2}>S^{m}(a)-\beta >S^{m}(b)-\beta$; in each case, b cannot be the winner. It follows that FV is not sensitive to the No-Show paradox when the winner is determined at level $l=1$ or $l=m$.

Now, let us assume that a is the FV winner at level l ($l\ne 1,m$) and consider the following profile with 12 voters and three candidates.

$$\begin{aligned}{} & {} 2:\underline{a}\succ b\succ c; \quad \quad 1:\underline{a}\succ \underline{c}\succ \underline{b};\\{} & {} 4:\underline{b}\succ \underline{a}\succ c; \quad \quad 2:\underline{b}\succ c\succ a;\\{} & {} 1:\underline{c}\succ \underline{a}\succ \underline{b}; \quad \quad 1:\underline{c}\succ \underline{b}\succ a;\\{} & {} 1:\underline{c}\succ b\succ a; \end{aligned}$$

With this profile, no candidate wins at $l=1$ since $S^{1}(a)=S^{1}(c)=3$ and $S^{1}(b)=6$; at $l=2$, $S^{2}(a)=8$, $S^{2}(b)=7$, and $S^{2}(c)=4$, candidate a wins. Assume that the four voters with $\underline{b}\succ \underline{a}\succ c$ abstain. In the new profile, we get $S^{1}(a)=S^{1}(c)=3$, $S^{1}(b)=2$ at $l=1$, and no one wins; $S^{2}(a)=S^{2}(c)=4$ and $S^{2}(b)=3$, and no one wins. At $l=3$, $S^{3}(a)=S^{3}(c)=4$ and $S^{3}(b)=5$, and b wins; by abstaining, the four voters have favored b, who is preferred to a. Thus, FV is vulnerable to the No-Show paradox when the winner is determined at level of approval $l\ne 1$ and $l\ne m$.

Since the vulnerability of a voting rule to the No-Show paradox leads to its vulnerability to the truncation paradox, FV and PAV would therefore be vulnerable to the truncation paradox. Preference truncation is efficient under FV and PAV only if it consists, as shown by Brams and Sanver (2009), in a contraction of the set of approved candidates.

1.3 Appendix 3: Details of the computational analysis

1.3.1 Preferences and the rules in three-candidate elections

We need to present the rankings and approvals in the particular case of three candidates. For the sake of simplicity, we rule out the possibilities of approving nothing; so, given his ranking, a voter may approve at least one candidate and at most all the running candidates. So, given $\mathcal {C}=\{a,b,c\}$, the 18 possible types of preferences on $\mathcal {C}$ are reported in Table 5. Then, a voting situation is the 18-tuple $\pi = (n_{1}, n_{2}, \ldots , n_{t}, \ldots , n_{18})$ such that $\sum _{t=1}^{18}n_{t}=n$.

Table 5 The 18 types of rankings and approvals on $\mathcal {C}=\{a,b,c\}$

Given the labels of Table 5, the approval scores $S^{l}(.)$ at level l are provided in Table 6; with three candidates, l varies from 1 to 3.

Table 6 The approval scores $S^{l}(.)$

Notice that $S^{3}(a)=\textbf{AV}(a,\pi )$. Candidate a is the AV winner if the conditions described by Eq. 1 are met.

$$\begin{aligned} \left\{ \begin{array}{lll} S^{3}(a) &{}>&{} S^{3}(b)\\ S^{3}(a) &{} >&{} S^{3}(c) \end{array} \right. \end{aligned}$$

(1)

Recall that $S^{1}(.)=\textbf{PR}(.,\pi )$. We provide in Table 7 the scores of the candidates under NPR and BR.¹⁷

Table 7 Scores of the candidates under NPR and BR

Given $\pi$, if candidate a is the FV winner, the following scenarios are possible:

• Candidate a is the only majority-approved candidate at $l=1$; this is fully described by Eq 2.

• No one wins at $l=1$, and a is the only candidate majority-approved at $l=2$. In this case, we get Eq 3.

• No one wins at $l=1$, and a with b (or c) are majority-approved at $l=2$; a gets more approvals than b (or c) at this stage. This situation is characterized by Eq 4 or Eq 5.

• No one wins at $l=1$, and a, b, and c are majority-approved at $l=2$. At this stage, a gets more approvals than b and c. In this case, we get Eq 6.

• There is no winner at both $l=1$ and $l=2$, and a is the only candidate who is majority-approved at $l=3$. This situation is characterized by Eq 7.

• There is no winner at $l=1$ and $l=2$: a with b (or c) are majority-approved at $l=3$. In this case, we get Eq. 8 or Eq 9.

• No candidate is majority-approved at $l=1,2$, but they are all majority-approved at $l=3$; a gets more approvals than b and c. This situation is characterized by Eq 10.

• No candidate is majority-approved at $l=1,2,3$, and a gets more approvals than b and c. This situation is characterized by Eq. 11.

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{1}(a) &{}>&{} \frac{n}{2} \\ S^{1}(b) &{}<&{} \frac{n}{2} \\ S^{1}(c) &{}<&{} \frac{n}{2} \end{array} \right. \end{aligned}$$

(2)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{1}(a) &{}<&{} \frac{n}{2} \\ S^{1}(b) &{}<&{} \frac{n}{2} \\ S^{1}(c) &{}<&{} \frac{n}{2}\\ S^{2}(a) &{}>&{} \frac{n}{2} \\ S^{2}(b) &{}<&{} \frac{n}{2} \\ S^{2}(c) &{}<&{} \frac{n}{2}\\ \end{array} \right. \end{aligned}$$

(3)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{1}(a) &{}<&{} \frac{n}{2} \\ S^{1}(b) &{}<&{} \frac{n}{2} \\ S^{1}(c) &{}<&{} \frac{n}{2}\\ S^{2}(b) &{}>&{} \frac{n}{2} \\ S^{2}(c) &{}<&{} \frac{n}{2}\\ S^{2}(a) &{}>&{} S^{2}(b) \end{array} \right. \end{aligned}$$

(4)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{1}(a) &{}<&{} \frac{n}{2} \\ S^{1}(b) &{}<&{} \frac{n}{2} \\ S^{1}(c) &{}<&{} \frac{n}{2}\\ S^{2}(b) &{}<&{} \frac{n}{2} \\ S^{2}(c) &{}>&{} \frac{n}{2}\\ S^{2}(a) &{}>&{} S^{2}(c) \end{array} \right. \end{aligned}$$

(5)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{1}(a) &{}<&{} \frac{n}{2} \\ S^{1}(b) &{}<&{} \frac{n}{2} \\ S^{1}(c) &{}<&{} \frac{n}{2}\\ S^{2}(b) &{}>&{} \frac{n}{2} \\ S^{2}(c) &{}>&{} \frac{n}{2}\\ S^{2}(a) &{}>&{} S^{2}(b)\\ S^{2}(a) &{}>&{} S^{2}(c) \end{array} \right. \end{aligned}$$

(6)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{1}(a) &{}<&{} \frac{n}{2} \\ S^{1}(b) &{}<&{} \frac{n}{2} \\ S^{1}(c) &{}<&{} \frac{n}{2}\\ S^{2}(a) &{}<&{} \frac{n}{2} \\ S^{2}(b) &{}<&{} \frac{n}{2} \\ S^{2}(c) &{}<&{} \frac{n}{2}\\ S^{3}(a) &{}>&{} \frac{n}{2} \\ S^{3}(b) &{}<&{} \frac{n}{2} \\ S^{3}(c) &{}<&{} \frac{n}{2} \end{array} \right. \end{aligned}$$

(7)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{1}(a) &{}<&{} \frac{n}{2} \\ S^{1}(b) &{}<&{} \frac{n}{2} \\ S^{1}(c) &{}<&{} \frac{n}{2}\\ S^{2}(a) &{}<&{} \frac{n}{2} \\ S^{2}(b) &{}<&{} \frac{n}{2} \\ S^{2}(c) &{}<&{} \frac{n}{2}\\ S^{3}(b) &{}>&{} \frac{n}{2} \\ S^{3}(c) &{}<&{} \frac{n}{2}\\ S^{3}(a) &{}>&{} S^{3}(b) \end{array} \right. \end{aligned}$$

(8)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{1}(a) &{}<&{} \frac{n}{2} \\ S^{1}(b) &{}<&{} \frac{n}{2} \\ S^{1}(c) &{}<&{} \frac{n}{2}\\ S^{2}(a) &{}<&{} \frac{n}{2} \\ S^{2}(b) &{}<&{} \frac{n}{2} \\ S^{2}(c) &{}<&{} \frac{n}{2}\\ S^{3}(b) &{}<&{} \frac{n}{2} \\ S^{3}(c) &{}>&{} \frac{n}{2}\\ S^{3}(a) &{}>&{} S^{3}(c) \end{array} \right. \end{aligned}$$

(9)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{1}(a) &{}<&{} \frac{n}{2} \\ S^{1}(b) &{}<&{} \frac{n}{2} \\ S^{1}(c) &{}<&{} \frac{n}{2}\\ S^{2}(a) &{}<&{} \frac{n}{2} \\ S^{2}(b) &{}<&{} \frac{n}{2} \\ S^{2}(c) &{}<&{} \frac{n}{2}\\ S^{3}(a) &{}>&{} \frac{n}{2} \\ S^{3}(a) &{}>&{} S^{3}(b) \\ S^{3}(a) &{}>&{} S^{3}(c) \end{array} \right. \end{aligned}$$

(10)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{1}(a) &{}<&{} \frac{n}{2} \\ S^{1}(b) &{}<&{} \frac{n}{2} \\ S^{1}(c) &{}<&{} \frac{n}{2}\\ S^{2}(a) &{}<&{} \frac{n}{2} \\ S^{2}(b) &{}<&{} \frac{n}{2} \\ S^{2}(c) &{}<&{} \frac{n}{2}\\ S^{3}(a) &{}<&{} \frac{n}{2} \\ S^{3}(a) &{}>&{} S^{3}(b) \\ S^{3}(a) &{}>&{} S^{3}(c) \end{array} \right. \end{aligned}$$

(11)

If we assume that candidate a is the PAV winner, the following five scenarios are possible:

• No candidate gets a majority of approvals, and a gets the highest number of approvals; this is fully described by Eq. 12.

• Only a gets a majority of approvals; in this case, we get Eq. 13.

• Candidates a and b (or c) get a majority of approvals, and a is majority-preferred to b (or to c); this leads to Eq. 14 (or Eq. 15).

• All three candidates get a majority of approvals, and a majority dominates b and c; this is described by Eq. 16.

• All three candidates get a majority of approvals, there is a majority cycle, and a gets the highest number of approvals; we thus get Eq. 17 or 18.

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{3}(a) &{}<&{} \frac{n}{2} \\ S^{3}(a) &{}>&{} S^{3}(b) \\ S^{3}(a) &{}>&{} S^{3}(c) \end{array} \right. \end{aligned}$$

(12)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{3}(a) &{}>&{} \frac{n}{2} \\ S^{3}(b) &{}<&{} \frac{n}{2}\\ S^{3}(c) &{}<&{} \frac{n}{2} \end{array} \right. \end{aligned}$$

(13)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{3}(a) &{}>&{} \frac{n}{2} \\ S^{3}(b) &{}>&{} \frac{n}{2}\\ S^{3}(c) &{}<&{} \frac{n}{2}\\ n_{ab} &{}>&{} n_{ba} \end{array} \right. \end{aligned}$$

(14)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{3}(a) &{}>&{} \frac{n}{2} \\ S^{3}(b) &{}<&{} \frac{n}{2}\\ S^{3}(c) &{}>&{} \frac{n}{2}\\ n_{ac} &{}>&{} n_{ca} \end{array} \right. \end{aligned}$$

(15)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{3}(a) &{}>&{} \frac{n}{2} \\ S^{3}(b) &{}>&{} \frac{n}{2}\\ S^{3}(c) &{}>&{} \frac{n}{2}\\ n_{ab} &{}>&{} n_{ba} \\ n_{ac} &{}>&{} n_{ca} \end{array} \right. \end{aligned}$$

(16)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{3}(a) &{}>&{} S^{3}(b) \\ S^{3}(a) &{}>&{} S^{3}(c)\\ S^{3}(b) &{}>&{} \frac{n}{2}\\ S^{3}(c) &{}>&{} \frac{n}{2}\\ n_{ab} &{}>&{} n_{ba} \\ n_{bc} &{}>&{} n_{cb}\\ n_{ca} &{}>&{} n_{ac} \end{array} \right. \end{aligned}$$

(17)

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} S^{3}(a) &{}>&{} S^{3}(b) \\ S^{3}(a) &{}>&{} S^{3}(c)\\ S^{3}(b) &{}>&{} \frac{n}{2}\\ S^{3}(c) &{}>&{} \frac{n}{2}\\ n_{ba} &{}>&{} n_{ab} \\ n_{ac} &{}>&{} n_{ca}\\ n_{cb} &{}>&{} n_{bc}\\ \end{array} \right. \end{aligned}$$

(18)

1.3.2 The impartial and anonymous culture assumption

When computing the likelihood of voting events, the impartial and anonymous culture (IAC) assumption introduced by Kuga and Nagatani (1974) and Gehrlein and Fishburn (1976) is one of the most widely used assumptions in social choice theory literature. Under this assumption, all voting situations are equally likely to be observed; it follows that the probability of a given event is calculated according to the ratio between the number of voting situations in which the event occurs and the total number of possible voting situations. For a given voting event, the number of voting situations can be reduced to the solutions of a finite system of linear constraints with rational coefficients. The appropriate mathematical tools to find these solutions are the Ehrhart polynomials.

For a non-exhaustive overview of these techniques and algorithms, we refer to the recent books by Diss and Merlin (2021) and Gehrlein and Lepelley (2011), Gehrlein and Lepelley (2017). As in this paper we deal with situations where the number of voters tends to infinity, finding the limiting probabilities under IAC is reduced to the computation of volumes of convex polytopes (Bruns & Söger, 2015; Schürmann, 2013). For our computations, we use the software Normaliz (Bruns & Ichim, 2021; Bruns et al., 2019),¹⁸ It should be noted that the calculations are relatively simple to implement under Normaliz because it is sufficient to enter the conditions describing an event, and the algorithm returns the volume of the corresponding polytope which is the probability of this event.

1.3.3 Agreement between the rules

First of all, let us look at situations where two rules coincide. Let us take the case where FV and AV agree on candidate a as the winner. We denote by $P(AV=FV=a)$ the limiting probability of this event. This probability is in fact equal to a sum of volumes of polytopes to take into account the different scenarios that can occur under FV as described above. For example, the case where the winner of AV is the same as the winner of FV at level $l=1$ is described by the inequalities of Eq. 1 and 2; we denote this volume obtained by $\mathcal {V}_{1\cap 2}(\pi )$. In a similar way, we determine the volumes $\mathcal {V}_{1\cap j}(\pi )$ for $j=3, 4,\ldots , 11$. Thus, we obtain

$$\begin{aligned} P(AV=FV=a)= & {} \sum \limits ^{11}_{j=2} \mathcal {V}_{1\cap j}(\pi )\\= & {} \frac{3864518350115}{15850845241344} \end{aligned}$$

We can therefore deduce $\mathcal {P}(FV=AV)$, the probability of agreement between AV and FV, as follows

$$\begin{aligned} \mathcal {P}(FV=AV)=3P(FV=AV=a)=\frac{3864518350115}{5283615080448} \end{aligned}$$

Note that the calculation of $(FV=PAV=a)$ requires us to review $7\times 10=70$ possible configurations; among these configurations, only 29 are possible because of the incompatibilities between the conditions. Proceeding in a similar way and including the scoring rules in our analysis, we obtain

$$\begin{aligned} \mathcal {P}(FV= & {} PAV)=\frac{20645280898898557}{28682781685383168}; \quad \quad \mathcal {P}(PAV=AV)=\frac{405549109}{603979776}; \\ \mathcal {P}(FV= & {} PR)=\frac{858426742033860211}{1299967445355724800}; \quad \quad \mathcal {P}(PAV=PR)=\frac{15393646886073191531}{19258776968232960000}; \\ \mathcal {P}(FV= & {} NPR)=\frac{29078653154282273}{41085390865563648}; \quad \quad \mathcal {P}(PAV=NPR)=\frac{3367171932047414983}{5135673858195456000}; \\ \mathcal {P}(FV= & {} BR)=\frac{356641532074024159}{462316319539200000}; \quad \quad \mathcal {P}(PAV=BR)=\frac{2966266305301241}{3424565329920000}; \\ \mathcal {P}(AV= & {} PR)=\frac{590913882103}{979552051200}; \quad \quad \mathcal {P}(AV=BR)=\frac{23515466951}{36578304000}; \\ \mathcal {P}(AV= & {} NPR)=\frac{5661560137}{9795520512}; \quad \quad \mathcal {P}(NPR=BR)=\frac{20645280898898557}{28682781685383168}; \\ \mathcal {P}(PR= & {} BR)=\frac{54057569}{68024448}; \quad \quad \mathcal {P}(PR=NPR)=\frac{4615849949}{8707129344}; \\ \end{aligned}$$

We summarize our results in Table 2.

Using the same approach as above, we were able to determine $\mathcal {P}(FV=AV=PAV)$, the limiting probability that AV, FV, and PAV agree on the same profile.

$$\begin{aligned} \mathcal {P}(FV=AV=PAV)=\frac{38878305102793}{66045188505600}\approx 0.5886621870 \end{aligned}$$

1.3.4 FV and PAV may pick the least-approved candidate

Let us now look at the cases where FV and PAV can elect the least-approved candidate. Let us assume on $\pi$ that candidate a is the least approved; this leads to Eq. 19.

$$\begin{aligned} \left\{ \begin{array}{lll} S^{3}(a) &{}<&{} S^{3}(b)\\ S^{3}(a) &{} <&{} S^{3}(c) \end{array} \right. \end{aligned}$$

(19)

As pointed out by Brams and Sanver (2009), a least-approved candidate may be a PAV winner under Rule 2i; in our framework, this event is fully characterized by the inequalities of Eq. 15 and 19. We then need to compute the volume $\mathcal {V}_{15\cap 19}(\pi )$ that we multiply by 3 to find $\mathcal {P}(PAV=LAV)$, the limiting probability that PAV elects the least-approved candidate as follows:

$$\begin{aligned} \mathcal {P}(PAV=LAV)=3\mathcal {V}_{15\cap 19}(\pi )=\frac{6095207}{75497472}\approx 0.0807339 \end{aligned}$$

So, it is thus in nearly $8.07\%$ of cases that PAV can lead to the election of the least-approved candidate. What about FV? Since at level $l=m$, $S^{l}(.)$ is equal to the AV score, it is obvious that FV cannot elect the least-approved candidate at this level. It follows then that with three candidates, FV can elect the least-approved candidate only at $l=1$ or $l=2$; this corresponds to Eq. 2 to 6. Thus, $\mathcal {P}(FV=LAV)$, the limiting probability that FV elects the least-approved candidate, is computed as follows:

$$\begin{aligned} \mathcal {P}(FV=LAV)= & {} 3\left (\sum \limits ^{6}_{j=2}\mathcal {V}_{19\cap j}(\pi )\right ) \\= & {} \frac{262005663203}{5283615080448}\approx 0.04958833 \end{aligned}$$

1.3.5 A unanimously approved candidate may not win under FV or PAV

As Brams and Sanver (2009) note, there may be times when FV and PAV do not elect a unanimously approved candidate. This marks another point of dissonance between these rules and AV. By definition, this can only occur with PAV under Rule 2i. Let us assume on $\mathcal {C}=\{a,b,c\}$ that b is unanimously approved. In our framework, this is tantamount to

$$\begin{aligned} n_{1}+n_{2}+n_{5}+n_{6}+n_{8}+n_{11}=0 \end{aligned}$$

(20)

If b and c are both unanimously approved, we get

$$\begin{aligned} n_{10}+n_{12}+n_{13}+n_{14}+n_{15}+n_{16}+n_{17}+n_{18}=n \end{aligned}$$

(21)

Given Eq. 20, situations where a is the PAV winner while b (resp. c) is unanimously approved occur when Eq. 14 or 16 (resp. Equation 15 or 16) hold. The case where both b and c are unanimously approved while a is the PAV winner can only occur if Eq. 16 holds. Then, $\mathcal {P}(PAV\ne Uap)$, the limiting probability that PAV fails to elect a unanimously approved candidate, is computed as follows:

$$\begin{aligned} \mathcal {P}(PAV\ne Uap)= & {} 3\bigg [2\bigg (\mathcal {V}_{20\cap 14}(\pi )+\mathcal {V}_{20\cap 16}(\pi )\bigg )-\mathcal {V}_{21\cap 16}(\pi )\bigg ] \\= & {} 3\bigg [2\bigg (\frac{5}{512}+\frac{313}{4096}\bigg )-\frac{7}{64}\bigg ] \\= & {} \frac{387}{2048}\approx 0.1889648 \end{aligned}$$

FV may fail to pick a unanimously approved candidate when Eq. 2 or 4 or 5 or 6 holds. Then, $\mathcal {P}(FV\ne Uap)$, the limiting probability that FV fails to elect a unanimously approved candidate, is computed as follows:¹⁹

$$\begin{aligned} \mathcal {P}(FV\ne Uap)= & {} 3\bigg (2\sum \limits ^{6}_{j=2}\mathcal {V}_{20\cap j}(\pi )-\sum \limits ^{6}_{j=2}\mathcal {V}_{21\cap j}(\pi )\bigg ) \\= & {} 3\bigg [2\bigg (\frac{67}{2048}+0+\frac{2573}{262144}+\frac{3}{2048}+\frac{36212845}{1719926784}\bigg )\\{} & {} -\bigg (\frac{1}{16}+0+\frac{9}{2048}+\frac{9}{2048}+\frac{5635}{186624}\bigg )\bigg ] \\= & {} \frac{12304397}{143327232}\approx 0.08584828 \end{aligned}$$

From the above, we note that in almost $18.89\%$ of the cases, PAV may not elect a unanimously approved candidate, while this is the case in only $8.58\%$ of the cases for FV.

1.3.6 The election of the Condorcet winner

Recall that candidate a is the Condorcet winner if he is majority-preferred to both b and c; using our notation, this is equivalent to Eq. 22.

$$\begin{aligned} \left\{ \begin{array}{lll} n_{ab} &{}>&{} n_{ba} \\ n_{ac} &{}>&{} n_{ca} \\ \end{array} \right. \end{aligned}$$

(22)

Using the conditions of Eq. 22, Normaliz gives us the probability $P(a=CW)$ that a is the winner of Condorcet over $\pi$.

$$\begin{aligned} P(a=CW)=\frac{20129}{65536} \end{aligned}$$

In the same way, we determined the probability that a is the absolute Condorcet winner (i.e., $S^{1}(a)>\frac{n}{2}$):

$$\begin{aligned} P(a=ACW)=\frac{4701}{65536} \end{aligned}$$

We therefore deduce $\mathcal {P}(CW)$, the existence probability of the Condorcet winner, and $\mathcal {P}(ACW)$, that of the absolute Condorcet winner:

$$\begin{aligned} \mathcal {P}(CW)= & {} 3P(a=CW)=\frac{60387}{65536}\approx 0.9214325 \\ \mathcal {P}(ACW)= & {} 3P(a=ACW)=\frac{14103}{65536}\approx 0.2151947 \end{aligned}$$

To determine $\mathcal{C}\mathcal{E}(R)$ the Condorcet efficiency of a given rule R, the methodology is the following: we determine the volume of the polytope describing the situation in which a is the Condorcet winner and the winner of R; this volume will then be divided by $P(a=CW)$ to obtain the desired probability. This procedure allows us to obtain

$$\begin{aligned} \mathcal{C}\mathcal{E}(AV)= & {} \frac{7491383}{11594304}; \quad \quad \mathcal{C}\mathcal{E}(PAV)=\frac{69380155}{226492416};\\ \mathcal{C}\mathcal{E}(FV)= & {} \frac{77089920161}{330225942528}; \quad \quad \mathcal{C}\mathcal{E}(BR)=\frac{39814829}{44022123};\\ \mathcal{C}\mathcal{E}(PR)= & {} \frac{8906796973}{10697375889}; \quad \quad \mathcal{C}\mathcal{E}(NPR)=\frac{14904579328717}{21908225820672}; \end{aligned}$$

Proceeding as in the case of the Condorcet efficiency, we determine $\mathcal {ACE}(R)$, the probability that the rule R elects the absolute Condorcet winner when he exists. It is known that PR always elects the absolute Condorcet winner when he exists. Following Proposition 2, this is also the case for FV and PAV; so $\mathcal {ACE}(PR)=\mathcal {ACE}(FV)=\mathcal {ACE}(PAV)=1$. For the other rules, we get

$$\begin{aligned} \mathcal {ACE}(AV)=\frac{13158985}{16246656}; \quad \quad \mathcal {ACE}(NPR)=\frac{700614205919}{959348790144}; \quad \quad \mathcal {ACE}(BR)=\frac{10223639}{10281087}; \end{aligned}$$

The second and fourth columns of Table 3 allow a better visualization of the results obtained in terms of (absolute) Condorcet efficiency.

To refine the comparisons, we assess how each of the above probabilities reacts to the proportion $\alpha =\frac{n_{1}+n_{2}+n_{3}+n_{4}+n_{5}+n_{6}}{n}$ of voters who approve only one candidate. For some values of $\alpha$, we report in Table 4 the probabilities $\mathcal{C}\mathcal{E}(R,\alpha )$, $\mathcal {ACE}(R,\alpha )$, $\mathcal{C}\mathcal{L}(R,\alpha )$, and $\mathcal {ACL}(R,\alpha )$ as functions of $\alpha$.

1.3.7 The election of the Condorcet loser

Let us assume on $\mathcal {C}=\{a,b,c\}$ that a is the Condorcet loser (resp. the absolute Condorcet loser); using the labels of Table 5, this is equivalent to Eq. 23 (resp. Equation 24).

$$\begin{aligned}{} & {} \left\{ \begin{array}{lll} n_{ab} &{}<&{} n_{ba} \\ n_{ac} &{}<&{} n_{ca} \end{array} \right. \end{aligned}$$

(23)

$$\begin{aligned}{} & {} \textbf{NPR}(a,\pi ) > \frac{n}{2} \end{aligned}$$

(24)

For our voting situations with three candidates, $\mathcal {P}(CL)$, the existence probability of the Condorcet loser and $\mathcal {P}(ACL)$ that of the absolute Condorcet loser, are as follows: $\mathcal {P}(CL)=\mathcal {P}(CW)$ and $\mathcal {P}(ACL)=\mathcal {P}(ACW)$.

We know from Proposition 3 that FV and PAV may elect the (absolute) Condorcet loser when he exists. When a voting rule may elect a Condorcet loser (resp. an absolute Condorcet loser), it is said to be vulnerable to the Borda paradox (resp. to the absolute majority loser paradox). By definition, an (absolute) Condorcet loser, when he exists, can never be elected under Rule 2 of PAV; this can only be the case under Rule 1. With FV, the Condorcet loser cannot be elected at level $l=1$, and the absolute Condorcet loser can only be elected at level $l=3$. We follow the same methodology as for the Condorcet winner efficiency to determine $\mathcal{C}\mathcal{L}(.)$ (resp. $\mathcal {ACL}(.))$, the limiting probability of electing the Condorcet loser (resp. the absolute Condorcet loser) when he exists. From our computations, we get²⁰:

$$\begin{aligned} \mathcal{C}\mathcal{L}(AV)= & {} \frac{1041839}{11594304}; \quad \quad \mathcal {ACL}(AV)=\frac{476761}{16246656};\\ \mathcal{C}\mathcal{L}(FV)= & {} \frac{1016677891}{110075314176}; \quad \quad \mathcal {ACL}(FV)=\frac{10859}{97479936};\\ \mathcal{C}\mathcal{L}(PAV)= & {} \frac{14311}{452984832}; \quad \quad \mathcal {ACL}(PAV)=\frac{809}{32493312};\\ \mathcal{C}\mathcal{L}(PR)= & {} \frac{364069916}{10697375889}; \quad \quad \mathcal {ACL}(PR)=\frac{104603503}{7494912423};\\ \mathcal{C}\mathcal{L}(NPR)= & {} \frac{787367474789}{21908225820672}; \end{aligned}$$

We were willing, as we did in the previous section, to refine our findings based on $\alpha$, the proportion of voters who approve of exactly one candidate. The probabilities $\mathcal{C}\mathcal{L}(R,\alpha )$ and $\mathcal {ACL}(R,\alpha )$ that we obtained in this regard are provided in Table 4.