Analyzing the Practical Relevance of the Condorcet Loser Paradox and the Agenda Contraction Paradox

Abstract

A large part of the social choice literature studies voting paradoxes in which seemingly mild properties are violated by common voting rules. In this chapter, we investigate the likelihood of the Condorcet Loser Paradox (CLP) and the Agenda Contraction Paradox (ACP) using Ehrhart theory, computer simulations, and empirical data. We present the first analytical results for the CLP on four alternatives and show that our experimental results, which go well beyond four alternatives, are in almost perfect congruence with the analytical results. It turns out that the CLP—which is often cited as a major flaw of some Condorcet extensions such as Dodgson’s rule, Young’s rule, and MaxiMin—is of no practical relevance. The ACP, on the other hand, frequently occurs under various distributional assumptions about the voters’ preferences. The extent to which it is real threat, however, strongly depends on the voting rule, the underlying distribution of preferences, and, somewhat surprisingly, the parity of the number of voters.

1 Introduction

A large part of the social choice literature studies voting paradoxes in which seemingly mild properties are violated by common voting rules. Moreover, there are a number of sweeping impossibilities, which entail that there exists no “optimal” voting rule that avoids all paradoxes. As a consequence, much of the research in social choice theory is concerned with whether a paradox can appear for a given voting rule or not. However, it turns out that some paradoxes—while possible in principle—will almost never appear in practice.

An extreme example of this phenomenon occurred for the voting rule $TEQ$ (Schwartz 1990). Due to its unwieldy recursive definition, it was unknown for more than 20 years whether $TEQ$ satisfies any of a number of very basic desirable properties. In 2013, Brandt et al. (2013) have shown that $TEQ$ violates all of these properties. However, their proof is non-constructive and only shows the existence of astronomically large counterexamples requiring about $10^{136}$ alternatives. While smaller computer-generated counterexamples exist, extensive simulations have shown that these counterexamples are extremely rare and that $TEQ$ satisfies the desirable properties for all practical purposes (Brandt et al. 2010). These findings motivated us to provide analytical, experimental, and empirical justifications for such statements.

In this chapter, we study two voting paradoxes. The first is the well-known Condorcet loser paradox (CLP), which occurs when a voting rule selects the Condorcet loser, an alternative that loses against every other alternative in pairwise majority contests. Perhaps surprisingly, this paradox affects some Condorcet extensions, i.e., voting rules that are guaranteed to select an alternative that wins against every other alternative in pairwise majority contests. Common affected Condorcet extensions are Dodgson’s rule, Young’s rule, and MaxiMin (Fishburn 1977). The second paradox, called agenda contraction paradox (ACP), occurs when removing losing alternatives changes the set of winners. There are only few voting rules that do not suffer from this paradox, one of them being the essential set (Dutta and Laslier 1999). In fact, all common voting rules that violate the CLP also violate the ACP.

In principle, quantitative results on voting paradoxes can be obtained via three different approaches. The analytical approach uses theoretical models to quantify paradoxes based on certain assumptions about the voters’ preferences. Analytical results usually tend to be quite hard to obtain and are limited to simple—and often unrealistic—assumptions. The experimental approach uses computer simulations based on underlying stochastic models of how the preference profiles are distributed. Experimental results have less general validity than analytical results, but can be obtained for arbitrary distributions of preferences. Finally, the empirical approach is based on evaluating real-world data to analyze how frequently paradoxes actually occur or how frequently they would have occurred if certain voting rules had been used for the given preferences. Unfortunately, only very limited real-world data for elections is available.

Our main results are as follows.

Using Ehrhart theory, we compute upper bounds for the CLP as well as the exact probabilities under which the CLP occurs for MaxiMin when there are four alternatives and preferences are distributed according to the Impartial Anonymous Culture (IAC) distribution. This approach also yields the exact limit probabilities (for the CLP and the ACP) when the number of voters goes to infinity. To the best of our knowledge, these are the first analytical results for the CLP on four alternatives (which is the minimal number of alternatives for which the voting rules we consider exhibit the CLP).

For both the CLP and the ACP, we throughly analyze a variety of other settings with more alternatives and other stochastic preference models using computer simulations. For those settings in which the analytical approach is also feasible, our results are in almost perfect congruence with the analytical results. This is strong evidence for the accuracy of our simulation results.

It turns out that the CLP—which is often cited as a major flaw of some Condorcet extensions —is of no practical relevance. The maximum probability under all preference models we studied is $2.2\%$ (for MaxiMin, three voters, four alternatives, and IAC). In more realistic settings, it is much lower. For Dodgson’s rule, it never exceeds $0.01\%$. We did not find any occurrence of the paradox in real-world data, neither in the PrefLib library (Mattei and Walsh 2013) nor in millions of elections based on data from the Netflix Prize (Bennett and Lanning 2007).

The ACP, on the other hand, frequently occurs under various distributional assumptions about the voters’ preferences. The extent to which it is real threat, however, strongly depends on the voting rule, the underlying distribution of preferences, and the parity of the number of voters. If the number of voters is much larger than the number of alternatives, less discriminating voting rules seem to fare better than more discriminating ones. For example, when there are 1,000 voters and four alternatives, the probability for the ACP under Copeland’s rule and IAC is $9\%$ while it occurs with a probability of $33\%$ for Borda’s rule. When there are fewer voters, the parity of the number of voters plays a surprisingly strong role. For example, if there are 6 alternatives, the ACP probability for Copeland’s rule is $44\%$ for 50 voters, but only $26\%$ for 51 voters. These results are in line with the empirical data we analyzed.

2 Related Work

There is a huge body of research on the quantitive study of voting paradoxes. Gehrlein (2006) focusses on the non-existence of Condorcet winners, arguably the most studied voting paradox. An overview of many paradoxes with an analysis of group coherence is provided by Gehrlein and Lepelley (2011). On top of that, Gehrlein and Lepelley (2011, 2017) survey different tools and techniques that have been applied over the years for the quantitive study of voting paradoxes.

The analytical study of voting paradoxes under the assumption of IAC is most effectively done via Ehrhart theory, which goes back to the year 1962 and the French mathematician Eugène Ehrhart (Ehrhart 1962). Interestingly, parts of these results have been reinvented (in the context of social choice) by Huang and Chua (2000), before Ehrhart ’s original work was independently rediscovered for social choice by Wilson and Pritchard (2007) and Lepelley et al. (2008) more than forty years later.

Current research on the probability of voting paradoxes under IAC is based on algorithms that build upon Ehrhart’s results, such as the algorithm developed by Barvinok (1994). For many years, these approaches were limited to cases with three or fewer alternatives. Recent advances in software tools and mathematical modeling enabled the study of elections with four alternatives. Bruns and Söger (2015) and Schürmann (2013) provide such results for Condorcet’s paradox, the Condorcet efficiency of plurality and the similarity between plurality and plurality with runoff. Schürmann (2013) further shows how symmetries in the formulation of the paradoxes can be exploited to facilitate the corresponding computations. Finally, Bruns et al. (2019b) study Condorcet and Borda paradoxes, as well as the Condorcet efficiency of plurality voting with runoff.

For the CLP (sometimes also referred to as “Borda’s paradox”) many quantitive results are known (Gehrlein and Lepelley 2011; Diss and Gehrlein 2012), which are, however, limited to simple voting rules and scoring rules in particular. These results also include some empirical evidence for the paradox under plurality (Gehrlein and Lepelley 2011, p. 15) and suggest that it is an unlikely yet possible problem in practice. Interestingly, the CLP for Condorcet extensions has—to the best of our knowledge—only been considered by Plassmann and Tideman (2014). However, they restrict their analysis to the 3-alternative case and find that the CLP never occurs, which is unsurprising since provably four alternatives are required for the Condorcet extensions they considered. In a more recent work, Bubboloni et al. (2019) consider the probability of the CLP for extensions of MaxiMin to the committee selection setting.

The ACP appears to have received less attention in the quantitative literature on voting paradoxes. Some limit probabilities for scoring rules were obtained by Gehrlein and Fishburn (see Gehrlein and Lepelley 2011, pp. 282–284). Fishburn (1974) experimentally studied a variant of this paradox called “winner turns loser paradox” for Borda’s rule under Impartial Culture. For Condorcet extensions, Plassmann and Tideman (2014) considered another variant of the ACP under a spatial model, but again limit their experiments to three alternatives. These few results already seem to indicate that the ACP might occur even under realistic assumptions. However, there are no results for more than three alternatives, Condorcet extensions, and the ACP in its full generality.

3 Models and Definitions

Let A be a set of m alternatives and $N = \{1, \ldots , n\}$ a set of voters. Each voter is equipped with a (strict) preference relation $\succ _i$, i.e., a complete, transitive, and asymmetric binary relation on A. We read $x \succ _i y$ as voter i (strictly) preferring alternative x to alternative y.

A (preference) profile (or an election) is an n-tuple of preference relations and will be denoted by $R:=({\succ _1}, \ldots , {\succ _{n}})$. We will sometimes consider the restriction of $\succ _i$ to a subset of alternatives $B\subseteq A$, called an agenda. Such a restriction will be denoted by $R|_B:=({\succ _1}|_B, \ldots , {\succ _{n}}|_B)$.

3.1 Stochastic Preference Models

In this chapter we consider five of the most common stochastic preference models. These models vary in their degree of realism. Impartial culture (IC) and impartial anonymous culture (IAC), for example, are usually considered as rather unrealistic. However, the simplicity of these models enables the use of analytical tools that cannot be applied to the other models. IC and IAC typically yield higher probabilities for paradoxes than other preference models and can therefore be seen as worst-case estimates (see, e.g., Regenwetter et al. 2006). We only give informal definitions here; for more extensive treatments see, e.g., Critchlow et al. (1991) and Marden (1995).

Impartial culture. The most widely-studied distribution is the so-called impartial culture (IC), under which every possible preference relation has the same probability of $\frac{1}{m!}$. Thus, every preference profile is equally likely to occur.

Impartial anonymous culture. In contrast to IC the impartial anonymous culture (IAC) is not based on the probabilities of individual preferences but on the probabilities of whole profiles. Under IAC one assumes that each possible anonymous preference profile on n voters is equally likely to occur. A more formal definition is given in Sect. 4.1.

Mallows-$\phi$ model. In Mallows-$\phi$ model, the distance to a reference ranking (or ground truth) is measured by means of the Kendall-tau distance¹ and a parameter $\phi$ is used to indicate the dispersion. The case of $\phi =1$ means absolute dispersion and coincides with IC, the case $\phi =0$ corresponds to no dispersion and every voter always picks the “true” ranking. We chose $\phi =0.8$ to simulate voters with relatively bad estimates, which leads to situations in which paradoxes are more likely to occur.

Pólya-Eggenberger urn model. In the Pólya-Eggenberger urn model, each possible preference relation is represented by a ball in an urn from which individual preferences are drawn. After each draw, the chosen ball is put back and $\alpha \in \mathbb {N}_0$ new balls of the same kind are added to the urn. While the urn model subsumes both impartial culture ($\alpha =0$) and impartial anonymous culture ($\alpha =1$), we set $\alpha =10$ to obtain a reasonably realistic interdependence of individual preferences.

Spatial model. In the spatial model alternatives and agents are placed in a multi-dimensional space uniformly at random and the agents’ preferences are then determined by the Euclidean distances to the alternatives (closer alternatives are preferred to more distant ones). The spatial model is considered particularly realistic in political science where the dimensions are interpreted as different aspects of the alternatives (Tideman and Plassmann 2012). We chose the simple case of two dimensions for our analysis.²

3.2 Voting Rules

A voting rule is a function f that maps a preference profile to a non-empty set of winners. For a preference profile R, let $g_{xy} := |\{i\in N:x \succ _i y\}| - |\{i\in N:y \succ _i x\}|$ denote the majority margin of x against y. A very influential concept in social choice is the notion of a Condorcet winner, an alternative that wins against any other alternative in a pairwise majority contest. Alternative x is a Condorcet winner (CW) of a profile R if $g_{xy}>0$ for all $y \in A\setminus \{x\}$. Conversely, alternative x is a Condorcet loser (CL) if $g_{yx}>0$ for all $y \in A\setminus \{x\}$. Neither CWs nor CLs necessarily exist, but whenever they do they are unique. A voting rule f is called a Condorcet extension if $f(R)=\{x\}$ whenever x is the CW in R.

In the following paragraphs we briefly introduce the voting rules considered in this chapter.

Borda’s Rule. Under Borda’s rule each alternative receives from 0 to $|A| - 1$ points from each voter (depending on the position the alternative is ranked in). The alternatives with highest accumulated score win.

MaxiMin. The MaxiMin rule is only concerned with the highest defeat of each alternative in a pairwise majority contest. It yields all alternatives x which have the maximal value of $\min _{y \in A} g_{xy}$.

Young’s Rule. Young’s rule yields all alternatives that can be made a CW by removing a minimal number of voters.

Dodgson’s Rule. Dodgson’s rule selects all alternatives that can be made a CW by a minimal number of pairwise swaps of adjacent alternatives in the individual preference relations.

Tideman’s Rule. Tideman’s rule was introduced as an approximation of Dodgson’s rule by Tideman (1987). It yields all alternatives x for which the sum of pairwise majority defeats $\sum _{y \in A} \max (0,g_{yx})$ is minimal.

Copeland’s Rule. Copelands’s rule selects all alternatives where the number of majority wins plus half the number of majority draws is maximal.

Essential Set. Consider the symmetric two-player zero-sum game G given by the skew-symmetric matrix with entries $g_{xy}$ for all pairs of alternatives x, y. The essential set is the set of all alternatives that are played with positive probability in some mixed Nash equilibrium of G.³

Except for Borda’s rule, all presented voting rules are in fact Condorcet extensions. While Borda’s rule, MaxiMin, and the essential set can be computed efficiently, Young’s rule and Dodgson’s rule have been shown to be computationally intractable. The essential set is one of the few voting rules that do suffer from neither the CLP nor the ACP, and is merely included as a reference. For more formal definitions and computational properties of these rules, we refer to Brandt et al. (2016).

3.3 Voting Paradoxes

In this chapter we focus on two voting paradoxes whose occurrence can be determined given a voting rule f and a preference profile R.

Let f be a voting rule. Formally, a (voting) paradox is a characteristic function that maps a preference profile to 0 or 1. In the latter case, we say the paradox occurs for voting rule f at profile R.

The Condorcet Loser Paradox (CLP) occurs when a voting rule selects the CL as a winner.

Definition 1

Given a voting rule f the Condorcet loser paradox CLP$_f$ is defined as

$$ \text {CLP}_f(R)= {\left\{ \begin{array}{ll} 1 &{} \text {if }f(R) \text { contains a CL} \\ 0 &{} \text {otherwise}. \end{array}\right. } $$

The agenda contraction paradox (ACP) occurs when reducing the set of alternatives, by eliminating unchosen alternatives, influences the outcome of an election.

Definition 2

Given a voting rule f the agenda contraction paradox ACP$_f$ is a paradox defined as

$$ \text {ACP}_f(R)= {\left\{ \begin{array}{ll} 1 &{} \text {if } f(R|_B) \ne f(R)\text { for some }B \supseteq f(R) \\ 0 &{} \text {otherwise}. \end{array}\right. } $$

4 Quantifying Voting Paradoxes

In this section we present the three general approaches for quantifying voting paradoxes: the analytical approach via Ehrhart theory, the experimental approach via computer simulations, and the empirical approach via real-world data.

4.1 Exact Analysis via Ehrhart Theory

Anonymous preference profiles only count the number of voters for each of the m! possible rankings on m alternatives. An anonymous preference profile can hence be viewed as an integer point in a space of $d:=m!$ dimensions. Formally, the set $S_{m,n}$ of anonymous preference profiles on m alternatives with n voters can be identified with the set of all integer points $z = (z_1, \ldots , z_{m!}) \in \mathbb {Z}^{m!}$ which satisfy

$$ z_i \ge 0 \text { for all } i \in \{1, \ldots , m!\} \text {, and } \sum _{i=1}^{m!} z_i = n \text{. } $$

Under IAC each anonymous preference profile is assumed to be equally likely to occur. Hence, in order to determine the probability of a paradox under IAC it is enough to compute the number of points belonging to preference profiles in which the paradox occurs and compare them to the total number of points in $S_{m,n}$, which is known to be $|S_{m,n}|=\left( {\begin{array}{c}m!+n-1\\ m!-1\end{array}}\right)$.⁴

In this framework, many paradoxes X can be described with the help of linear constraints, i.e., the set of points belonging to the event can be described with the help of (in)equalities, a polytope. For variable n, this approach then describes a dilated polytope $P_n=nP:=\{n\mathbf {x} :\mathbf {x} \in P\}$. Hence, we know that the probability of a paradox $X_n$ under IAC is given by:

$$ \mathbb {P}(X_n) = \frac{|nP \cap \mathbb {Z}^d|}{|S_{m,n}|}\text{. } $$

and we can determine the probability of (many) voting paradoxes under IAC by evaluating the function $L(P, n):= |nP \cap \mathbb {Z}^d|$, which describes the number of integer points inside the dilation nP. This can be done with the help of Ehrhart theory. Ehrhart (1962) was the first to show that L(P, n) can be described by special functions, called quasi- or Ehrhart-polynomials. A function $f: \mathbb {Z} \rightarrow \mathbb {Q}$ is a quasi-polynomial of degree d and period q if there exists a list of q polynomials $f_i:\mathbb {Z} \rightarrow \mathbb {Q}$ $(0 \le i < q)$ of degree d such that $f(n) = f_i(n)$ if $n \equiv i \mod q$.

Quasi-polynomials can be determined with the help of computer programs such as LattE (De Loera et al. (2004)) or Normaliz (Bruns et al. (2019a)). Unfortunately, the computation of our quasi-polynomials is computationally very demanding, especially because the dimension of the polytopes grows super-exponentially in the number of alternatives. This limits analytical results under IAC to rather small numbers of alternatives. To the best of our knowledge, Normaliz is the only program which is able to compute polytopes corresponding to elections with up to four alternatives. And even Normaliz is not always able to compute the whole quasi-polynomial, but sometimes we had to resort to computing the leading coefficients only of the polynomial, which fortunately suffices for determining the limit probability of a paradox when the number of voters goes to infinity. The problem of calculating the limit probability is equivalent to computing the volume of polytopes, for which there are also other software solutions (e.g., Convex by Franz (2016))

An overview of our analytical findings obtained in this way is provided in Table 1.

Table 1 Theoretical results obtained via Ehrhart theory (for four alternatives and under IAC)

4.2 Finding a Quasi-polynomial for MaxiMin

As an example for the method just described, we consider the CLP$_{\text {MaxiMin}}$ in 4-alternative elections under IAC, the probabilities of which can be computed from a quasi-polynomial with degree 23 and a period of 5,040.⁵

In order to determine the polynomial, we first need to describe the corresponding polytope with equalities and inequalities. Recall the definition of MaxiMin from Sect. 3.2:

$$ f_{\text {MaxiMin}} (R) := \arg \max _{x \in A} \min _{y \in A} g_{xy}. $$

For CLP$_{\text {MaxiMin}}(R)=1$ the CL of R has to have the lowest highest defeat. Formally, there is $x\in A$ such that for all $y \in A \backslash \{ x \}$,

$$\begin{aligned} g_{yx}&>0 \text {, and }\end{aligned}$$

(1)

$$\begin{aligned} \max _{z \in A \backslash \{x\}} g_{zx}&\le \max _{z \in A \backslash \{y\}} g_{zy} \text{. } \end{aligned}$$

(2)

Now let $A=\{a,b,c,d\}$ and assume $x=d$. We then have that $g_{ad}, g_{bd}, g_{cd} > 0$, which implies $\max _{z \in A \backslash \{d\}} g_{zd} > 0$. Furthermore,

$$ \max _{z \in A \backslash \{y\}} g_{zy} > 0 \text { for all } y \in \{a,b,c\}\text {, } $$

from which it follows that either $g_{ab}, g_{bc}, g_{ca} > 0$ or $g_{ba}, g_{cb}, g_{ac} > 0$. In both cases there is a majority cycle between a, b, and c. Due to symmetry we can choose one direction of the cycle arbitrarily and assume $g_{ab},g_{bc},g_{ca} > 0$. Then,

$$ \max _{z \in A \backslash \{a\}} g_{za} = g_{ca}\text {,} \max _{z \in A \backslash \{b\}} g_{zb} = g_{ab} \text {, and } \max _{x \in A \backslash \{c\}} g_{zc} = g_{ac}. $$

Condition (1) is already represented in the form of linear inequalities. In order to model condition (2) we determine $\max _{z \in A \backslash \{d\}} g_{zd}$ and distinguish cases for the seven possible outcomes. The inequalities for the case $\max _{z \in A \backslash \{d\}} g_{zd} = \{ g_{ad} \}$ are

$$\begin{aligned} g_{ad} - g_{bd}> 0\qquad \text {and} \qquad g_{ad} - g_{cd} > 0 \text {.} \end{aligned}$$

Condition (2) furthermore yields

$$ g_{ca} - g_{ad} \ge 0\text {,} \qquad g_{ab} - g_{ad} \ge 0\text {,} \qquad \text {and} \qquad g_{bc} - g_{ad} \ge 0. $$

Each case belongs to a different polytope and the polytopes are pairwise distinct, so we can compute each quasi-polynomial separately and later combine them to one. To get the final polynomial we have to multiply by eight for the four different possible choices of a CL and the two possible directions of the majority cycle. This then enables us to efficiently evaluate the exact probabilities for any number of voters. The results are depicted in Fig. 2. The leading coefficient of the quasi-polynomial can also be used to determine the limit probability which is given by

$$ \mathbb {P}(\text {CLP}_{\text {MaxiMin}}=1 \mid m=4, n \rightarrow \infty ) = 8 \cdot \frac{485052253637930099}{6443662124777472000000} \approx 0.06\% \text{. } $$

4.3 Experimental Analysis

As we will see, simulating elections with the help of computers is a viable way of achieving very good approximations for the probabilities we are looking for. It even turns out that the results of our simulations are almost indistinguishable from the theoretical result obtained via Ehrhart theory (with the exception of the limit case, which cannot be realized via simulations).

More specifically, the experimental approach works as follows: a profile source creates random preference profiles according to a specific preference model. The profiles are then used to compute the winner(s) according to a given voting rule and to determine if the paradox occurs. Any such experiment is carried out for each pair of n and m and repeated frequently. In many cases in which we covered a wide range of voters, we did not consider every possible value of n but, more economically, only simulated the values: 1–30, 49–51, 99–101, 199–201, 499–501, 999–1,001.

Since we are particularly concerned about the statistical significance of our experimental results, we also computed 99%-confidence intervals for each data point we generated. To this end, we used the binofit function in Matlab which is based on the standard approach by Clopper and Pearson (1934). It shows that, based on our sampling rate of $10^5$ and $10^6$, respectively, the 99%-confidence intervals are pleasantly small. Hence, even though they are depicted in all of the figures throughout this chapter, sometimes it can be difficult to recognize them.

4.4 Empirical Analysis

The most valuable quantification of voting paradoxes would be their actual frequency in real-world elections. As mentioned before, real-world election data is generally relatively sparse, incomplete, and inaccurate. This makes empirical research on this topic rather difficult. Otherwise, the empirical approach strongly resembles the experimental approach.

For this chapter we used two sources of empirical data. First, we used the 314 profiles with strict order preferences from the PrefLib library (Mattei and Walsh 2013). Second, we had access to the 54,650 preference profiles over four alternatives without a CW which belong to the roughly 11 million 4-alternative elections which Mattei et al. (2012) derived from the Netflix Prize data (Bennett and Lanning 2007). Non-existence of Condorcet winners is a prerequisite for the paradoxes we study.

5 Condorcet Loser Paradox

In this section we present our findings on the CLP. We conclude that—even though the CLP is possible in principle—it is so unlikely that it cannot be used as a serious argument against any of the Condorcet extensions we considered.

5.1 An Upper Bound

Before analyzing the CLP for concrete voting rules, we discuss an upper bound valid for all Condorcet extensions. For a Condorcet extension to choose the CL a profile obviously has to satisfy two conditions. First, there has to exist a CL in the profile. Second, no CW may exist in the profile. In the case of 4-alternative elections—which is the first interesting case—we can compute the quasi-polynomial via Ehrhart theory and hence know the exact probabilities for any number of voters. Similar to the example in Sect. 4.1, we can assume that alternative d is the CL and obtain the inequalities $g_{ad}, g_{bd}, g_{cd} >0$. The event that none of the remaining alternatives is the CW can be formalized as

$$\begin{aligned} (g_{ba} \ge 0 \vee g_{ca} \ge 0) \wedge (g_{ab} \ge 0 \vee g_{cb} \ge 0) \wedge (g_{ac} \ge 0 \vee g_{bc} \ge 0)\text{. } \end{aligned}$$

This leads to 27 satisfiable cases all belonging to disjoint polytopes, since $g_{xy} \ge 0$ and $\lnot (g_{xy} \ge 0)$ are exclusive. Each quasi-polynomial can be computed separately and (attributing for the four different possible CLs) they can be combined to a single quasi-polynomial, which has degree 23 and contains 24 polynomials. The coefficients take up several pages and we omit them here. The resulting probabilities for up to 1, 000 voters—and a comparison with the results of an experimental analysis—can be obtained from Fig. 1. The value of the limit probability is approximately $8\%$.

Fig. 1

Probability of the event that a Condorcet extension could choose a CL in 4-alternative elections under IAC

Especially for small even numbers of voters, where the probability is around 20%, the upper bound is too high to discard the CLP for Condorcet extensions altogether, and even the limit probability of 8% is relatively large. Also, for an increasing number of alternatives this problem does not vanish (for elections with 50 and 51 one voters and up to 100 alternatives the probabilities range between 5 and 25%).⁶

Note that differences between odd and even number of voters were to be expected since even numbers allow for majority ties, which have significant consequences for the paradoxes; this effect decreases for larger electorates. In the specific case under consideration, the upper bound is generally higher for an even number of voters because the much higher likelihood of not having a CW more than counterbalances the lower likelihood of having a CL.

5.2 Results Under IAC

Despite the high upper bounds from the previous section, the picture is quite clear for concrete Condorcet extensions: even under IAC, the risk of the considered Condorcet extensions selecting the CL is very low, as shown in Fig. 2 for 4-alternative elections. The highest probability was found for CLP$_{\text {MaxiMin}}$ with 2.2% for three voters (CLP$_{\text {Young}}$ with about 0.9%). The limit probability of CLP$_{\text {MaxiMin}}$, with 0.06% is so low that for sufficiently large electorates it would occur in only one out of 10,000 elections. The same seems to hold for the limit probability for CLP$_{\text {Young}}$. The probability of CLP$_{\text {Dodgson}}$ is even significantly lower, with a maximum of about 0.01% in elections with 9,999 voters. We could determine the limit probability of 0.01% only for an approximation of Dodgson’s rule by Tideman (1987), which seems to be close to that for Dodgson’s rule, based on our experimental data.

When increasing the number of alternatives the probabilities drop even further. For elections with more than ten alternatives they reach a negligibly small level of less than 0.005% for all considered rules and in no simulations with twelve or more alternatives we could find any occurrence of the paradox.

Fig. 2

Comparison between CLP probabilities for MaxiMin, Young’s rule (left) and Dodgson’s rule (right) under IAC in 4-alternative elections

5.3 Results Under Other Preference Models

Figure 3, as one would expect, shows that under more realistic assumptions the probability of the CLP decreases further in 4-alternative elections with 50/51 voters, with the highest probability occurring under the unrealistic assumption of IC and the lowest probability under what may be the most realistic model in many settings, the spatial model. In our experiments, Dodgson’s rule never selected a CL in the spatial model.

Similarly, we could not find any occurrence of the CLP in real-world data, which may be considered the strongest evidence that the CLP virtually never materializes in practice.⁷

Fig. 3

CLP probabilities in 4-alternative elections for varying preference models and MaxiMin

6 Agenda Contraction Paradox

Recall that the agenda contraction paradox (ACP) occurs when a reduced set of alternatives (created by the unavailability of losing alternatives) influences the outcome of an election. For many cases, it may be considered a generalization of the CLP as the following argument shows. Suppose the CL x is uniquely selected by a voting rule which implements majority rule on 2-alternative choice sets. Then restricting A to $\{x,y\}$ for some alternative $y\ne x$ yields the new winner y (since $g_{xy}>0$).

As we will see, the ACP is much more of a practical problem than the CLP. The picture, however, is not black and white. Whether or not it is a serious threat depends on the voting rule, the underlying preference distribution, and on the parity of the number of voters.

6.1 Varying Voting Rules

The ACP probability strongly varies for different voting rules (see Fig. 4). Borda’s rule generally exhibits the worst behavior of the rules studied, with probabilities of up to 56%, and with 34% for large electorates with 1, 000 voters. In contrast, Copeland’s rule is quite robust to the ACP for large electorates (with only about 8% occurrence probability for 1, 000 voters).⁸

The reason for this gap between Borda’s and Copeland’s rule appears to be two-fold: First, Condorcet extensions are safe from this paradox as long as a CW exists; Borda’s rule, by contrast, is not. Second, the discriminatory power of voting rules (i.e., their ability to select small winning sets) strongly supports the paradox. As soon as a single majority-dominated alternative is selected, the ACP has to occur. For large numbers of voters, this is in line with Copeland’s rule being least discriminating among those evaluated. The essential set is among the most discriminating known voting rules immune to the ACP, but presumably less discriminating than Copeland’s rule.

The behavior of MaxiMin is almost identical to that of Young’s and Dodgson’s rule. Confirming our approximate “limit” results of 1, 000 voters, we were able to analytically compute the limit probability for MaxiMin as $\frac{331}{2048} \approx 16\%$. This is in perfect congruence with the (rounded) values for MaxiMin, Young’s rule, and Dodgson’s rule.

It should also be noted that with fewer than 100 voters, the parity of the number of voters plays a major role. For even numbers, significantly higher probabilities arise (which is particularly true for Copeland’s rule, see above). At least part of this can be explained by a reduced probability for CWs in these cases.

For more alternatives (see the right-hand side of Fig. 4), the relative behavior remains vastly unchanged with probabilities further increasing to values larger than 40–80% (mostly since the likelihood of a CW decreases roughly at the same rate).

Fig. 4

Comparison between ACP probabilities for different voting rules under IAC

6.2 Varying Preference Models

Figure 5 extends the analysis of the previous section by additionally considering preference models beyond IAC. The overall picture regarding the different rules remains the same. For large electorates Copeland’s rule outperforms the other rules, whereas Borda’s rule performs worst. Regarding the different preference models, three classes emerge from Fig. 5.

Fig. 5

Comparison between ACP$_\text {Borda}$, ACP$_\text {Copeland}$, ACP$_\text {MaxiMin}$, and ACP$_\text {Dodgson}$ for varying preference models in 4-alternative elections; the values of ACP$_\text {Young}$ are omitted since they strongly resemble the ones of ACP$_\text {MaxiMin}$ and ACP$_\text {Dodgson}$

First, for Mallows-$\phi$ we observe probabilities that are vanishing with increased numbers of voters. Under the spatial model this is true as well, with the surprising exception of Borda’s rule, for which the picture looks completely different and the probability does not go below $20\%$ in the spatial model. Presumably, this can be explained by Borda’s inability to select the CW in this setting, a hypothesis that deserves further study, however. On the contrary, the other rules appear to be benefitting from the fact that the existence of a CW becomes very likely under models with high voter interdependence.

Second, as expected, the assumption of IC serves as an upper bound for all other preference models. The results for IAC are not much lower, fostering the impression that IAC could also be an unrealistic upper bound.

Third, the urn model yields much lower values compared to IAC and IC. The absolute numbers, however, are still beyond acceptable levels (between 4 and 23% for 1,000 voters).

Table 2 Rounded maximal CLP and ACP probabilities which occurred during our simulations

The findings in the empirical data corroborate our experimental findings. In PrefLib the ACP occurs 17 times for Borda, three times for Copeland and exactly once for MaxiMin as well as Young’s and Dodgson’s rule. In the Netflix data set, where the number of voters is at least 350, Copeland performs much better than the other Condorcet extensions (4, 400 compared to 18, 470 occurrences for the other Condorcet extensions). Borda’s rule virtually always suffers from the ACP on this data set: there are 54, 620 instances of ACPs already when considering profiles that do not have a CW (there are 54, 650 of such).

7 Conclusion

We investigated the likelihood of the CLP and the ACP using Ehrhart theory, computer simulations, and empirical data. The CLP is often cited as a major flaw of some Condorcet extensions such as Dodgson’s rule, Young’s rule, and MaxiMin. For example, Fishburn regards Condorcet extensions that suffer from the CLP (specifically referring to the three rules mentioned above) as “‘dubious’ extensions of the basic Condorcet criterion” (Fishburn 1977, p. 480).⁹ While this is intelligible from a theoretical point of view, our results have shown that the CLP is of virtually no practical concern. The ACP, on the other hand, frequently occurs under various distributional assumptions about the voters’ preferences. The extent to which it is real threat, however, strongly depends on the voting rule, the underlying distribution of preferences, and, surprisingly, the parity of the number of voters. Our main quantitative results for the worst case are summarized in Table 2.