Axioms for defeat in democratic elections

Abstract

We propose six axioms concerning when one candidate should defeat another in a democratic election involving two or more candidates. Five of the axioms are widely satisfied by known voting procedures. The sixth axiom is a weakening of Kenneth Arrow’s famous condition of the Independence of Irrelevant Alternatives (IIA). We call this weakening Coherent IIA. We prove that the five axioms plus Coherent IIA single out a method of determining defeats studied in our recent work: Split Cycle. In particular, Split Cycle provides the most resolute definition of defeat among any satisfying the six axioms for democratic defeat. In addition, we analyze how Split Cycle escapes Arrow’s impossibility theorem and related impossibility results.

1. Introduction

In the abstract of his lecture at a 2017 Lindau Nobel Laureate Meeting, Eric Maskin (2017) claimed that “The systems that most countries use to elect presidents are deeply flawed,” a claim defended in writing by Maskin and Sen (2016, 2017a, 2017b). In fact, the issue goes far beyond presidential elections: the same voting systems are used in elections ranging from national elections to elections in small committees and clubs. In our view, the key issue highlighted by Maskin and Sen can be stated in terms of the following normative principle (closely related to what voting theorists call Condorcet consistency, defined below ¹ ):

Majority Defeat: if a candidate loses an election (before any tiebreaking), they must have been defeated by some other candidate in the election, and a candidate should defeat another only if a majority of voters prefer the first candidate to the second. ²

As is well known, widely used voting systems can violate the principle of Majority Defeat.

Example 1

In the 2000 US presidential election in Florida, George W. Bush defeated Al Gore and Ralph Nader according to Plurality voting, which only allows voters to vote for one candidate. Yet based on the plausible inference that most Nader voters preferred Gore to Bush (see Magee 2003), it follows that a majority of all voters preferred Gore to Bush.

Example 2

In the 2009 mayoral election in Burlington, Vermont, the Progressive candidate Bob Kiss defeated the Democratic candidate Andy Montroll according to Instant Runoff Voting (defined in Example 14), but Montroll was preferred to each of the other candidates including Kiss by majorities of voters, according to the ranked ballots collected.

Example 3

During the 2016 US presidential primary season, an NBC News/Wall Street Journal poll (3–6 March) asked respondents both for their top choice and their preference between Donald Trump and each of Ted Cruz, John Kasich, and Marco Rubio. Trump was the Plurality winner, receiving 30% of first-place votes, but Cruz, Kasich, and Rubio were each preferred to Trump by 57%, 57%, and 56% of respondents, respectively (see Kurrild-Klitgaard 2018 concerning statistical significance). For further discussion of whether another Republican might have been majority preferred to Trump, see Maskin and Sen 2016, Maskin 2017, Kurrild-Klitgaard 2018, and Woon et al. 2020.

For related examples outside the US, see, for example, Kaminski 2015, Section 20.3.2 and Feizi et al. 2020.

The above failures of Majority Defeat involve spoiler effects. In Example 1, although it is likely that a majority of voters preferred Gore to Bush and also preferred Gore to Nader, Nader’s inclusion in the race spoiled the election for Gore, handing victory to Bush. In Example 2, although a majority of voters preferred Montroll to Kiss and a majority preferred Montroll to the Republican candidate, Kurt Wright, Wright’s inclusion in the race spoiled the election for Montroll, handing victory to Kiss. Finally, in Example 3, although the NBC News/Wall Street Journal poll did not ask for respondents’ preferences between Cruz, Kasich, and Rubio, if one of them was majority preferred to the other two, then it would be reasonable to call the latter two spoilers for the first, as their inclusion in the poll handed the plurality victory to Trump.

What other benefits might respecting Majority Defeat provide besides mitigating spoiler effects of the kind shown above? Maskin and Sen (2017a) make the following conjecture:

[M]ajority rule may reduce polarization. A centrist like Bloomberg [in the 2016 U.S. presidential election] may not be ranked first by a large proportion of voters [and hence cannot win under Plurality], but can still be elected [with the backing of majorities against each other candidate] if viewed as a good compromise. Majority rule also encourages public debate about a larger group of potential candidates [since more candidates can participate without worry of their being spoilers], bringing us closer to John Stuart Mill’s ideal of democracy as “government by discussion.”

To respect the principle of Majority Defeat, we need to collect ballots in which voters rank the candidates in the election. ³ Due to the possibility of strategic voting, we cannot guarantee that voters’ rankings of the candidates always reflect their sincere preferences (see Taylor 2005), but one can try to choose voting procedures that provide fewer incentives for strategic voting (see, e.g., Bassi 2015; Chamberlin 1985; Holliday and Pacuit 2019; Nitzan 1985). Assuming we collect ranked ballots, a wide variety of voting procedures become available (see, e.g., Brams and Fishburn 2002; Pacuit 2019; and Examples 14 and 19).

One obvious idea for satisfying the principle of Majority Defeat is to say that one candidate defeats another if and only if a majority of voters prefer the first candidate to the second. Notoriously, however, this can result in every candidate being defeated, leaving no candidate who wins. In particular, there can be a majority cycle, wherein a majority of voters prefer $a$ to $b$ , a majority of voters prefer $b$ to $c$ , and a majority of voters prefer $c$ to $a$ (Condorcet 1785). Majority cycles may also involve more than three candidates. This so-called Paradox of Voting is perhaps the main theoretical obstacle to the possibility of rational democratic decision making with more than two candidates. Riker (1982) has famously argued that the Paradox of Voting, along with the related Arrow Impossibility Theorem (Arrow 1963), destroys the notion of a coherent “will of the people” in a democracy. ⁴ Although there is not yet enough empirical research to know how prevalent majority cycles are in real elections of various scales, ⁵ majority cycles have been found in some large elections (see Deemen 2014). In a typical election, we expect (or at least hope) that there will be a Condorcet winner—a candidate $a$ such that for every candidate $b$ , more voters prefer $a$ to $b$ than $b$ to $a$ —in which case some voting theorists believe that the choice is clear: elect the Condorcet winner (see, e.g., Felsenthal and Machover 1992; Maskin and Sen 2017a, 2017b). A voting method is Condorcet consistent if it chooses as the unique winner of an election the Condorcet winner, whenever a Condorcet winner exists. But there must be some backup plan in place in case there is no Condorcet winner.

In the absence of a Condorcet winner, Maskin and Sen (2017a) suggest “having a runoff between the two top candidates,” but defining “the two top candidates” faces some of the same difficulties as defining “the best candidate.” In a recent paper (Holliday and Pacuit 2020), we study a voting procedure that we call Split Cycle, which provides a different backup plan for the case where no Condorcet winner exists. ⁶ Instead of saying if there is a Condorcet winner, elect that person, and if not, do something else with a different justification, Split Cycle provides a unified rule for cases with or without Condorcet winners:

In an election with candidates $x$ and $y$ , say that $x$ wins by a margin of $n$ over $y$ when there are $n$ more voters who prefer $x$ to $y$ than who prefer $y$ to $x$ . Then $x$ defeats $y$ according to Split Cycle if $x$ wins by more than $n$ over $y$ for the smallest number $n$ such that there is no majority cycle containing $x$ and $y$ in which each candidate wins by more than $n$ over the next candidate in the cycle.

Although there may be no Condorcet winner, there is always an undefeated candidate according to Split Cycle (if there is more than one, a tiebreaking process must be applied—cf. Remark 46). An intuitive way ⁷ to determine the Split Cycle defeat relation is as follows:

In each majority cycle, identify the wins with the smallest margin in that cycle.

After completing step 1 for all cycles, discard the identified wins. All remaining wins count as defeats.

As we show, Split Cycle mitigates spoiler effects (see Section 4.3) and has several other virtues, including avoiding the so-called Strong No Show Paradox (see Holliday and Pacuit 2020, 2021).

In this paper, we arrive at Split Cycle (defined formally in Section 3) by another route. We propose six general axioms concerning when one candidate should defeat another in a democratic election involving two or more candidates (Section 4). Five of the axioms are widely satisfied by known voting procedures. The sixth axiom is a weakening of Kenneth Arrow’s famous condition of the Independence of Irrelevant Alternatives (IIA) (Arrow 1963). We call this weakening Coherent IIA. Arrow’s IIA states that if in two elections, all voters rank candidate $x$ versus candidate $y$ in the same way, then if $x$ defeats $y$ in the first election, $x$ must also defeat $y$ in the second election. Coherent IIA agrees provided that the second election does not involve greater incoherence with respect to $x$ and $y$ , in the sense of new majority cycles or stronger majority cycles involving $x$ and $y$ . For if the second election involves greater incoherence, we may need to suspend the judgment that $x$ defeats $y$ that we could coherently accept in the first election. Both by itself and together with other axioms, Coherent IIA has a number of desirable consequences. Already by itself Coherent IIA rules out—as IIA does—a flip from $x$ defeating $y$ to $y$ defeating $x$ in two elections in which all voters rank $x$ versus $y$ in the same way; and together with other natural axioms, Coherent IIA implies Majority Defeat.

The first half of the paper culminates in a proof that the five axioms plus Coherent IIA single out Split Cycle (Section 5). In particular, our main result is that Split Cycle provides the most resolute definition of defeat of any satisfying the six axioms for democratic defeat. In the second half, we analyze how Split Cycle manages to escape Arrow’s Impossibility Theorem and related impossibility results in social choice theory (Section 6). The answer is twofold: we weaken IIA to Coherent IIA, and we relax Arrow’s assumptions about the properties of the defeat relation between candidates. We explain how neither of these moves is sufficient by itself to escape Arrow-like impossibility theorems. But by doing both, Split Cycle provides a compelling response, we think, to both the Paradox of Voting and Arrow’s Impossibility Theorem.

A key aspect of our characterization of Split Cycle using the six axioms for defeat is that we work with a model in which elections can have different sets of voters and different sets of candidates, just as they do in reality. Given the importance of this variable-election setting to our characterization, we consider how standard impossibility results for a fixed set of candidates/voters can be adapted to and even strengthened in the variable-election setting, and yet how Split Cycle still escapes them (Sections 6.2 and 6.3). One of the methodological lessons of the paper, in our view, is the value of working in a variable-election framework.

We start in Section 2 by reviewing the formal framework we will use to conduct our analysis.

2. Voting methods and collective choice rules

As suggested in Section 1, we work in a variable-voter and variable-candidate setting. This means that our group decision method can input elections—formalized as profiles below—with different sets of voters and different sets of candidates (see Remark 9.1 for a comparison with a fixed-voter and fixed-candidate setting). To allow sets of voters and candidates of arbitrary (but finite) size in elections, we first fix infinite sets $\mathcal{V}$ and $\mathcal{X}$ of voters and candidates, respectively. A given election will use only finite subsets $V\subset \mathcal{V}$ and $X\subset \mathcal{X}$ . We consider elections in which each voter in the election submits a ranking of the candidates in the election. For simplicity, in this paper, we assume that each voter submits a strict linear order on the set $X$ of candidates, that is, a binary relation $P$ on $X$ satisfying the following conditions for all $x,y,z\in X$ :

asymmetry: if $xPy$ then not $yPx$ ;

transitivity: if $xPy$ and $yPz$ , then $xPz$ ;

connectedness: if $x\ne y$ , then $xPy$ or $yPx$ .

We take $xPy$ to mean that the voter strictly prefers candidate $x$ to candidate $y$ . In practice, one may wish to allow voters not to rank all the candidates or even to indicate indifference between candidates. The voting procedures discussed below can be generalized to this setting, as we will discuss for our favored procedure in future work, but doing so raises some choice points that are not essential to the main ideas in this paper.

We formalize the notion of an election as a function associating with each voter their ranking of the candidates. For a set $X$ , let $\mathcal{L}(X)$ be the set of all strict linear orders on $X$ .

Definition 4

A profile is a function $\mathbf{P}:V\to \mathcal{L}(X)$ for some nonempty finite $V\subset \mathcal{V}$ and nonempty finite $X\subset \mathcal{X}$ , which we denote by $V(\mathbf{P})$ (called the set of voters in $\mathbf{P}$ ) and $X(\mathbf{P})$ (called the set of candidates in $\mathbf{P}$ ), respectively. We call $\mathbf{P}(i)$ voter $i$ ’s ballot, and we write “ $x{\mathbf{P}}_{i}y$ ” for $(x,y)\in \mathbf{P}(i)$ .

When we display profiles, we show their “anonymized form” that records only the number of voters with each type of ballot, rather than the identities of the voters. For example:

The above diagram indicates that two voters rank $b$ above $c$ above $a$ (notation: $bca$ ), etc.

It will be important later to consider the restriction of a profile to a subset $Y$ of the candidates: we erase from each voter’s ballot any candidates not in $Y$ , leaving the ranking of the candidates in $Y$ unchanged.

Definition 5

Given a binary relation $P$ on $X$ and $Y\subseteq X$ , let $P_{\mid Y}$ be the restriction of $P$ to the set $Y$ , that is, $P_{\mid Y}=P\cap (Y\times Y)$ . Given a profile $\mathbf{P}$ , let ${\mathbf{P}}_{\mid Y}$ be the profile with $X({\mathbf{P}}_{\mid Y})=Y$ and $V({\mathbf{P}}_{\mid Y})=V(\mathbf{P})$ obtained from $\mathbf{P}$ by restricting each voter’s ballot to the set $Y$ . ⁸

We now consider two different kinds of group decision methods, differing in what they output. The first kind outputs a set of potential winners for the election.

Definition 6

A voting method is a function $F$ on the domain of all profiles that returns for any profile $\mathbf{P}$ a nonempty subset $F(\mathbf{P})$ of the candidates in $\mathbf{P}$ , i.e., $\varnothing \ne F(\mathbf{P})\subseteq X(\mathbf{P})$ .

As usual, if $F(\mathbf{P})$ contains multiple candidates, we assume that some further tiebreaking process would then apply, though we do not fix the nature of this process (see Schwartz 1986, 14–15 for further discussion). If $x\notin F(\mathbf{P})$ , this means that $x$ is excluded from the rest of the process that leads to the ultimate winner.

The second kind of group decision method outputs an asymmetric binary relation on the set of candidates. In social choice theory, this relation is typically called the “strict social preference” relation. We interpret this binary relation as a defeat relation for the election in the sense of Section 1.

Definition 7

A variable-election collective choice rule (VCCR) is a function $f$ on the domain of all profiles such that for any profile $\mathbf{P}$ , $f(\mathbf{P})$ is an asymmetric binary relation on $X(\mathbf{P})$ , which we call the defeat relation for $\mathbf{P}$ according to $f$ . For $x,y\in X(\mathbf{P})$ , we say that $x$ defeats $y$ in $\mathbf{P}$ according to $f$ when $(x,y)\in f(\mathbf{P})$ .

A well-known special case of a collective choice rule (CCR) is what Arrow called a social welfare function (SWF). The output of an SWF is a strict weak order, that is, a binary relation $P$ on $X$ satisfying asymmetry and the condition that for all $x,y,z\in X:$

if $xPy$ , then $xPz$ or $zPy$ .

Note that these conditions imply that $P$ is transitive. In the variable-election setting, we define the following.

Definition 8

A variable-election social welfare function (VSWF) is a VCCR $f$ such that for any profile $\mathbf{P}$ , $f(\mathbf{P})$ is a strict weak order.

For readers familiar with the standard setup in social choice theory, we note some subtleties about our definitions.

Remark 9

$$

We add the modifier “variable-election” because the term “collective choice rule” due to Sen (2017, Chapter 2 ${}^{*}$ ) appears in a fixed-voter and fixed-candidate setting. In this setting, one begins by fixing a nonempty set $V$ of voters and a nonempty set $X$ of candidates; one then defines a collective choice rule (CCR) as a function that takes as its input a profile for $V$ and $X$ (see Section 6.1). One could call this a “variable election” setting insofar as the sizes of $V$ and $X$ are not specified and definitions of CCRs and axioms concerning CCRs do not refer to specific numbers of voters and candidates. However, it is not a variable election setting in our sense, since the domain of a CCR cannot contain both a profile whose set of voters is $\{i,j,k\}$ and a profile whose set of voters is $\{i,j\}$ ; likewise, it cannot contain both a profile whose set of candidates is $\{a,b,c\}$ and a profile whose set of candidates is $\{a,b\}$ , etc. Yet there are important axioms in voting theory concerning the addition or removal of voters or candidates: not only some of the axioms proposed below, but also, for instance, axioms concerning adding voters who support a given candidate (see, e.g., Felsenthal and Nurmi 2016) or adding a candidate who is a “clone” of another candidate (Tideman 1987). These axioms cannot be formalized in terms of a CCR whose domain contains only profiles for $V$ and $X$ .

In social choice theory, one often defines the output of a CCR (as Sen does) to be a “weak social preference” relation $R$ that is reflexive instead of asymmetric. For social welfare functions, the choice does not matter, because strict weak orders $P$ are in one-to-one correspondence with complete and transitive relations $R$ . ⁹ However, since we aim to study the concept of defeat, an asymmetric relation, we have defined VCCRs accordingly.

For simplicity, we build the axiom of Universal Domain into the definition of a VCCR, but one could of course define a notion of VCCR where only certain profiles are in the domain of $f$ (cf. Gaertner 2001).

Any VSWF $f$ induces a voting method $\overline{f}$ such that for any profile $\mathbf{P}$ , $\overline{f}(\mathbf{P})$ is the set of candidates who are not defeated by any candidates in $\mathbf{P}$ according to $f$ . That $f(\mathbf{P})$ is a strict weak order implies that $\overline{f}(\mathbf{P})$ is nonempty, but in fact a much weaker condition is sufficient—namely, acyclicity.

Definition 10

Let $P$ be an asymmetric binary relation on a set $X$ . A cycle in $P$ is a sequence $x_1,\dots ,x_n$ of elements of $X$ such that $x_{1}P{x}_2,\dots ,x_{n-1}P{x}_n$ , $x_n=x_1$ , and all elements are distinct except $x_1$ and $x_n$ . ¹⁰ The relation $P$ is acyclic if there is no cycle in $P$ . A VCCR $f$ is acyclic if for all profiles $\mathbf{P}$ , $f(\mathbf{P})$ is acyclic.

Any acyclic VCCR induces a voting method that outputs for a given profile the set of undefeated candidates. All defeated candidates are excluded from the rest of the process that leads to the ultimate winner.

Lemma 11

Given any acyclic VCCR $f$ , the function $\overline{f}$ on the set of profiles defined by

$$\overline{f}(\mathbf{P})=\{x\in X(\mathbf{P})\mid \text{ there is no }y\in X(\mathbf{P}):y\text{ defeats }x\text{ in }\mathbf{P}\text{ according to }f\}$$

is a voting method, as $\varnothing \ne \overline{f}(\mathbf{P})\subseteq X(\mathbf{P})$ .

Given a voting method $F$ , we can consider the acyclic VCCRs from which $F$ arises as in Lemma 11.

Definition 12

Let $F$ be a voting method and $f$ a VCCR. Then $F$ is defeat rationalized by $f$ if $F=\overline{f}$ .

Let us now review some standard VCCRs. Several of the VCCRs are based on the majority preference relation, defined as follows.

Definition 13

Given a profile $\mathbf{P}$ and $x,y\in X(\mathbf{P})$ , we say that $x$ is majority preferred to $y$ in $\mathbf{P}$ (and $y$ is majority dispreferred to $x$ in $\mathbf{P}$ ) if more voters rank $x$ above $y$ in $\mathbf{P}$ than rank $y$ above $x$ in $\mathbf{P}$ . We write $x{\to }_{\mathbf{P}}y$ (or $x\to y$ if $\mathbf{P}$ is clear from context) to indicate that $x$ is majority preferred to $y$ in $\mathbf{P}$ .

A majority cycle in $\mathbf{P}$ is a cycle in the relation ${\to }_{\mathbf{P}}$ .

Example 14

$$

Simple Majority. For $x,y\in X(\mathbf{P})$ , $x$ defeats $y$ in $\mathbf{P}$ if and only if $x\to y$ .

Covering (Gillies 1959; Fishburn 1977; Miller 1980). For $x,y\in X(\mathbf{P})$ , say that $x$ left-covers $y$ in $\mathbf{P}$ if for all $z\in X(\mathbf{P})$ , if $z\to x$ , then $z\to y$ ; and $x$ right-covers $y$ in $\mathbf{P}$ if for all $z\in X(\mathbf{P})$ , if $y\to z$ , then $x\to z$ . (Left-covering and right-covering are equivalent if $\mathbf{P}$ has an odd number of voters but not for an even number of voters.) We say that $x$ defeats $y$ in $\mathbf{P}$ according to the Left Covering VCCR (respectively, Right Covering VCCR) if $x\to y$ and $x$ left-covers $y$ (respectively, $x\to y$ and $x$ right-covers $y$ ). We say that $x$ defeats $y$ in $\mathbf{P}$ according to the Fishburn VCCR if $x$ left-covers $y$ but $y$ does not left-cover $x$ .

Copeland (Copeland 1951). The Copeland score of a candidate $x$ in profile $\mathbf{P}$ is the number of candidates to whom $x$ is majority preferred in $\mathbf{P}$ minus the number of candidates who are majority preferred to $x$ in $\mathbf{P}$ : $|\{z\in X(\mathbf{P})\mid x\to z\}|-|\{z\in X(\mathbf{P})\mid z\to x\}|$ . Then for $x,y\in X(\mathbf{P})$ , $x$ defeats $y$ in $\mathbf{P}$ if and only if the Copeland score of $x$ is greater than the Copeland score of $y$ .

Borda. The Borda score of a candidate $x$ in profile $\mathbf{P}$ is calculated as follows: for every voter who ranks $x$ in last place, $x$ receives 0 points, and for every voter who ranks $x$ in second to last place, $x$ receives 1 point, and so on. That is, for every voter who ranks $x$ in $k$ places above the last place, $x$ receives $k$ points. The sum of the points that $x$ receives is $x$ ’s Borda score in $\mathbf{P}$ . Then for $x,y\in X(\mathbf{P})$ , $x$ defeats $y$ in $\mathbf{P}$ if and only if the Borda score of $x$ is greater than the Borda score of $y$ .

Plurality. The plurality score of a candidate $x$ in profile $\mathbf{P}$ is the number of voters who rank $x$ in the first place. Then for $x,y\in X(\mathbf{P})$ , $x$ defeats $y$ in $\mathbf{P}$ if and only if the plurality score of $x$ is greater than the plurality score of $y$ .

Instant Runoff (Hare). Given a profile $\mathbf{P}$ , define a sequence ${\mathbf{P}}_0,\dots ,{\mathbf{P}}_n$ of profiles as follows. First, ${\mathbf{P}}_0=\mathbf{P}$ . Second, given a profile ${\mathbf{P}}_k$ in the sequence, if all candidates in ${\mathbf{P}}_k$ have the same plurality score, set $n=k$ to end the sequence; otherwise, where $A_k$ is the set of candidates whose plurality score in ${\mathbf{P}}_k$ is above the lowest plurality score of a candidate in ${\mathbf{P}}_k$ , let ${\mathbf{P}}_{k+1}$ be obtained from ${\mathbf{P}}_k$ by restricting the set of candidates to $A_k$ , that is, ${\mathbf{P}}_{k+1}=({\mathbf{P}}_k{)}_{\mid A_k}$ . ¹¹ The Hare score of candidate $x$ in $\mathbf{P}$ is the number of rounds of elimination that $x$ survives, that is, the greatest $k$ such that $x\in A_k$ . Then $x$ defeats $y$ in $\mathbf{P}$ if and only if the Hare score of $x$ is greater than the Hare score of $y$ .

VCCRs 2–6 are all acyclic—but 1 is not, due to the possibility of majority cycles—and 3–6 are VSWFs. For axiomatic characterizations of the Copeland and Borda VSWFs, see Rubinstein 1980 for Copeland and Nitzan and Rubinstein 1981 and Mihara 2017 for Borda.

VCCRs 1–4 all have an important property in common: their output depends only on the margins between candidates in the given profile.

Definition 15

Let $\mathbf{P}$ be a profile and $x,y\in X(\mathbf{P})$ . The margin of $x$ over $y$ in $\mathbf{P}$ is the number of voters who rank $x$ above $y$ in $\mathbf{P}$ minus the number of voters who rank $y$ above $x$ in $\mathbf{P}$ . ¹² Let $Margi{n}_{\mathbf{P}}(x,y)$ be the margin of $x$ over $y$ in $\mathbf{P}$ .

The margin graph of $\mathbf{P}$ , $\mathcal{M}(\mathbf{P})$ is the directed graph with weighted edges whose set of nodes is $X(\mathbf{P})$ with an edge from $x$ to $y$ when $x$ is majority preferred to $y$ , weighted by the margin of $x$ over $y$ in $\mathbf{P}$ .

Example 16

For a profile $\mathbf{P}$ shown in anonymized form on the left, its margin graph $\mathcal{M}(\mathbf{P})$ is shown on the right:

Clearly the edge relation in $\mathcal{M}(\mathbf{P})$ must be asymmetric, since if $x$ is majority preferred to $y$ , then $y$ is not majority preferred to $x$ . Also note that if there is an even number of voters, then it may be that neither $x$ nor $y$ is majority preferred to the other, in which case there is no edge from $x$ to $y$ or from $y$ to $x$ in $\mathcal{M}(\mathbf{P})$ . Thus, the underlying graph of $\mathcal{M}(\mathbf{P})$ is not necessarily a tournament, which is a directed graph whose edge relation is asymmetric and connected, that is, if $x\ne y$ , then there is an edge from $x$ to $y$ or an edge from $y$ to $x$ . However, when the number of voters is odd, then the directed graph is a tournament.

Now the idea that the output of a VCCR depends only on margins can be formalized as follows. ¹³

Definition 17

A VCCR $f$ is margin based if for any profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ , if $\mathcal{M}(\mathbf{P})=\mathcal{M}({\mathbf{P}}^{\prime })$ , then $f(\mathbf{P})=f({\mathbf{P}}^{\prime })$ .

It is obvious that VCCRs 1–3 in Example 14 are margin based, but this is less obvious for Borda.

Lemma 18

For any profile $\mathbf{P}$ and $x,y\in X(\mathbf{P})$ , $x$ defeats $y$ according to the Borda VCCR if and only if the sum of the margins of $x$ over all other candidates is greater than the sum of the margins of $y$ over all other candidates. ¹⁴

Other examples of margin-based VCCRs include the following.

Example 19

$$

Weighted Covering (Dutta and Laslier 1999; Pérez-Fernández and De Baets 2018). Given a profile $\mathbf{P}$ and $x,y\in X(\mathbf{P})$ , $x$ defeats $y$ in $\mathbf{P}$ if $x\to y$ and for all $z\in X(\mathbf{P})$ , $Margi{n}_{\mathbf{P}}(x,z)\ge Margi{n}_{\mathbf{P}}(y,z)$ (or equivalently $Margi{n}_{\mathbf{P}}(z,x)\le Margi{n}_{\mathbf{P}}(z,y)$ ).

Beat Path (Schulze 2011). Given a profile $\mathbf{P}$ and $x,y\in X(\mathbf{P})$ a path from $x$ to $y$ is a sequence $z_1,\dots ,z_n$ of candidates with $z_1=x$ and $z_n=y$ such that each candidate is majority preferred to the next candidate in the sequence. The strength of a path is the smallest margin between consecutive candidates in the path. Then $x$ defeats $y$ in $\mathbf{P}$ according to the Beat Path VCCR if the strength of the strongest path from $x$ to $y$ is greater than the strength of the strongest path from $y$ to $x$ .

Remark 20

Within the family of margin-based VCCRs, we can make a useful three-way distinction.

A majority graph is any directed graph $M$ whose edge relation is asymmetric. Given a profile $\mathbf{P}$ , the majority graph of $\mathbf{P}$ , $M(\mathbf{P})$ , is the directed graph whose set of nodes is $X(\mathbf{P})$ with an edge from $x$ to $y$ when $x$ is majority preferred to $y$ in $\mathbf{P}$ . We say that a VCCR $f$ is majority based if for any profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ , if $M(\mathbf{P})=M({\mathbf{P}}^{\prime })$ , then $f(\mathbf{P})=f({\mathbf{P}}^{\prime })$ . ¹⁵ The Simple Majority, Covering, and Copeland VCCRs in Example 14 are majority based in this sense. Similarly one can define the class of majority based voting methods (as distinguished from VCCRs), which generalize tournament solutions (Brandt et al. 2016; Laslier 1997) from tournaments to majority graphs.

A qualitative margin graph is a pair $\mathbb{M}=(M,\prec )$ where $M$ is a majority graph and $\prec$ is a strict weak order on the set of edges of $M$ . The qualitative margin graph of $\mathbf{P}$ is the pair $\mathbb{M}(\mathbf{P})=(M(\mathbf{P}),{\prec }_{\mathbf{P}})$ such that for any edges $(a,b)$ and $(c,d)$ in $M(\mathbf{P})$ , we have $(a,b){\prec }_{\mathbf{P}}(c,d)$ if $Margi{n}_{\mathbf{P}}(a,b)<Margi{n}_{\mathbf{P}}(c,d)$ . We say that a VCCR $f$ is qualitative-margin based if for any profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ , if $\mathbb{M}(\mathbf{P})=\mathbb{M}({\mathbf{P}}^{\prime })$ , then $f(\mathbf{P})=f({\mathbf{P}}^{\prime })$ . ¹⁶ The Weighted Covering and Beat Path VCCRs in Example 19 are qualitative-margin based in this sense, as is the Split Cycle VCCR defined in Section 3, but none of these VCCRs are majority based.

A margin graph is a weighted directed graph $\mathcal{M}$ such that: the edge relation of the graph is asymmetric; either all weights of edges are even positive integers or all weights of edges are odd positive integers; and if there are two nodes with no edge between them, then all weights are even. We already defined for a profile $\mathbf{P}$ the margin graph of $\mathbf{P}$ in Definition 17, as well as margin-based VCCRs in Definition 17. Note that the Borda VCCR in Example 14 is margin based but not qualitative-margin based.

Finally, a useful fact for the study of margin-based VCCRs is that any abstract margin graph as in Remark 20.3 can be realized as the margin graph of a profile.

Theorem 21 (Debord 1987)

For any margin graph $\mathcal{M}$ , there is a profile $\mathbf{P}$ such that $\mathcal{M}$ is the margin graph of $\mathbf{P}$ .

In light of Debord’s theorem, one can construct margin graphs at will, without deriving them from particular profiles, when experimenting with the operation of margin-based VCCRs.

This concludes our review of basic notions. In the next section, we turn to our preferred VCCR.

3. Split Cycle

In Holliday and Pacuit 2020, we studied a voting method that we call Split Cycle. Here we formulate the Split Cycle VCCR that defeat rationalizes the Split Cycle voting method (recall Definition 12). We give two formulations in Definition 22 and Lemma 3.5, respectively. The first definition of Split Cycle formalizes the definition given in Section 1. For a profile $\mathbf{P}$ , candidates $x,y\in X(\mathbf{P})$ , and natural number $n$ , say that $x$ wins by $n$ over $y$ if the margin of $x$ over $y$ in $\mathbf{P}$ is $n$ (recall Definition 15).

Definition 22

Given a profile $\mathbf{P}$ and candidates $x,y\in X(\mathbf{P})$ , $x$ defeats $y$ in $\mathbf{P}$ according to Split Cycle if $x$ wins by more than $n$ over $y$ for the smallest number $n$ such that there is no majority cycle containing $x$ and $y$ in which each candidate wins by more than $n$ over the next candidate in the cycle.

The basic idea is that when the electorate’s majority preference relation is incoherent, in the sense that there is a majority cycle, this raises the threshold required for one candidate $a$ in the cycle to defeat another $b$ —but not infinitely. If we raise the threshold $n$ sufficiently, then there will be no incoherence involving $a$ and $b$ with respect to the higher threshold, that is, no cycles in the win by more than $n$ relation that contain $a$ and $b$ . If the margin of $a$ over $b$ is greater than this sufficiently large $n$ , Split Cycle says that $a$ defeats $b$ . Note, crucially, that for some other pair of candidates $a^{\prime }$ and $b^{\prime }$ , the threshold for $a^{\prime }$ to defeat $b^{\prime }$ may be different, if $a^{\prime }$ and $b^{\prime }$ are contained in different majority cycles than $a$ and $b$ are.

Example 23

Consider a profile $\mathbf{P}$ with the following margin graph:

The only majority cycle is $a\to b\to c\to a$ . Note that each candidate wins by more than $2$ over the next candidate in the sequence. However, it is not the case that each candidate wins by more than $3$ over the next candidate in the sequence. Thus, a threshold of win by more than $3$ splits the $a\to b\to c\to a$ cycle:

Hence there is no incoherence involving $a$ and $b$ with respect to the win by more than $3$ relation. Then since $a$ wins by more than $3$ over $b$ , Split Cycle says that $a$ defeats $b$ . Similarly, since $b$ wins by more than $3$ over $c$ , Split Cycle says that $b$ defeats $c$ . However, since $c$ does not win by more than $3$ over $a$ , Split Cycle says that $c$ does not defeat $a$ . Crucially, though, since $c$ and $d$ are not involved in any cycles together, and $c$ wins by more than 0 over $d$ , Split Cycle says that $c$ defeats $d$ . The key point is that incoherence can be localized: $c$ and $a$ belong to a cycle together, but $c$ and $d$ do not. By the same reasoning, $a$ defeats $d$ , and $b$ defeats $d$ . Thus, we obtain the following defeat relation:

Note that just as in a sporting tournament, it can happen that while team $a$ defeats team $b$ and team $b$ defeats team $c$ , team $a$ does not defeat team $c$ , the same phenomenon occurs in the defeat relation above. Finally, since $a$ is the only undefeated candidate, $a$ is the winner according to Split Cycle.

Remark 24

Where $f$ is the Split Cycle VCCR as in Definition 22, the induced voting method $\overline{f}$ , which picks as winners the undefeated candidates, is the Split Cycle voting method. As a voting method, Split Cycle is Condorcet consistent: if $x$ is majority preferred to every other candidate $y$ —if $x$ is a Condorcet winner—then $x$ is the unique winner of the election. For if $x$ is the Condorcet winner, then there are no cycles involving $x$ , so $x$ defeats all other candidates according to Split Cycle.

An equivalent definition of Split Cycle can be given in terms of the following concept.

Definition 25

Let $\mathbf{P}$ be a profile and $\rho$ a majority cycle in $\mathbf{P}$ . The splitting number of $\rho$ in $\mathbf{P}$ is the smallest margin between consecutive candidates in $\rho$ . Let $Split{\mathrm{\#}}_{\mathbf{P}}(\rho )$ be the splitting number of $\rho$ in $\mathbf{P}$ .

For example, the splitting number of the cycles $a,b,c,a$ in the profile in Example 23 is 3. In Holliday and Pacuit 2020, we took the following formulation of Split Cycle to be the official definition (for a proof of Lemma 3.5, see Appendix A).

Lemma 26

Let $\mathbf{P}$ be a profile and $x,y\in X(\mathbf{P})$ . Then $x$ defeats $y$ in $\mathbf{P}$ according to Split Cycle if and only if $Margi{n}_{\mathbf{P}}(x,y)>0$ and

$$Margi{n}_{\mathbf{P}}(x,y)>Split{\mathrm{\#}}_{\mathbf{P}}(\rho )\text{ for every majority cycle }\rho \text{ in }\mathbf{P}\text{ containing }x\text{ and }y.$$

Thus, in Example 23, $a$ defeats $b$ because $Margi{n}_{\mathbf{P}}(a,b)=5$ , the only majority cycle is $a,b,c,a$ , and its splitting number is $3$ . Observe that since we are only comparing the sizes of margins, Split Cycle is qualitative-margin based in the sense of Remark 20.

Example 27

It is important to note that two candidates may be contained in multiple majority cycles, as in the following margin graph, repeated three times with the majority cycles highlighted:

The splitting number of the cycle $a\to d\to b\to a$ is 1; the splitting number of the cycle $a\to c\to b\to a$ is 5; and the splitting number of the cycle $a\to c\to d\to b\to a$ is 3. Comparing the margins against these splitting numbers, one can calculate that the defeat relation is as follows:

Since $d$ is the only undefeated candidate, $d$ is the winner according to Split Cycle. ¹⁷

Additional examples of determining the Split Cycle defeat relation will be given below (Example 36, Remark 38, and Example 62). For still more examples, see Holliday and Pacuit 2020.

A useful fact, proved in Holliday and Pacuit 2020, is that it suffices to only look at majority cycles in which $y$ directly follows $x$ . We include the proof in Appendix A to keep the paper self-contained.

Lemma 28

Let $\mathbf{P}$ be a profile and $x,y\in X(\mathbf{P})$ . Then $x$ defeats $y$ in $\mathbf{P}$ according to Split Cycle if and only if $Margi{n}_{\mathbf{P}}(x,y)>0$ and

$$\begin{array}{rl}& Margi{n}_{\mathbf{P}}(x,y)>Split{\mathrm{\#}}_{\mathbf{P}}(\rho )\mathrm{foreverymajoritycycle}\rho \mathrm{in}\mathbf{P}\mathrm{oftheform}\\ & x\to y\to z_1\to \cdots \to z_n\to x.\end{array}$$

In Holliday and Pacuit 2020, we show that Split Cycle—understood as a voting method, that is, as $\overline{f}$ for the Split Cycle VCCR $f$ —satisfies a number of desirable axioms for voting methods, and we systematically compare Split Cycle to other margin-based voting methods, including Beat Path and Ranked Pairs (Tideman 1987). In particular, we show that Split Cycle is the only known voting method that satisfies several axioms, including anti-spoiler axioms and axioms preventing the so-called Strong No Show Paradox. In the next two sections, we take a different approach: we characterize Split Cycle as a VCCR, rather than a voting method, and we characterize the Split Cycle VCCR relative to all VCCRs.

4. Axioms

In this section, we propose six axioms concerning when one candidate should defeat another in a democratic election involving two or more candidates. Four axiom are standard (Section 4.1); one is less well known but also from the previous literature (Section 4.2); and the key axiom is new (Section 4.3).

4.1. Standard axioms

The first four axioms are ubiquitous in social choice and voting theory. The first axiom appears already in May’s (1952) characterization of majority rule for two-candidate elections:

A1. Anonymity and Neutrality: if $x$ defeats $y$ in $\mathbf{P}$ , and ${\mathbf{P}}^{\prime }$ is obtained from $\mathbf{P}$ by swapping the ballots assigned to two voters, then $x$ still defeats $y$ in ${\mathbf{P}}^{\prime }$ (Anonymity); and if $x$ defeats $y$ in $\mathbf{P}$ , and ${\mathbf{P}}^{\prime }$ is obtained from $\mathbf{P}$ by swapping $x$ and $y$ on each voter’s ballot, then $y$ defeats $x$ in ${\mathbf{P}}^{\prime }$ (Neutrality). ¹⁸

It is clear that all VCCRs defined so far in this paper satisfy Anonymity and Neutrality.

The second axiom is definitive of the problem of choosing winners that we aim to solve:

A2. Availability: for every $\mathbf{P}$ , there is some undefeated candidate in $\mathbf{P}$ .

To say that in some profiles all candidates are defeated and hence excluded from further consideration—so no candidate is available to become the ultimate winner—is to give up on solving the problem. Unlike the Simple Majority VCCR (Example 14), Split Cycle satisfies Availability.

Proposition 29

Split Cycle satisfies Availability.

Proof

Suppose there is a profile $\mathbf{P}$ in which every candidate is defeated by some other. Since $X(\mathbf{P})$ is finite, it follows that there is a sequence $\rho =x_1,\dots ,x_n$ of candidates with $x_1=x_n$ such that each candidate defeats the next candidate in the sequence. It follows by Lemma 3.5 that $\rho$ is a majority cycle in which the margin of each candidate over the next is greater than the splitting number of $\rho$ , which is impossible.  □

Note that Availability is strictly weaker than the assumption that a VCCR is acyclic. There being no defeat cycles implies that some candidate is undefeated (given that the set of candidates in a profile is finite), but some candidate being undefeated does not imply that there are no defeat cycles (e.g. $a$ could be undefeated while there is a defeat cycle involving $b$ , $c$ , and $d$ ). Nonetheless, the proof of Proposition 29 (starting in the second sentence) shows that Split Cycle is an acyclic VCCR as well.

For the third axiom, given any profile $\mathbf{P}$ and natural number $m$ , the profile $m\mathbf{P}$ is obtained from $\mathbf{P}$ by replacing each voter by $m$ copies of that voter. For example, if $\mathbf{P}$ has three voters $i,j,k$ , then $2\mathbf{P}$ has six voters $i_1,i_2,j_1,j_2,k_1,k_2$ such that the ballots of $i_1$ and $i_2$ in $2\mathbf{P}$ are the same as those of $i$ in $\mathbf{P}$ , etc.

A3. (Upward) Homogeneity: for every $\mathbf{P}$ , if $x$ defeats $y$ in $\mathbf{P}$ , then $x$ defeats $y$ in $2\mathbf{P}$ .

Homogeneity is usually stated as the condition that for any $m\ge 1$ , $x$ defeats $y$ in $\mathbf{P}$ if and only if $x$ defeats $y$ in $m\mathbf{P}$ . As Smith (1973, 1029) remarks, “Homogeneity seems an extremely natural requirement; if each voter suddenly splits into $m$ voters, each of whom has the same preferences as the original, it would be hard to imagine how the “collective preference” would change.” Nonetheless, we use the weaker version stated above since it is sufficient for our main result. Almost all standard voting procedures satisfy (the usual statement of) Homogeneity. ¹⁹ That Split Cycle satisfies Homogeneity follows from the fact that Split Cycle is qualitative-margin based as in Remark 20, and $\mathbf{P}$ and $2\mathbf{P}$ have the same qualitative margin graphs.

The fourth axiom is one of the most widely discussed principles in voting theory. The term “Monotonicity” is used for a number of different conditions, but our formulation is equivalent (for profiles of linear ballots) to Arrow’s (1963) axiom of Positive Association of Social and Individual Values: ²⁰

A4. Monotonicity (respectively, Monotonicity for two-candidate profiles): if $x$ defeats $y$ in a profile (respectively, two-candidate profile) $\mathbf{P}$ , and ${\mathbf{P}}^{\prime }$ is obtained from $\mathbf{P}$ by some voter $i$ moving $x$ above the candidate that $i$ ranked immediately above $x$ in $\mathbf{P}$ , then $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ .

One might argue that Monotonicity should hold for any number of candidates, but Monotonicity for two-candidate profiles is sufficient for the proof of our main result. This is noteworthy because the Instant Runoff VCCR in Example 14 (as well as VCCRs based on other standard voting procedures, e.g. Baldwin, Coombs, and Nanson) does not satisfy Monotonicity for arbitrary profiles (see Felsenthal and Nurmi 2017) but does for two-candidate profiles. All other VCCRs defined above satisfy Monotonicity for all profiles.

The axioms proposed so far imply the principle of Majority Defeat for two-candidate profiles. The proof is essentially part of the proof of May’s (1952) characterization of majority rule.

Lemma 30

If $f$ satisfies Anonymity, Neutrality, and Monotonicity with respect to two-candidate profiles, then $f$ satisfies Special Majority Defeat: for any two-candidate profile $\mathbf{P}$ , $x$ defeats $y$ in $\mathbf{P}$ according to $f$ only if $x$ is majority preferred to $y$ .

Proof

Suppose $x$ defeats $y$ in $\mathbf{P}$ . It follows by Anonymity, Neutrality, and the asymmetry of defeat that the number of voters who rank $x$ above $y$ is not equal to the number who rank $y$ above $x$ . Now we claim that $x$ is majority preferred to $y$ . Suppose instead that $y$ is majority preferred to $x$ by a margin of $m$ . Flip voters with $y{\mathbf{P}}_{i}x$ to $x{\mathbf{P}}_i^{\prime }y$ until we obtain a profile ${\mathbf{P}}^{\prime }$ in which $x$ is majority preferred to $y$ by a margin of $m$ . Since $x$ defeats $y$ in $\mathbf{P}$ , $x$ still defeats $y$ in ${\mathbf{P}}^{\prime }$ by Monotonicity. But ${\mathbf{P}}^{\prime }$ can also be obtained from $\mathbf{P}$ by the voter and candidate swaps described in the statements of Anonymity and Neutrality. Thus, since $x$ defeats $y$ in $\mathbf{P}$ , $y$ defeats $x$ in ${\mathbf{P}}^{\prime }$ . Hence in ${\mathbf{P}}^{\prime }$ , $x$ defeats $y$ and $y$ defeats $x$ , contradicting the asymmetry of defeat.  □

Remark 31

Monotonicity is weaker than May’s (1952) condition of Positive Responsiveness, which in addition requires that if $y$ does not defeat $x$ in $\mathbf{P}$ , then changing a single voter from $y{\mathbf{P}}_{i}x$ to $x{\mathbf{P}}_i^{\prime }y$ results in $x$ defeating $y$ in ${\mathbf{P}}^{\prime }$ . We find imposing Positive Responsiveness in general, that is, for elections with any number of candidates, much too strong, ²¹ so we prefer to motivate majority rule in two-candidate elections using axioms that are more plausible for any number of candidates, as in Proposition 35 below.

4.2. Neutral reversal

Like the axiom of homogeneity, the next axiom is a variable-voter axiom. Say that two voters $i$ and $j$ have reversed ballots in a profile $\mathbf{Q}$ if for all $x,y\in X(\mathbf{Q})$ , we have $x{\mathbf{Q}}_{i}y$ if and only if $y{\mathbf{Q}}_{j}x$ . For example, if $i$ has $abcd$ and $j$ has $dcba$ , then $i$ and $j$ have reversed ballots. Adding a pair of voters with reversed ballots to a profile does not change the margins between any candidates. A natural thought is that such voters balance each other out, so adding such a pair to an election should not change the defeat relations between candidates. This leads to what Saari (2003) calls the Neutral Reversal Requirement.

A5. Neutral Reversal: if ${\mathbf{P}}^{\prime }$ is obtained from $\mathbf{P}$ by adding two voters with reversed ballots, then $x$ defeats $y$ in $\mathbf{P}$ if and only if $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ .

Not only Split Cycle but all other margin-based VCCRs (recall Example 14) satisfy Neutral Reversal. However, Neutral Reversal is weaker than the assumption that a VCCR is margin based.

Example 32

We define the Positive/Negative VCCR (cf. García-Lapresta et al. 2010 and Heckelman and Ragan 2021) as follows. In a profile $\mathbf{P}$ , a candidate $x$ receives $1$ point for every voter who ranks $x$ first and $-1$ point for every voter who ranks $x$ last. The score of $x$ in $\mathbf{P}$ is the sum of the points $x$ receives from voters. Then $x$ defeats $y$ in $\mathbf{P}$ if the score of $x$ is greater than the score of $y$ . This Positive/Negative VCCR satisfies Neutral Reversal, as a pair of reversed ballots adds a net score of 0 to each candidate. Yet it is easy to construct profiles with the same margin graphs that have different defeat relations.

Not all common VCCRs satisfy Neutral Reversal, as Examples 33 and 34 below show. To analyze violations of Neutral Reversal, we distinguish its two directions:

Upward Neutral Reversal: if ${\mathbf{P}}^{\prime }$ is obtained from $\mathbf{P}$ by adding two voters with reversed ballots, then if $x$ defeats $y$ in $\mathbf{P}$ , $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ .

Downward Neutral Reversal: if ${\mathbf{P}}^{\prime }$ is obtained from $\mathbf{P}$ by adding two voters with reversed ballots, then if $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ , $x$ defeats $y$ in $\mathbf{P}$ .

Example 33

Consider the Plurality VCCR from Example 14. Let $\mathbf{P}$ be any profile for candidates $a,b,c$ . Adding to $\mathbf{P}$ a pair of voters with the reversed ballots $abc$ and $cba$ to obtain a profile ${\mathbf{P}}^{\prime }$ increases the plurality scores of $a$ and $c$ by one but does not increase the plurality score of $b$ . From here it is easy to see that the Plurality VCCR violates both Upward and Downward Neutral Reversal.

Example 34

The Pareto VCCR $f$ is defined as follows: for any profile $\mathbf{P}$ and $x,y\in X(\mathbf{P})$ , $x$ defeats $y$ in $\mathbf{P}$ if and only if all voters in $\mathbf{P}$ rank $x$ above $y$ . Clearly adding two voters with reversed ballots to a profile in which $x$ is unanimously ranked above $y$ results in a profile in which $x$ is not unanimously ranked above $y$ . Thus, the Pareto VCCR violates Upward Neutral Reversal. However, it trivially satisfies Downward Neutral Reversal, because if ${\mathbf{P}}^{\prime }$ has a pair of voters with reversed ballots, then no candidates defeat any other in ${\mathbf{P}}^{\prime }$ .

The Pareto VCCR seems reasonable for certain special purposes; for example, in a small club, unanimity may be valued and often possible. However, in elections where disagreement is expected, the Pareto VCCR would be of little help in narrowing down the range of potential winners, as so few candidates would defeat others. Of course, we agree that it is a sufficient condition for $x$ to defeat $y$ that $x$ is unanimously ranked above $y$ . A VCCR $f$ is said to satisfy the Pareto axiom if for all profiles $\mathbf{P}$ and $x,y\in X(\mathbf{P})$ , if $x{\mathbf{P}}_{i}y$ for all $i\in V(\mathbf{P})$ , then $x$ defeats $y$ in $\mathbf{P}$ according to $f$ . Split Cycle clearly satisfies the Pareto axiom, since there cannot be a majority cycle all of whose margins are equal to the total number of voters. Moreover, we can use Pareto and Upward Neutral Reversal to derive the converse of Special Majority Defeat (Lemma 30), thereby obtaining a characterization of majority rule for two-candidate elections that differs from May’s (1952) famous characterization (cf. Aşan and Sanver 2002; Woeginger 2002; and Llamazares 2006, Cor. 12).

Proposition 35

For any VCCR $f$ , the following are equivalent:

$f$ coincides with majority rule on two-candidate profiles;

$f$ satisfies the following axioms with respect to two-candidate profiles: Anonymity, Neutrality, Monotonicity, Pareto, and Upward Neutral Reversal.

Proof

The implication from 1 to 2 is easy to check. From 2 to 1, we already proved in Lemma 30 that if $f$ satisfies Anonymity, Neutrality, and Monotonicity for two-candidate profiles, then in such a profile, $x$ defeats $y$ only if $x$ is majority preferred to $y$ . We now use Pareto and Upward Neutral Reversal to show that if $x$ is majority preferred to $y$ , then $x$ defeats $y$ . For suppose $\mathbf{P}$ is a two-candidate profile in which $x$ is majority preferred to $y$ . Consecutively remove pairs of voters $(i,j)$ with $x{\mathbf{P}}_{i}y$ and $y{\mathbf{P}}_{j}x$ until we obtain a profile ${\mathbf{P}}_0$ in which all voters rank $x$ over $y$ . By Pareto, $x$ defeats $y$ in ${\mathbf{P}}_0$ . Then by repeated application of Upward Neutral Reversal, adding back the removed pairs of voters, $x$ defeats $y$ in $\mathbf{P}$ .  □

We prefer this characterization of majority rule to that of May (1952) for the reason given in Remark 31.

4.3. Coherent IIA and the Fallacy of IIA

Suppose $x$ defeats $y$ in a profile $\mathbf{P}$ , and a profile ${\mathbf{P}}^{\prime }$ is exactly like $\mathbf{P}$ with respect to how every voter ranks $x$ versus $y$ . Should it follow that $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ ? Arrow’s (1963) famous axiom of IIA says “yes” (see Section 6.1). But we say “no” if ${\mathbf{P}}^{\prime }$ is more incoherent than $\mathbf{P}$ , in terms of cycles. If ${\mathbf{P}}^{\prime }$ is sufficiently incoherent, we may need to suspend judgment on many defeat relations that we could coherently accept in $\mathbf{P}$ . To overlook this point is to commit what we call the Fallacy of IIA. ²²

Although there is a perfectly reasonable notion of the advantage of $x$ over $y$ that only depends on how voters rank $x$ versus $y$ , whether that intrinsic advantage is sufficient for $x$ to defeat $y$ may depend on a standard that takes into account the whole election—for example, that takes into account whether the electorate is incoherent with respect to a set of candidates including $x,y$ (see Holliday and Kelley 2021 for a formalization of the advantage-standard idea). That standards may be context dependent should be no surprise: just as whether a person counts as “tall” depends on who else is being assessed for tallness in the context of our judgment, whether one candidate’s performance against another counts as “a defeat” depends on which other pairwise candidate performances are also being assessed as potential defeats in the context of our judgment. ²³

Example 36

In the profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ below, we have ${\mathbf{P}}_{\mid \{a,b\}}={\mathbf{P}}_{\mid \{a,b\}}^{\prime }$ . In the context of the perfectly coherent profile $\mathbf{P}$ , the margin of $n$ for $a$ over $b$ should be sufficient for $a$ to defeat $b$ . But in the context of the incoherent profile ${\mathbf{P}}^{\prime }$ , it is not sufficient: no one can be judged to defeat anyone else (this follows from Anonymity, Neutrality, and Availability). Thus, this is a counterexample to IIA.

However, it is not as if the standard for defeat in every case of a majority cycle is unattainable. In the profile $\mathbf{Q}$ below, we believe that the advantage of $a$ over $b$ is sufficient for $a$ to defeat $b$ :

According to Split Cycle, the standard for $a$ to defeat $b$ in a profile, which the margin of $a$ over $b$ must surpass, is the maximum of the splitting numbers of the cycles containing $a$ and $b$ . Since the splitting number of the cycle in the profile $\mathbf{Q}$ is 1, the margin of $a$ over $b$ surpasses the standard, so $a$ defeats $b$ .

Remark 37

In an illuminating result, Patty and Penn (2014) prove that Arrow’s IIA is equivalent to the condition of unilateral flip independence, which states that if two profiles are alike except that one voter flips one pair of adjacent candidates on her ballot, then the defeat relations for the two profiles can differ at most on the flipped candidates. They write that this theorem “demonstrates a fundamental basis of the normative appeal of IIA” (p. 52) (cf. Patty and Penn 2019, 155). ²⁴ However, observe that for the profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ in Example 36, if $n=1$ , then a single voter (the middle voter) flipping adjacent candidates on her ballot ( $ac$ to $ca$ ) takes us from the coherent profile $\mathbf{P}$ , in which there is no difficulty in judging that $a$ defeats $b$ , to the incoherent profile ${\mathbf{P}}^{\prime }$ , in which no one can be judged to defeat anyone else. Hence unilateral flip independence makes the same mistake as IIA in ignoring how context can affect the standard for defeat.

Remark 38

Maskin (2020) proposes a weakening of IIA called Modified IIA, which states that if profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ are alike in how every voter ranks $x$ versus $y$ , and for each voter $i$ and candidate $z$ , $i$ ranks $z$ in between $x$ and $y$ in $\mathbf{P}$ if and only if $i$ ranks $z$ in between $x$ and $y$ in ${\mathbf{P}}^{\prime }$ , then $x$ defeats $y$ in $\mathbf{P}$ if and only if $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ . Saari (1994, 1995, 1998) proposed a stronger axiom, though still weaker than IIA, called Intensity IIA: if profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ are alike in how every voter ranks $x$ versus $y$ , and for each voter $i$ , the number of candidates whom $i$ ranks in between $x$ and $y$ in $\mathbf{P}$ is the same as the number of candidates whom $i$ ranks in between $x$ and $y$ in ${\mathbf{P}}^{\prime }$ , then $x$ defeats $y$ in $\mathbf{P}$ if and only if $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ . Modified IIA and Intensity IIA are problematic for the same reason that IIA is, only we now need four candidates to see why. In the profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ below, we have ${\mathbf{P}}_{\mid \{a,b\}}={\mathbf{P}}_{\mid \{a,b\}}^{\prime }$ , and for each voter $i$ and candidate $z$ , $i$ ranks $z$ in between $a$ and $b$ in $\mathbf{P}$ if and only if $i$ ranks $z$ in between $a$ and $b$ in ${\mathbf{P}}^{\prime }$ . In the context of the perfectly coherent profile $\mathbf{P}$ , the margin of $2n$ for $a$ over $b$ should be sufficient for $a$ to defeat $b$ . But in the context of the incoherent profile ${\mathbf{P}}^{\prime }$ , it is not sufficient: no one can be judged to defeat anyone else (this follows from Anonymity, Neutrality, and Availability). Thus, this is a counterexample to Modified IIA and Intensity IIA.

Maskin (2020) suggests the benefit of Modified IIA is that it rules out vote-splitting, which he illustrates using spoiler effects in Plurality voting as in Examples 1 and 3. However, Modified IIA is neither necessary nor sufficient for a voting procedure to have good anti-spoiler properties. Split Cycle does not satisfy Modified IIA—it correctly says that $a$ defeats $b$ in $\mathbf{P}$ but not ${\mathbf{P}}^{\prime }$ above—yet Split Cycle satisfies strong anti-spoiler properties: not only Independence of Clones (Tideman 1987), as shown in Holliday and Pacuit 2020, but also a condition of Immunity to Spoilers, as shown below. On the other hand, Borda satisfies Modified IIA yet satisfies neither Independence of Clones nor Immunity to Spoilers, as shown in Example 43 below.

Avoiding the Fallacy of IIA does not mean abandoning the idea behind IIA entirely. ²⁵ We need only depart from its local evaluation of $x$ versus $y$ when increasing incoherence demands that we are more conservative in locking in relations of defeat. If there is no increase in incoherence from profile $\mathbf{P}$ to ${\mathbf{P}}^{\prime }$ , then if the intrinsic advantage of $x$ over $y$ is sufficient for $x$ to defeat $y$ in $\mathbf{P}$ , we think it should still be sufficient for $x$ to defeat $y$ in ${\mathbf{P}}^{\prime }$ . Moreover, a clearly sufficient condition for there to be no increase in incoherence from $\mathbf{P}$ to ${\mathbf{P}}^{\prime }$ is the following: the margin graph of ${\mathbf{P}}^{\prime }$ is obtained from that of $\mathbf{P}$ by deleting zero or more candidates other than $x$ and $y$ and deleting or reducing the margins on zero or more edges not connecting $x$ and $y$ . ²⁶ For such deletions or reductions can only reduce incoherence. For example, in the profile $\mathbf{Q}$ in Example 36, deleting candidate $c$ or deleting or reducing the margins on the $c\to a$ or $b\to c$ edges only reduces incoherence, so $a$ ’s defeat of $b$ should be preserved. Thus, we arrive at our proposed axiom of Coherent IIA.

A6. Coherent IIA: if $x$ defeats $y$ in $\mathbf{P}$ , and ${\mathbf{P}}^{\prime }$ is a profile such that ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ and the margin graph of ${\mathbf{P}}^{\prime }$ is obtained from that of $\mathbf{P}$ by deleting zero or more candidates other than $x$ and $y$ and deleting or reducing the margins on zero or more edges not connecting $x$ and $y$ , then $x$ still defeats $y$ in ${\mathbf{P}}^{\prime }$ .

In Section 6.1.2, we show that Coherent IIA implies Weak IIA (Baigent 1987): if two profiles are exactly alike with respect to how every voter ranks $x$ versus $y$ , it cannot be that in one profile $x$ defeats $y$ while in the other profile $y$ defeats $x$ . At most, a defeat that holds in one can be withdrawn in the other.

Proposition 39

Split Cycle satisfies Coherent IIA.

Proof

Suppose $x$ defeats $y$ in $\mathbf{P}$ , so by Lemma 26, $Margi{n}_{\mathbf{P}}(x,y)>Split{\mathrm{\#}}_{\mathbf{P}}(\rho )$ for every majority cycle $\rho$ in $\mathbf{P}$ containing $x$ and $y$ . Since ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ , $Margi{n}_{\mathbf{P}}(x,y)=Margi{n}_{{\mathbf{P}}^{\prime }}(x,y)$ . Since $\mathcal{M}({\mathbf{P}}^{\prime })$ is obtained from $\mathcal{M}(\mathbf{P})$ by deleting zero or more candidates other than $x$ and $y$ and zero or more edges not connecting $x$ and $y$ , every majority cycle $\rho$ in ${\mathbf{P}}^{\prime }$ containing $x$ and $y$ is already a majority cycle in $\mathbf{P}$ containing $x$ and $y$ , and as no margins have increased from $\mathbf{P}$ to ${\mathbf{P}}^{\prime }$ , $Split{\mathrm{\#}}_{\mathbf{P}}(\rho )\ge Split{\mathrm{\#}}_{{\mathbf{P}}^{\prime }}(\rho )$ . It follows that $Margi{n}_{{\mathbf{P}}^{\prime }}(x,y)>Split{\mathrm{\#}}_{{\mathbf{P}}^{\prime }}(\rho )$ for every majority cycle $\rho$ in ${\mathbf{P}}^{\prime }$ containing $x$ and $y$ . Thus, $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ by Lemma 26.  □

Unlike our proposed axioms in previous sections, Coherent IIA significantly cuts down the space of allowable VCCRs, ruling out all the VCCRs in Examples 14 and 19 except for Simple Majority. For example, it rules out the Borda VCCR as follows.

Example 40

To see that Borda fails Coherent IIA, consider the following profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ :

According to the Borda VCCR, $x$ defeats $y$ in $\mathbf{P}$ : despite the fact that only one person prefers $x$ to $y$ , whereas three prefer $y$ to $x$ , the proponent of Borda ascribes some significance to the fact that the first voter places $a,b,c$ between $x$ and $y$ (perhaps strategically, of course). Now although ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ and the margin graph of ${\mathbf{P}}^{\prime }$ is obtained from that of $\mathbf{P}$ by deleting some edges not connecting $x$ and $y$ , Borda changes the verdict for ${\mathbf{P}}^{\prime }$ and says that $y$ defeats $x$ in ${\mathbf{P}}^{\prime }$ . Thus, Borda violates Coherent IIA. The mistake, in our view, was to judge that $x$ defeats $y$ in $\mathbf{P}$ in the first place. According to Split Cycle, by contrast, $y$ defeats $x$ in $\mathbf{P}$ because $y$ is majority preferred to $x$ and there are no majority cycles in $\mathbf{P}$ .

Example 62 shows that Borda fails to satisfy the principle of Majority Defeat from Section 1: if $x$ defeats $y$ in $\mathbf{P}$ , then $x$ is majority preferred to $y$ in $\mathbf{P}$ .

Lemma 41

Anonymity, Neutrality, Monotonicity (for two-candidate profiles), and Coherent IIA together imply Majority Defeat.

Proof

Suppose $x$ defeats $y$ in $\mathbf{P}$ . Then by Coherent IIA, $x$ defeats $y$ in ${\mathbf{P}}_{\mid \{x,y\}}$ . Given Anonymity, Neutrality, and Monotonicity, it follows by Lemma 30 that $x$ is majority preferred to $y$ in ${\mathbf{P}}_{\mid \{x,y\}}$ and hence in $\mathbf{P}$ .  □

Remark 42

Whenever an election has a Condorcet winner, Majority Defeat implies that the Condorcet winner is undefeated, but it does not imply that the Condorcet winner is the only undefeated candidate. Thus, Majority Defeat does not by itself imply Condorcet consistency.

Finally, we will show that Coherent IIA (together with Anonymity, Neutrality, and Monotonicity) rules out the kind of spoiler effects shown in Examples 1 to 3. For this, we must consider an election with and without a potential spoiler. Given a profile $\mathbf{P}$ and $b\in X(\mathbf{P})$ , let ${\mathbf{P}}_{-b}$ be the profile obtained from $\mathbf{P}$ by deleting $b$ from all ballots. ²⁷ In Holliday and Pacuit 2020, we define the following axiom:

Immunity to Spoilers: if $a$ is undefeated in ${\mathbf{P}}_{-b}$ , and $a$ is majority preferred to $b$ in $\mathbf{P}$ , and $b$ is defeated in $\mathbf{P}$ , then $a$ is still undefeated in $\mathbf{P}$ .

Examples 1 and 3 show how Plurality voting can violate Immunity to Spoilers. In the first example, assume Gore would win in the two-candidate profile ${\mathbf{P}}_{-\mathrm{Nader}}$ and that Gore is majority preferred to Nader in the full election $\mathbf{P}$ . Then since Nader is defeated in $\mathbf{P}$ , Immunity to Spoilers requires that Nader not spoil the election for Gore, that is, that Gore is still a winner in $\mathbf{P}$ . The analysis of Example 3 is similar, making some assumptions about voters’ rankings of Cruz, Kasich, and Rubio. Example 2 shows how Instant Runoff voting can violate Immunity to Spoilers. Montroll wins in the two-candidate profile ${\mathbf{P}}_{-\mathrm{Wright}}$ , and Montroll is majority preferred to Wright in the full election $\mathbf{P}$ . Then since Wright is defeated in $\mathbf{P}$ , Immunity to Spoilers requires that Wright not spoil the election for Montroll, that is, that Montroll is still a winner in $\mathbf{P}$ .

To see how Borda violates Immunity to Spoilers, consider the following.

Example 43

Let ${\mathbf{P}}_{-b}$ and $\mathbf{P}$ be the following profiles:

According to Borda, $a$ defeats $c$ in ${\mathbf{P}}_{-b}$ . Note that $a$ is majority preferred to $b$ in $\mathbf{P}$ , and $b$ is defeated in $\mathbf{P}$ by both $a$ and $c$ according to Borda. But the addition of the loser $b$ spoils the election for $a$ , as $c$ defeats $a$ in $\mathbf{P}$ according to Borda. This violates Immunity to Spoilers. It also violates Independence of Clones (Tideman 1987), as $b$ is a clone of $c$ (no candidates appear in between $b$ and $c$ on any voter’s ballot). Finally, $c$ defeating $a$ in $\mathbf{P}$ but not in ${\mathbf{P}}_{-b}$ is another violation of Coherent IIA (see the proof of Proposition 44).

In fact, Coherent IIA (together with the other mentioned axioms) implies an even strong anti-spoiler axiom from Holliday and Pacuit 2020:

Stability for Winners (respectively, Strong Stability for Winners): if $a$ is undefeated in ${\mathbf{P}}_{-b}$ , and $a$ is majority preferred to $b$ in $\mathbf{P}$ (respectively, $b$ is not majority preferred to $a$ in $\mathbf{P}$ ), then $a$ is still undefeated in $\mathbf{P}$ .

Proposition 44

Anonymity, Neutrality, Monotonicity (for two-candidate profiles), and Coherent IIA together imply Strong Stability for Winners.

Proof

Suppose $a$ is undefeated in ${\mathbf{P}}_{-b}$ according to $f$ and that $b$ is not majority preferred to $a$ in $\mathbf{P}$ . Suppose for contradiction that $a$ is defeated in $\mathbf{P}$ according to $f$ . Since $b$ is not majority preferred to $a$ in $\mathbf{P}$ , it follows by Lemma 41 that $b$ does not defeat $a$ in $\mathbf{P}$ according to $f$ . Hence there is some $c\in X(\mathbf{P})\setminus \{b\}$ that defeats $a$ in $\mathbf{P}$ according to $f$ . Then since ${\mathbf{P}}_{\mid \{a,c\}}=({\mathbf{P}}_{-b}{)}_{\mid \{a,c\}}$ and the margin graph of ${\mathbf{P}}_{-b}$ is obtained from that of $\mathbf{P}$ by deleting a candidate other than $a$ and $c$ , it follows by Coherent IIA that $c$ defeats $a$ in ${\mathbf{P}}_{-b}$ according to $f$ , contradicting our initial assumption.  □

Thus, contrary to Maskin 2020, it is Coherent IIA rather than Modified IIA that mitigates spoiler effects.

5. Characterization

In this section, we prove our main result using the axioms proposed in Section 4. Given VCCRs $f$ and $g$ , we say that $g$ is a refinement of $f$ if for every profile $\mathbf{P}$ and $x,y\in X(\mathbf{P})$ , if $x$ defeats $y$ in $\mathbf{P}$ according to $f$ , then $x$ defeats $y$ in $\mathbf{P}$ according to $g$ . It follows that the set of candidates selected by $\overline{g}$ (i.e., the set of undefeated candidates according to $g$ ) is always a subset of the set of candidates selected by $\overline{f}$ (i.e., the set of undefeated candidates according to $f$ ). Thus, a refinement extends the defeat relation and may shrink the set of potential winners.

Given a class $\mathsf{C}$ of VCCRs and $g\in \mathsf{C}$ , we say that $g$ is the most resolute VCCR in $C$ if $g$ is a refinement of every VCCR in $\mathsf{C}$ , or equivalently, if for every $f\in \mathsf{C}$ , profile $\mathbf{P}$ , and $x,y\in X(\mathbf{P})$ , if $x$ defeats $y$ in $\mathbf{P}$ according to $f$ , then $x$ defeats $y$ in $\mathbf{P}$ according to $g$ . A number of voting procedures can be characterized as “the most resolute procedure satisfying such and such properties” (see, e.g., Brandt et al. 2013; Brandt and Seedig 2014). We now give such a characterization of Split Cycle.

Figure 1.

The profile ${\mathbf{P}}^{\prime }$ .

Figure 2.

The profile $\sigma ({\mathbf{P}}^{\prime })$ .

Theorem 45

Split Cycle is the most resolute of all VCCRs satisfying the six axioms for defeat:

A1. Anonymity and Neutrality: if $x$ defeats $y$ in $\mathbf{P}$ , and ${\mathbf{P}}^{\prime }$ is obtained from $\mathbf{P}$ by swapping the ballots assigned to two voters, then $x$ still defeats $y$ in ${\mathbf{P}}^{\prime }$ (Anonymity); and if $x$ defeats $y$ in $\mathbf{P}$ , and ${\mathbf{P}}^{\prime }$ is obtained from $\mathbf{P}$ by swapping $x$ and $y$ on each voter’s ballot, then $y$ defeats $x$ in ${\mathbf{P}}^{\prime }$ (Neutrality).

A2. Availability: for every $\mathbf{P}$ , there is some undefeated candidate in $\mathbf{P}$ .

A3. (Upward) Homogeneity: for every $\mathbf{P}$ , if $x$ defeats $y$ in $\mathbf{P}$ , then $x$ defeats $y$ in $2\mathbf{P}$ .

A4. Monotonicity (for two-candidate profiles): if $x$ defeats $y$ in $\mathbf{P}$ (a two-candidate profile), and ${\mathbf{P}}^{\prime }$ is obtained from $\mathbf{P}$ by some voter $i$ moving $x$ above the candidate that $i$ ranked immediately above $x$ in $\mathbf{P}$ , then $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ .

A5. Neutral Reversal: if ${\mathbf{P}}^{\prime }$ is obtained from $\mathbf{P}$ by adding two voters with reversed ballots, then $x$ defeats $y$ in $\mathbf{P}$ if and only if $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ .

A6. Coherent IIA: if $x$ defeats $y$ in $\mathbf{P}$ , and ${\mathbf{P}}^{\prime }$ is a profile such that ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ and the margin graph of ${\mathbf{P}}^{\prime }$ is obtained from that of $\mathbf{P}$ by deleting zero or more candidates other than $x$ and $y$ and deleting or reducing the margins on zero or more edges not connecting $x$ and $y$ , then $x$ still defeats $y$ in ${\mathbf{P}}^{\prime }$ .

Proof

We have already observed that Split Cycle satisfies the axioms. Next, we show that for any VCCR $f$ satisfying the axioms for defeat and any profile $\mathbf{P}$ , if $x$ defeats $y$ in $\mathbf{P}$ according to $f$ , then $x$ defeats $y$ in $\mathbf{P}$ according to Split Cycle. Toward a contradiction, suppose $x$ defeats $y$ in $\mathbf{P}$ according to $f$ but not according to Split Cycle. Since $\mathbf{P}$ may have an odd number of voters, consider $2\mathbf{P}$ . It follows by (Upward) Homogeneity that $x$ defeats $y$ in $2\mathbf{P}$ according to $f$ . But according to Split Cycle, $x$ does not defeat $y$ in $2\mathbf{P}$ (whose qualitative margin graph is the same as $\mathbf{P}$ ). Since $x$ defeats $y$ according to $f$ , by Majority Defeat (Lemma 41), we have $Margi{n}_{2\mathbf{P}}(x,y)>0$ . Moreover, since $2\mathbf{P}$ has an even number of voters, $Margi{n}_{2\mathbf{P}}(x,y)$ is even. Now since $x$ does not defeat $y$ in $2\mathbf{P}$ according to Split Cycle, by Lemma 26 there is a majority cycle $x\to y\to z_1\to \cdots \to z_n\to x$ in $2\mathbf{P}$ such that $Margi{n}_{2\mathbf{P}}(x,y)$ is less than or equal to every margin along the cycle. Let $\mathbf{Q}$ be obtained from $\mathbf{2}\mathbf{P}$ by adding zero or more reversal pairs of voters so that $|V(\mathbf{Q})|\ge (n+2)Margi{n}_{2\mathbf{P}}(x,y)$ . Then by (Upward) Neutral Reversal, $x$ defeats $y$ in $\mathbf{Q}$ according to $f$ . Let ${\mathcal{M}}^{\prime }$ be the weighted directed graph obtained from $\mathcal{M}(2\mathbf{P})$ by deleting all candidates except $x,y,z_1,\dots ,z_n$ and all edges except the edges in the cycle and reducing the weights on all remaining edges so they are equal to $Margi{n}_{2\mathbf{P}}(x,y)$ . Let $k=Margi{n}_{2\mathbf{P}}(x,y)/2$ . We now construct a profile ${\mathbf{P}}^{\prime }$ whose margin graph is ${\mathcal{M}}^{\prime }$ . ²⁸ For each edge $a\to b$ in $x\to y\to z_1\to \cdots \to z_n\to x$ , where $c_1,\dots ,c_n$ are the elements from $\{x,y,z_1,\dots ,z_n\}\setminus \{a,b\}$ such that $b\to c_1\to \cdots \to c_n\to a$ , we add voters to ${\mathbf{P}}^{\prime }$ as follows:

If $a=x$ (and hence $b=y$ ), then for $k$ voters from $V(\mathbf{Q})$ who rank $x$ above $y$ in $\mathbf{Q}$ , add them to ${\mathbf{P}}^{\prime }$ with the ballot $\mathit{a},\mathit{b},c_1,\dots ,c_n$ (which in this case is $\mathit{x},\mathit{y},z_1,\dots ,z_n$ ), and for $k$ other voters from $V(\mathbf{Q})$ who rank $x$ above $y$ in $\mathbf{Q}$ , add them to ${\mathbf{P}}^{\prime }$ with the ballot $c_n,\dots ,c_1,\mathit{a},\mathit{b}$ (which in this case is $z_1,\dots ,z_n,\mathit{x},\mathit{y}$ ). See the first and second columns in the profile in Figure 1.

If $a\ne x$ and $y$ occurs before $x$ in the sequence $b,c_1,\dots ,c_n,a$ , then for $k$ voters from $V(\mathbf{Q})$ who rank $y$ above $x$ in $\mathbf{Q}$ , add them to ${\mathbf{P}}^{\prime }$ with the ballot $\mathit{a},\mathit{b},c_1,\dots ,c_n$ , and for $k$ voters from $V(\mathbf{Q})$ who rank $x$ above $y$ in $\mathbf{Q}$ , add them to ${\mathbf{P}}^{\prime }$ with the ballot $c_n,\dots ,c_1,\mathit{a},\mathit{b}$ . See, for example, the third and fourth columns in the profile in Figure 1.

If $a\ne x$ and $x$ occurs before $y$ in the sequence $b,c_1,\dots ,c_n,a$ , then for $k$ voters from $V(\mathbf{Q})$ who rank $x$ above $y$ in $\mathbf{Q}$ , add them to ${\mathbf{P}}^{\prime }$ with the ballot $\mathit{a},\mathit{b},c_1,\dots ,c_n$ , and for $k$ voters from $V(\mathbf{Q})$ who rank $y$ above $x$ in $\mathbf{Q}$ , add them to ${\mathbf{P}}^{\prime }$ with the ballot $c_n,\dots ,c_1,\mathit{a},\mathit{b}$ . See, for example, the fifth and sixth columns in the profile in Figure 1.

This construction uses $2k+(n+1)k$ voters from $V(\mathbf{Q})$ who rank $x$ over $y$ and $(n+1)k$ voters from $V(\mathbf{Q})$ who rank $y$ over $x$ , for a total of $(n+2)Margi{n}_{2\mathbf{P}}(x,y)$ voters from $V(\mathbf{Q})$ . Then ${\mathbf{P}}^{\prime }$ has the form in Figure 1. Observe that $\mathcal{M}({\mathbf{P}}^{\prime })={\mathcal{M}}^{\prime }$ (e.g., $Margi{n}_{{\mathbf{P}}^{\prime }}(x,y)=2k=Margi{n}_{2\mathbf{P}}(x,y)$ , $Margi{n}_{{\mathbf{P}}^{\prime }}(x,z_1)=0$ , etc.).

Now we claim that $x$ does not defeat $y$ in ${\mathbf{P}}^{\prime }$ according to $f$ . Toward a contradiction, suppose $x$ does defeat $y$ in ${\mathbf{P}}^{\prime }$ according to $f$ . Let $\sigma ({\mathbf{P}}^{\prime })$ be the profile obtained from ${\mathbf{P}}^{\prime }$ by the permutation $\sigma$ that maps each $a\in \{x,y,z_1,\dots ,z_n\}$ to the unique $b\in \{x,y,z_1,\dots ,z_n\}$ such that $a\to b$ in ${\mathbf{P}}^{\prime }$ , as shown in Figure 2.

By Neutrality, ²⁹ since $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ , it follows that $y$ defeats $z_1$ in $\sigma ({\mathbf{P}}^{\prime })$ . But ${\mathbf{P}}^{\prime }$ can obviously be obtained from $\sigma ({\mathbf{P}}^{\prime })$ by a permutation of the voters (e.g., in Figures 1 and 2, the first column in ${\mathbf{P}}^{\prime }$ is the same as the second to last column in $\sigma ({\mathbf{P}}^{\prime })$ ). Thus, by Anonymity, since $y$ defeats $z_1$ in $\sigma ({\mathbf{P}}^{\prime })$ , it follows that $y$ defeats $z_1$ in ${\mathbf{P}}^{\prime }$ . By similar reasoning using $\sigma (\sigma ({\mathbf{P}}^{\prime }))$ , we have that $z_1$ defeats $z_2$ in ${\mathbf{P}}^{\prime }$ , etc., until we conclude that $xDyD{z}_{1}D\cdots D{z}_{n}Dx$ where $D$ is the defeat relation in ${\mathbf{P}}^{\prime }$ . This contradicts Availability. Hence $x$ does not defeat $y$ in ${\mathbf{P}}^{\prime }$ according to $f$ .

Since $V({\mathbf{P}}^{\prime })\subseteq V(\mathbf{Q})$ and $Margi{n}_{\mathbf{Q}}(x,y)=Margi{n}_{{\mathbf{P}}^{\prime }}(x,y)$ , it follows that half of the voters in $V(\mathbf{Q})\setminus V({\mathbf{P}}^{\prime })$ (which may be empty) rank $x$ above $y$ and half of the voters in $V(\mathbf{Q})\setminus V({\mathbf{P}}^{\prime })$ rank $y$ above $x$ . Let ${\mathbf{P}}^{″}$ be obtained from ${\mathbf{P}}^{\prime }$ as follows: for each voter in $V(\mathbf{Q})\setminus V({\mathbf{P}}^{\prime })$ who ranks $x$ above $y$ , add them to ${\mathbf{P}}^{″}$ with the ballot $x,y,z_1,\dots ,z_n$ , and for each voter $V(\mathbf{Q})\setminus V({\mathbf{P}}^{\prime })$ who ranks $y$ above $x$ , add them to ${\mathbf{P}}^{″}$ with the ballot $z_n,\dots ,z_1,y,x$ . Thus, ${\mathbf{P}}^{″}$ is obtained from ${\mathbf{P}}^{\prime }$ by adding zero or more reversal pairs of voters, so by (Downward) Neutral Reversal, since $x$ does not defeat $y$ in ${\mathbf{P}}^{\prime }$ according to $f$ , it follows that $x$ does not defeat $y$ in ${\mathbf{P}}^{″}$ according to $f$ . Finally, we have:

$V(\mathbf{Q})=V({\mathbf{P}}^{″})$ and ${\mathbf{Q}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{″}$ ;

$\mathcal{M}({\mathbf{P}}^{″})$ is obtained from $\mathcal{M}(\mathbf{Q})$ by deleting zero or more candidates other than $x$ and $y$ and deleting or reducing the margins on zero or more edges other than the $x\to y$ edge.

Thus, by Coherent IIA, since $x$ defeats $y$ in $\mathbf{Q}$ according to $f$ , we have that $x$ defeats $y$ in ${\mathbf{P}}^{″}$ according to $f$ , contradicting what we derived above. □

Of course Split Cycle is not the only VCCR that satisfies the six axioms for defeat. For example, the null VCCR according to which no one ever defeats anyone else satisfies all six axioms—although it can easily be ruled out by other axioms that Split Cycle satisfies, such as the Pareto axiom. Another example is the VCCR according to which $x$ defeats $y$ if $Margi{n}_{\mathbf{P}}(x,y)$ is greater than the splitting number of every majority cycle in $\mathbf{P}$ , not only those majority cycles containing $x$ and $y$ . Since these VCCRs are not refinements of Split Cycle, ³⁰ they do not satisfy the seventh “axiom” that the VCCR should be the most resolute VCCR among those satisfying the first six axioms. A natural next step would be to obtain another axiomatic characterization of Split Cycle as the only VCCR satisfying some axioms without reference to resoluteness.

Theorem 45 shows that using a VCCR other than Split Cycle requires either violating one of the six axioms for defeat or sacrificing resoluteness. For these and other reasons (see Holliday and Pacuit 2020), we settle on Split Cycle as our preferred VCCR and hence as our preferred answer to the question of when one candidate should defeat another in a democratic election using ranked ballots.

Remark 46

When there are multiple undefeated candidates, but a single winner must be chosen, some further tiebreaking process must select the ultimate winner from the undefeated candidates. However, we need not interpret that process as establishing additional relations of defeat between candidates in the politically significant sense of defeat. This is obvious if we randomly choose the ultimate winner from the undefeated candidates. But the point may also apply if we first make a deterministic choice of a subset of undefeated candidates before resorting to random choice if necessary.

6. Escaping impossibility

In this section, we address the question: how does Split Cycle escape Arrow’s Impossibility theorem and related impossibility results? That is, how did we relax Arrow’s assumptions to avoid the existence of a dictator, vetoers, etc.? In Section 6.1, we recall the standard formulation of Arrow’s theorem and related results, and we explain how Split Cycle escapes these results. In Section 6.2, we reformulate these results in the variable-candidate setting in which we characterized Split Cycle. Finally, in Section 6.3, we consider some simple impossibility results based not on IIA but instead on a choice-consistency principle sometimes conflated with IIA, allegedly even by Arrow himself (see Appendix B).

6.1. Impossibility theorems in the fixed-candidate setting

6.1.1. Arrow’s Theorem

Arrow (1963) worked in a fixed-voter and fixed-candidate setting (see Campbell and Kelly 2002 and Penn 2015 for modern presentations). Fix nonempty finite sets $V$ and $X$ of voters and candidates, respectively. A $(V,X)$ -profile is a profile $\mathbf{P}$ as in Definition 4 in which $V(\mathbf{P})=V$ and $X(\mathbf{P})=X$ . A ( $V,X$ )-collective choice rule (or $(V,X)$ -CCR) is a function on the set of $(V,X)$ -profiles such that for any $(V,X)$ -profile $\mathbf{P}$ , $f(\mathbf{P})$ is an asymmetric binary relation on $X$ . ³¹ If $f$ is a VCCR as in Section 2, then for any finite $V\subset \mathcal{V}$ and finite $X\subset \mathcal{X}$ , the restriction $f_{\mid V,X}$ of $f$ to the set of $(V,X)$ -profiles is a $(V,X)$ -CCR. In particular, for any such $(V,X)$ , the Split Cycle VCCR restricts to the Split Cycle $(V,X)$ -CCR. Our question is: how does the Split Cycle $(V,X)$ -CCR escape Arrow’s theorem?

Let $f$ be a $(V,X)$ -CCR. To state Arrow’s theorem, we recall the following key notions:

$f$ is a $(V,X)$ -social welfare function (or $(V,X)$ -SWF) if for any $(V,X)$ -profile $\mathbf{P}$ , $f(\mathbf{P})$ is a strict weak order (recall Section 2);

$f$ satisfies IIA if for any $(V,X)$ -profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ and $x,y\in X$ , if ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ , then $x$ defeats $y$ in $\mathbf{P}$ according to $f$ if and only if $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ according to $f$ ;

$f$ satisfies Pareto if for any $(V,X)$ -profile $\mathbf{P}$ and $x,y\in X$ , if $x{\mathbf{P}}_{i}y$ for all $i\in V$ , then $x$ defeats $y$ in $\mathbf{P}$ according to $f$ ;

an $i\in V$ is a dictator for $f$ if for all $(V,X)$ -profiles $\mathbf{P}$ and $x,y\in X$ , if $x{\mathbf{P}}_{i}y$ , then $x$ defeats $y$ in $\mathbf{P}$ according to $f$ .

Then Arrow’s famous Impossibility theorem can be stated as follows. ³²

Theorem 47 (Arrow 1963)

Assume $|X|\ge 3$ . Any $(V,X)$ -SWF satisfying IIA and Pareto has a dictator.

Remark 48

Since our profiles are profiles of linear ballots, the conclusion of Arrow’s theorem can be strengthened to say that $f$ has a strong dictator, that is, an $i\in V$ such that for all $(V,X)$ -profiles $\mathbf{P}$ and $x,y\in X$ , we have that $x$ defeats $y$ in $\mathbf{P}$ according to $f$ if and only if $x{\mathbf{P}}_{i}y$ , that is, $f(\mathbf{P})={\mathbf{P}}_i$ .

The Split Cycle $(V,X)$ -CCR avoids Arrow’s theorem due to the following facts:

We weaken IIA to Coherent IIA. ³³

We weaken Arrow’s assumption that the defeat relation is a strict weak order to it being acyclic.

Neither of these move by itself is sufficient to escape Arrow-style impossibility theorems, as we show below.

6.1.2. Baigent’s Theorem

To see that weakening IIA to Coherent IIA is not sufficient, we first observe that Coherent IIA implies a weakening of IIA known as Weak IIA, which states that if ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ and $x$ defeats $y$ in $\mathbf{P}$ according to $f$ , then $y$ does not defeat $x$ in ${\mathbf{P}}^{\prime }$ according to $f$ .

Lemma 49

If $f$ is a VCCR satisfying Coherent IIA, then for any finite $V\subset \mathcal{V}$ and finite $X\subset \mathcal{X}$ , $f_{\mid V,X}$ satisfies Weak IIA.

Proof

Suppose that ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ and $x$ defeats $y$ in $\mathbf{P}$ . Then by Coherent IIA, $x$ defeats $y$ in ${\mathbf{P}}_{\mid \{x,y\}}$ , so $y$ does not defeat $x$ in ${\mathbf{P}}_{\mid \{x,y\}}$ . Now if $y$ defeats $x$ in ${\mathbf{P}}^{\prime }$ , then by Coherent IIA, $y$ defeats $x$ in ${\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ and hence in ${\mathbf{P}}_{\mid \{x,y\}}$ , since ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ , which is a contradiction. Therefore, $y$ does not defeat $x$ in ${\mathbf{P}}^{\prime }$ .  □

Under Weak IIA, Baigent (1987) proved an Arrow-style impossibility theorem asserting the existence of a vetoer instead of a dictator. ³⁴ Given a $(V,X)$ -CCR $f$ , a voter $i\in V$ is a vetoer for $f$ if for all $(V,X)$ -profiles $\mathbf{P}$ and $x,y\in X(\mathbf{P})$ , if $x{\mathbf{P}}_{i}y$ , then $y$ does not defeat $x$ in $\mathbf{P}$ according to $f$ .

Theorem 50 (Baigent 1987)

Assume $|X|\ge 4$ . Any $(V,X)$ -SWF satisfying Weak IIA and Pareto has a vetoer.

The existence of a vetoer for an SWF is inconsistent with the SWF satisfying both Pareto and Anonymity.

Proposition 51

Suppose $|V|\ge 2$ and $|X|\ge 3$ . Let $f$ be a $(V,X)$ -SWF satisfying Pareto. If $f$ has a vetoer, then $f$ has a unique vetoer and hence violates Anonymity.

Proof

Suppose there are two vetoers $j$ and $k$ . Consider a profile $\mathbf{P}$ in which (i) $x{\mathbf{P}}_{i}y$ for all $i\in V$ , (ii) $y{\mathbf{P}}_{j}z$ , and (iii) $z{\mathbf{P}}_{k}x$ . By (i) and Pareto, $x$ defeats $y$ in $\mathbf{P}$ according to $f$ . By (ii), $z$ does not defeat $y$ , since $j$ is a vetoer. By (iii), $x$ does not defeat $z$ , since $k$ is a vetoer. But since $f$ is an SWF, $f(\mathbf{P})$ is a strict weak order, so if $x$ defeats $y$ , then either $z$ defeats $y$ or $x$ defeats $z$ . Thus, we have a contradiction.  □

As a corollary of Theorem 50 and Proposition 51, we have the following.

Corollary 52

Assume $|X|\ge 4$ . There is no $(V,X)$ -SWF satisfying Weak IIA, Pareto, and Anonymity.

In light of Lemma 49, Theorem 50, and Corollary 52, only weakening IIA to Coherent IIA is not sufficient to escape Arrow-style impossibility results.

6.1.3. Blau–Deb Theorem

Weakening Arrow’s assumption that the defeat relation is a strict weak order to it being acyclic is also not sufficient by itself. Blau and Deb (1977) prove a vetoer theorem for acyclic CCRs under IIA together with Neutrality and Monotonicity (recall Section 4.1). Let $f$ be a $(V,X)$ -CCR. A coalition $C\subseteq V$ of voters has veto power for $f$ if for any $(V,X)$ -profile $\mathbf{P}$ and $x,y\in X$ , if $x{\mathbf{P}}_{i}y$ for all $i\in C$ , then $y$ does not defeat $x$ in $\mathbf{P}$ according to $f$ .

Theorem 53 (Blau and Deb 1977)

Let $f$ be an acyclic $(V,X)$ -CCR satisfying IIA, Neutrality, and Monotonicity.

For any partition of $V$ into at most $|X|$ -many coalitions, at least one of the coalitions has veto power.

If $|X|\ge |V|$ , then $f$ has a vetoer.

Remark 54

Part 2 is an immediate consequence of part 1 by considering the finest partition.

Remark 55

Inspection of the proof of the Veto Theorem in Blau and Deb 1977 shows that the assumption of acyclicity may be replaced by the weaker axiom of Availability (recall Section 4.1).

As an example of applying Theorem 53.1, if there are five candidates, then for any partition of the electorate into five coalitions—say, five coalitions of equal size—one of the five coalitions has veto power (and hence, assuming Anonymity, all coalitions of the same size would have veto power). Moreover, in the variable-candidate setting, we can use Theorem 53 to prove the existence of a single vetoer under a variable-candidate version of IIA (see Proposition 61 below), without the assumption that $|X|\ge |V|$ . Thus, weakening Arrow’s strict weak order assumption to the assumption of acyclicity (or even Availability) is not enough by itself to escape Arrow-style impossibility theorems, if we would like to retain Neutrality and Monotonicity.

It is the combination of weakening IIA to Coherent IIA and weakening Arrow’s strict weak order assumption to acyclicity that allows Split Cycle to escape Arrow-style impossibility theorems.

6.2. Impossibility theorems in the variable-candidate setting

Since we have analyzed Split Cycle as a VCCR in this paper, to properly make claims about how Split Cycle relates to Arrow-style impossibility theorems, we should recast these results in the variable-election setting. In this setting, there are two versions of Arrow’s IIA.

Definition 56

Let $f$ be a VCCR.

$f$ satisfies fixed-candidate Independence of Irrelevant Alternatives (FIIA) if for any profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ with $X(\mathbf{P})=X({\mathbf{P}}^{\prime })$ , if ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ , then $x$ defeats $y$ in $\mathbf{P}$ according to $f$ if and only if $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ according to $f$ ;

$f$ satisfies variable-candidate Independence of Irrelevant Alternatives (VIIA) if for any profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ with $x,y\in X(\mathbf{P})\cap X({\mathbf{P}}^{\prime })$ , if ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ , then $x$ defeats $y$ in $\mathbf{P}$ according to $f$ if and only if $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ according to $f$ .

We suggest in Appendix B that if asked to formulate his axioms for VCCRs, Arrow would formulate IIA as VIIA. Our Coherent IIA is a weakening of VIIA, as Coherent IIA strengthens the assumption from ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ to the assumption that not only ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ but also that the margin graph of ${\mathbf{P}}^{\prime }$ is obtained from that of $\mathbf{P}$ in a certain way.

Proposition 57

Any VCCR satisfying VIIA also satisfies Coherent IIA.

We reject VIIA in favor of Coherent IIA for the reasons explained in Section 4.3.

Arrow’s Impossibility Theorem can be stated in the variable-election setting using some additional notions. First, given a finite $V\subset \mathcal{V}$ , a $V$ -profile is a profile $\mathbf{P}$ as in Definition 4 in which $V(\mathbf{P})=V$ . Second, given $i\in V$ and finite $X\subset \mathcal{X}$ , we say that $i$ is ( $V,X$ )-dictator (respectively, $V$ -dictator) for $f$ if for any $(V,X)$ -profile (respectively, $V$ -profile) $\mathbf{P}$ and $x,y\in X(\mathbf{P})$ , $x{\mathbf{P}}_{i}y$ implies that $x$ defeats $y$ in $\mathbf{P}$ according to $f$ .

Theorem 58 (Arrow’s theorem for VSWFs)

Suppose $f$ is a VSWF satisfying the Pareto principle.

If $f$ satisfies FIIA, then for any finite sets $V\subset \mathcal{V}$ and $X\subset \mathcal{X}$ with $|X|\ge 3$ , there is a $(V,X)$ -dictator for $f$ .

If $f$ satisfies VIIA, then for any finite set $V\subset \mathcal{V}$ , there is a $V$ -dictator for $f$ .

Proof

For part 1, let $f_{\mid V,X}$ be the restriction of $f$ to $(V,X)$ -profiles. Then $f_{\mid V,X}$ is a $(V,X)$ -SWF as in Section 6 satisfying IIA and Pareto. Since $|X|\ge 3$ , Arrow’s theorem (Theorem 47) gives us the desired $(V,X)$ -dictator for $f$ .

For part 2, consider any finite $V\subset \mathcal{V}$ . Pick some finite $X_0\subset \mathcal{X}$ such that $|X_0|\ge 3$ . Then as in part 1, Arrow’s theorem applied to $f_{\mid V,X_0}$ gives us an $i_{V,X_0}\in V$ who is a $(V,X_0)$ -dictator for $f$ . We claim that $i_{V,X_0}$ is a $V$ -dictator for $f$ . Let $\mathbf{Q}$ be a $V$ -profile. We must show that for all $x,y\in X(\mathbf{Q})$ , $x{\mathbf{Q}}_{i_{V,X_0}}y$ implies that $x$ defeats $y$ in $\mathbf{Q}$ according to $f$ . Suppose $x{\mathbf{Q}}_{i_{V,X_0}}y$ . Let $X=X_0\cup X(\mathbf{Q})$ . Since $|X|\ge 3$ , Arrow’s theorem applied to $f_{\mid V,X}$ gives us an $i_{V,X}\in V$ who is a $(V,X)$ -dictator for $f$ . We claim that $i_{V,X}=i_{V,X_0}$ . Suppose not. There is a $(V,X)$ -profile ${\mathbf{P}}^{\star }$ such that for some $a,b\in X_0$ , voter $i_{V,X_0}$ ranks $a$ above $b$ in ${\mathbf{P}}^{\star }$ while $i_{V,X}$ ranks $b$ above $a$ in ${\mathbf{P}}^{\star }$ . Then since $i_{V,X}$ is a $(V,X)$ -dictator, $b$ defeats $a$ in ${\mathbf{P}}^{\star }$ according to $f$ . Hence by VIIA, $b$ defeats $a$ in ${\mathbf{P}}_{\mid X_0}^{\star }$ according to $f$ . But this contradicts the fact that $i_{V,X_0}$ is a $(V,X_0)$ -dictator, given that $X({\mathbf{P}}_{\mid X_0}^{\star })=X_0$ and $i_{V,X_0}$ ranks $a$ above $b$ in ${\mathbf{P}}_{\mid X_0}^{\star }$ . Hence $i_{V,X}=i_{V,X_0}$ , so $i_{V,X_0}$ is a $(V,X)$ -dictator for $f$ . Now let ${\mathbf{Q}}^{+}$ be any $(V,X)$ -profile such that ${\mathbf{Q}}_{\mid X}^{+}=\mathbf{Q}$ . Then $x{\mathbf{Q}}_{i_{V,X_0}}y$ implies $x{\mathbf{Q}}_{i_{V,X_0}}^{+}y$ , so $x$ defeats $y$ in ${\mathbf{Q}}^{+}$ according to $f$ because $i_{V,X_0}$ is a $(V,X)$ -dictator. Hence by VIIA, $x$ defeats $y$ in $\mathbf{Q}$ according to $f$ , which completes the proof, as shown in Figure 3 with $Y=X(\mathbf{Q})$ .  □

Figure 3.

To show that any $(V,X_0)$ -dictator is also a $(V,Y)$ -dictator, we first show that any $(V,X_0)$ -dictator is also a $(V,X_0\cup Y)$ -dictator and then show that any $(V,X_0\cup Y)$ -dictator is also a $(V,Y)$ -dictator.

Remark 59

As in Remark 48, since our profiles are profiles of linear ballots, the conclusions of parts 1 and 2 of Theorem 58 can be strengthened with “strong dictator” in place of “dictator.”

Remark 60

There are VSWFs satisfying Pareto and VIIA for which there is no $i\in \mathcal{V}$ who is a $V$ -dictator with respect to all finite $V\subset \mathcal{V}$ with $i\in V$ . For example, let $\mathcal{V}$ be the set of natural numbers, and for any profile $\mathbf{P}$ , let $f(\mathbf{P})={\mathbf{P}}_{\max (V(\mathbf{P}))}$ , where $\max (V(\mathbf{P}))$ is the greatest number in the set $V(\mathbf{P})$ . Thus, in the variable-voter setting, Arrow’s axioms are consistent with different electorates having different dictators.

Just as Arrow’s theorem can be adapted to the variable-election setting, so can Baigent’s theorem (Theorem 50), which we leave as an exercise to the reader (hint: use Proposition 51 to obtain the analog of Theorem 58.2). More interesting is the reformulation of the Blau–Deb theorem (Theorem 53) in the variable-election setting—in particular, the variable-candidate setting—as VIIA allow us to strengthen the conclusion of the theorem to state the existence of a vetoer without the restriction that $|X|\ge |V|$ .

To state the variable-candidate version of the Blau–Deb theorem, we need the following notions. Given finite $V\subset \mathcal{V}$ , $i\in V$ , finite $X\subset \mathcal{X}$ , and $a,b\in X$ , we say that:

$i$ is a $(V,X)$ -vetoer for $f$ on ( $a,b$ ) if for all $(V,X)$ -profiles $\mathbf{P}$ , if $a{\mathbf{P}}_{i}b$ , then $b$ does not defeat $a$ in $\mathbf{P}$ according to $f$ ;

$i$ is a $(V,X)$ -vetoer for $f$ if for every $a,b\in X$ , $i$ is a $(V,X)$ -vetoer for $f$ on $(a,b)$ ;

$i$ is a $V$ -vetoer for $f$ if for every finite $X\subset \mathcal{X}$ , $i$ is a $(V,X)$ -vetoer for $f$ .

Theorem 61

If $f$ is a VCCR satisfying VIIA, Availability, Neutrality, and Monotonicity, then for any finite $V\subset \mathcal{V}$ , $f$ has a $V$ -vetoer.

Proof

Consider any finite $V\subset \mathcal{V}$ . Pick some finite $X_0\subset \mathcal{X}$ such that $|X_0|\ge |V|$ . Then Theorem 53.2 (and Remark 55) applied to $f_{\mid V,X_0}$ gives us an $i_{V,X_0}\in V$ who is a $(V,X_0)$ -vetoer for $f$ . We claim that $i_{V,X_0}$ is a $V$ -vetoer for $f$ . Let $\mathbf{Q}$ be a $V$ -profile. We must show that for all $x,y\in X(\mathbf{Q})$ , $x{\mathbf{Q}}_{i_{V,X_0}}y$ implies that $y$ does not defeat $x$ in $\mathbf{Q}$ according to $f$ . Suppose $x{\mathbf{Q}}_{i_{V,X_0}}y$ . Let $X=X_0\cup X(\mathbf{Q})$ . We claim that for any $a,b\in X_0$ , voter $i_{V,X_0}$ is a $(V,X)$ -vetoer on $(a,b)$ . Suppose $\mathbf{P}$ is a $(V,X)$ -profile such that $a{\mathbf{P}}_{i_{V,X_0}}b$ . Then $i_{V,X_0}$ ranks $a$ above $b$ in the restricted profile ${\mathbf{P}}_{\mid X_0}$ , and $i_{V,X_0}$ is a $(V,X_0)$ -vetoer, so $b$ does not defeat $a$ in ${\mathbf{P}}_{\mid X_0}$ , which by VIIA implies that $b$ does not defeat $a$ in $\mathbf{P}$ . Thus, $i_{V,X_0}$ is a $(V,X)$ -vetoer on $(a,b)$ , which by Neutrality implies that $i_{V,X_0}$ is a $(V,X)$ -vetoer. ³⁵ Now let ${\mathbf{Q}}^{+}$ be any $(V,X)$ -profile extending $\mathbf{Q}$ . Then $x{\mathbf{Q}}_{i_{V,X_0}}y$ implies $x{\mathbf{Q}}_{i_{V,X_0}}^{+}y$ , so $y$ does not defeat $x$ in ${\mathbf{Q}}^{+}$ according to $f$ because $i_{V,X_0}$ is a $(V,X)$ -vetoer. Hence by VIIA, $y$ does not defeat $x$ in $\mathbf{Q}$ according to $f$ , which completes the proof.  □

Theorem 61 shows how moving to the variable-candidate setting and interpreting IIA as VIIA can strengthen impossibility theorems. But by weakening VIIA to Coherent IIA, impossibility results like Theorem 61 disappear. Split Cycle satisfies Coherent IIA, Availability, Neutrality, and Monotonicity but has no vetoer.

6.3. Impossibility, independence, and choice consistency

Our rejection of VIIA in favor of Coherent IIA also leads us to reject another well-known principle that is related to VIIA, at least under one interpretation. In particular, the term “IIA” is sometimes used in the theory of rational choice for a condition that differs from Arrow’s but also leads to impossibility theorems when applied in a certain way to voting, as explained below.

A choice function on a set $X$ is a function $\mathcal{C}$ such that for any nonempty subset $Y$ of $X$ , $\mathcal{C}(Y)$ is a nonempty subset of $Y$ . The intuitive interpretation is that in a given choice situation, it may be that not all alternatives in $X$ are available or feasible; if $Y$ is the set of feasible alternatives, called a menu or feasible set, the decision maker decides that the ultimately chosen alternative comes from $\mathcal{C}(Y)$ . If $\mathcal{C}(Y)$ is a singleton set, the decision maker has chosen the alternative in that set, whereas if $\mathcal{C}(Y)$ is not a singleton, then some further choice process or tiebreaking mechanism is applied (see Schwartz 1986, 14–15).

A choice function satisfies Sen’s (1971) condition $\alpha$ if

$$\text{for all nonempty }Z\subseteq Y\subseteq X,\text{ we have }Z\cap \mathcal{C}(Y)\subseteq \mathcal{C}(Z).$$

As a famous illustration of this condition in the context of individual choice, attributed to Sidney Morgenbesser, imagine that when offered a choice between apple pie and blueberry pie, you choose apple pie; but when offered a choice between apple, blueberry, and cherry, you switch to blueberry. This violates $\alpha$ where $Z=\{\text{apple, blueberry}\}$ , $Y=\{\text{apple, blueberry, cherry}\}$ , $\mathcal{C}(Y)=\{\mathrm{blueberry}\}$ , and $\mathcal{C}(Z)=\{\mathrm{apple}\}$ . Sen’s $\alpha$ is also known as “Chernoff’s axiom” (Chernoff 1954) and sometimes “IIA” (cf. Radner and Marschak 1954). But as Suzumura warns (1983, 66), “[C]are should be taken concerning the occasional unfortunate confusions in the literature between condition I [IIA] and Chernoff’s axiom of choice consistency, despite rather obvious contextual differences between them.” In Appendix B, we discuss the common allegation that Arrow himself was guilty of this confusion, as it relates to VIIA.

How can a choice-consistency axiom such as Sen’s $\alpha$ be applied to voting to compare it with IIA? The first question is: what does a feasible set of candidates represent? One natural interpretation is that $X(\mathbf{P})$ is the set of candidates whose names appear on the ballots in the election represented by $\mathbf{P}$ , but after the ballots are collected, a candidate might withdraw, become incapacitated, etc., leaving us with a new feasible set $Y\subset X(\mathbf{P})$ of candidates ³⁶ and the question of how to choose from $Y$ using the voters’ rankings of $X(\mathbf{P})$ . To answer this question, given an acyclic VCCR $f$ and profile $\mathbf{P}$ , there are two ways to use $f$ and $\mathbf{P}$ to define a choice function on $X(\mathbf{P})$ ³⁷ :

the global choice function ${\mathcal{G}}_f(\mathbf{P},\cdot )$ induced by $f,\mathbf{P}$ : for any nonempty $Y\subseteq X(\mathbf{P}),$

$${\mathcal{G}}_f(\mathbf{P},Y)=\{y\in Y\mid \text{ there is no }z\in Y\text{ that defeats }y\text{ in }\mathbf{P}\text{ according to }f\}.$$

the local choice function ${\mathcal{L}}_f(\mathbf{P},\cdot )$ induced by $f,\mathbf{P}$ : for any nonempty $Y\subseteq X(\mathbf{P}),$

$${\mathcal{L}}_f(\mathbf{P},Y)=\{y\in Y\mid \text{ there is no }z\in Y\text{ that defeats }y\text{ in }{\mathbf{P}}_{\mid Y}\text{ according to }f\}.$$

Intuitively, the local choice function chooses from the feasible set $Y$ by first erasing the names of candidates who have withdrawn, become incapacitated, etc., from each voter’s ballot and then applying the voting method to the restricted profile ${\mathbf{P}}_{\mid Y}$ . By contrast, while the global choice function excludes the unfeasible candidates from contention, it does not erase their names from voter’s ballots, so voters’ rankings of balloted but ultimately unfeasible candidates may still affect which of the other candidates are chosen from $Y$ .

Example 62

The distinction between the global choice function and local choice function can be illustrated by the well-known distinction between global Borda count and local Borda count. ³⁸ Let $f$ be the Borda VCCR according to which $x$ defeats $y$ in a profile $\mathbf{P}$ according to $f$ just in case the Borda score of $x$ in $\mathbf{P}$ is greater than that of $y$ . Then ${\mathcal{G}}_f(\mathbf{P},Y)$ , the elements of $Y$ chosen according to the global Borda count, are the elements of $Y$ whose Borda scores are maximal among elements of $Y$ , where Borda scores are calculated with respect to the full profile $\mathbf{P}$ . By contrast, ${\mathcal{L}}_f(\mathbf{P},Y)$ , the elements of $Y$ chosen according to the local Borda count, are the elements of $Y$ whose Borda scores are maximal among elements of $Y$ , where Borda scores are calculated with respect to the restricted profile ${\mathbf{P}}_{\mid Y}$ . For a concrete example, consider the following profiles $\mathbf{P}$ and ${\mathbf{P}}_{\mid \{x,y,a\}}$ :

Global Borda count yields ${\mathcal{G}}_f(\mathbf{P},\{x,y,a\})=\{x\}$ , as $x$ has the highest Borda score in $\mathbf{P}$ , while the local Borda count yields ${\mathcal{L}}_f(\mathbf{P},\{x,y,a\})=\{y\}$ , as $y$ has the highest Borda score in the restricted profile ${\mathbf{P}}_{\mid \{x,y,a\}}$ .

Before using the global and local choice functions to define two senses of Sen’s $\alpha$ for voting, we must note that the distinction between global and local is lost under the assumption of VIIA.

Proposition 63

Let $f$ be an acyclic VCCR. The following are equivalent:

$f$ satisfies VIIA;

for any profile $\mathbf{P}$ and $Y\subseteq X(\mathbf{P})$ , ${\mathcal{G}}_f(\mathbf{P},Y)={\mathcal{L}}_f(\mathbf{P},Y)$ .

Proof

Suppose $f$ satisfies VIIA. Consider any profile $\mathbf{P}$ and $Y\subseteq X(\mathbf{P})$ . Then the following are equivalent for any $y,z\in Y$ :

$z$ defeats $y$ in $\mathbf{P}$ according to $f$ ;

$z$ defeats $y$ in ${\mathbf{P}}_{\mid \{y,z\}}$ according to $f$ (by VIIA);

$z$ defeats $y$ in $({\mathbf{P}}_{\mid Y}{)}_{\mid \{y,z\}}$ according to $f$ (since ${\mathbf{P}}_{\mid \{y,z\}}=({\mathbf{P}}_{\mid Y}{)}_{\mid \{y,z\}}$ );

$z$ defeats $y$ in ${\mathbf{P}}_{\mid Y}$ according to $f$ (by VIIA).

Hence ${\mathcal{G}}_f(\mathbf{P},Y)={\mathcal{L}}_f(\mathbf{P},Y)$ by the definitions of ${\mathcal{G}}_f(\mathbf{P},\cdot )$ and ${\mathcal{L}}_f(\mathbf{P},\cdot )$ .

Suppose condition 2 holds. Consider profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ with $x,y\in X(\mathbf{P})\cap X({\mathbf{P}}^{\prime })$ and ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ . We must show that $x$ defeats $y$ in $\mathbf{P}$ according to $f$ if and only if $x$ defeats $y$ in ${\mathbf{P}}^{\prime }$ according to $f$ . This is equivalent to the claim that ${\mathcal{G}}_f(\mathbf{P},\{x,y\})={\mathcal{G}}_f({\mathbf{P}}^{\prime },\{x,y\})$ . We claim that the following equations hold:

$$\begin{array}{ccc}{\mathcal{G}}_f(\mathbf{P},\{x,y\})& & {\mathcal{G}}_f({\mathbf{P}}^{\prime },\{x,y\})\\ \\ \\ \Vert & & \Vert \\ \\ \\ {\mathcal{L}}_f(\mathbf{P},\{x,y\})& =& {\mathcal{L}}_f({\mathbf{P}}^{\prime },\{x,y\})\end{array}$$

The vertical equations hold by condition 2, while the horizontal equation holds since ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ . Hence ${\mathcal{G}}_f(\mathbf{P},\{x,y\})={\mathcal{G}}_f({\mathbf{P}}^{\prime },\{x,y\})$ .  □

Assuming we weaken VIIA, we can make the local–global distinction and hence distinguish two senses of Sen’s $\alpha$ in the context of voting.

Definition 64

Let $f$ be an acyclic VCCR.

$f$ satisfies Global- $\alpha$ if ${\mathcal{G}}_f(\mathbf{P},\cdot )$ satisfies $\alpha$ for all profiles $\mathbf{P}$ ;

$f$ satisfies Local- $\alpha$ if ${\mathcal{L}}_f(\mathbf{P},\cdot )$ satisfies $\alpha$ for all profiles $\mathbf{P}$ .

To illustrate this definition, let us return to the discussion of Borda count from Example 62.

Example 65

To see that the Borda VCCR $f$ satisfies Global- $\alpha$ , we must check that

$$\text{for all profiles }\mathbf{P}\text{ and nonempty }Z\subseteq Y\subseteq X(\mathbf{P}),\text{ we have }Z\cap {\mathcal{G}}_f(\mathbf{P},Y)\subseteq {\mathcal{G}}_f(\mathbf{P},Z).$$

Indeed, if $x\in Z$ and $x\in {\mathcal{G}}_f(\mathbf{P},Y)$ , so among the candidates in $Y$ , $x$ has maximal Borda score calculated with respect to the full profile $\mathbf{P}$ , then since $Z\subseteq Y$ , it follows that among the candidates in $Z$ , $x$ has a maximal Borda score calculated with respect to the full profile $\mathbf{P}$ , so $x\in {\mathcal{G}}_f(\mathbf{P},Z)$ . By contrast, the profile $\mathbf{P}$ from Example 62 shows that the Borda VCCR does not satisfy Local- $\alpha$ :

$$\begin{gathered} x,y,a\subseteq x,y,a,b,c\subseteq X(\mathbf{P}),\mathrm{but} \\ x,y,a\cap L_f(\mathbf{P},x,y,a,b,c)⊈L_f(\mathbf{P},x,y,a) \end{gathered}$$

because $x\in \{x,y,a\}\cap {\mathcal{L}}_f(\mathbf{P},\{x,y,a,b,c\})$ but $x\notin {\mathcal{L}}_f(\mathbf{P},\{x,y,a\})$ . Although $x$ has the highest Borda score calculated with respect to the full profile $\mathbf{P}$ , so ${\mathcal{L}}_f(\mathbf{P},\{x,y,a,b,c\})=\{x\}$ , $y$ has the highest Borda score calculated with respect to the restricted profile ${\mathbf{P}}_{\mid \{x,y,a\}}$ , so ${\mathcal{L}}_f(\mathbf{P},\{x,y,a\})=\{y\}$ .

It is no accident that the Borda VCCR satisfies Global- $\alpha$ but not Local- $\alpha$ . It is well known that Global- $\alpha$ imposes no constraint on an acyclic VCCR.

Proposition 66

If $f$ is an acyclic VCCR, then $f$ satisfies Global- $\alpha$ .

Proof

The claim that $f$ satisfies Global- $\alpha$ is the claim that for any profile $\mathbf{P}$ and nonempty $Z\subseteq Y\subseteq X(\mathbf{P})$ , we have $Z\cap {\mathcal{G}}_f(\mathbf{P},Y)\subseteq {\mathcal{G}}_f(\mathbf{P},Z)$ . Indeed, if $y\in Z\cap {\mathcal{G}}_f(\mathbf{P},Y)$ , so by definition there is no $z\in Y$ that defeats $y$ in $\mathbf{P}$ according to $f$ , then since $Z\subseteq Y$ , there is no $z\in Z$ that defeats $y$ in $\mathbf{P}$ according to $f$ , which by definition implies $y\in {\mathcal{G}}_f(\mathbf{P},Z)$ .  □

Let us now consider Local- $\alpha$ as a constraint on VCCRs. First, we note that it is a weakening of VIIA.

Proposition 67

$$

If $f$ is an acyclic VCCR satisfying VIIA, then $f$ satisfies Local- $\alpha$ .

There are acyclic VCCRs satisfying Local- $\alpha$ but not FIIA and hence not VIIA.

Proof

For part 1, assuming that $f$ satisfies VIIA, we show that for any profile $\mathbf{P}$ and nonempty $Z\subseteq Y\subseteq X(\mathbf{P})$ , we have $Z\cap {\mathcal{L}}_f(\mathbf{P},Y)\subseteq {\mathcal{L}}_f(\mathbf{P},Z)$ . Suppose $y\in Z$ but $y\notin {\mathcal{L}}_f(\mathbf{P},Z)$ , so there is an $x\in Z$ that defeats $y$ in ${\mathbf{P}}_{\mid Z}$ according to $f$ . Then since $({\mathbf{P}}_{\mid Z}{)}_{\mid \{x,y\}}=({\mathbf{P}}_{\mid Y}{)}_{\mid \{x,y\}}$ , it follows by VIIA that $x$ defeats $y$ in ${\mathbf{P}}_{\mid Y}$ according to $f$ , which with $x\in Z\subseteq Y$ implies $y\notin {\mathcal{L}}_f(\mathbf{P},Y)$ .

For part 2, let $f$ be a VCCR such that $x$ defeats $y$ in $\mathbf{P}$ according to $f$ if and only if (i) $x$ is unanimously preferred to $y$ and (ii) there is a $z\in X(\mathbf{P})\setminus \{x,y\}$ such that $x\to z$ but $y\nrightarrow z$ . Then $f$ is acyclic in virtue of (i). To see that $f$ violates FIIA, consider two profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ with $X(\mathbf{P})=X({\mathbf{P}}^{\prime })=\{x,y,z\}$ and $V(\mathbf{P})=V({\mathbf{P}}^{\prime })$ such that all $i\in V(\mathbf{P})$ have $x{\mathbf{P}}_{i}z{\mathbf{P}}_{i}y$ while all $i\in V({\mathbf{P}}^{\prime })$ have $x{\mathbf{P}}_i^{\prime }y{\mathbf{P}}_i^{\prime }z$ . Then ${\mathbf{P}}_{\mid \{x,y\}}={\mathbf{P}}_{\mid \{x,y\}}^{\prime }$ , and $x$ defeats $y$ in $\mathbf{P}$ but not in ${\mathbf{P}}^{\prime }$ , violating FIIA. To see that $f$ satisfies Local- $\alpha$ , we must show that for any profile $\mathbf{P}$ and nonempty $Z\subseteq Y\subseteq X(\mathbf{P})$ , we have $Z\cap {\mathcal{L}}_f(\mathbf{P},Y)\subseteq {\mathcal{L}}_f(\mathbf{P},Z)$ . Suppose $y\in Z$ but $y\notin {\mathcal{L}}_f(\mathbf{P},Z)$ , so there is an $x\in Z$ that defeats $y$ in ${\mathbf{P}}_{\mid Z}$ according to $f$ . Hence $x$ is unanimously preferred to $y$ in ${\mathbf{P}}_{\mid Z}$ and there is a $z\in Z$ such that $x\to z$ but $y\nrightarrow z$ . Then since $Z\subseteq Y$ , we have that $x\in Y$ , that $x$ is unanimously preferred to $y$ in ${\mathbf{P}}_{\mid Y}$ according to $f$ , and that there is a $z\in Y$ such that $x\to z$ but $y\nrightarrow z$ . Therefore, $x$ defeats $y$ in ${\mathbf{P}}_{\mid Y}$ according to $f$ , which with $x\in Y$ implies $y\notin {\mathcal{L}}_f(\mathbf{P},Y)$ .  □

Although weaker than VIIA, Local- $\alpha$ is still a significant restriction on an acyclic VCCR, as it rules out that the VCCR coincides with majority rule on two-candidates profiles.

Definition 68

A VCCR $f$ satisfies Binary Majoritarianism if for any profile $\mathbf{P}$ with $X(\mathbf{P})=\{x,y\}$ , $x$ defeats $y$ in $\mathbf{P}$ according to $f$ if and only if $x$ is majority preferred to $y$ in $\mathbf{P}$ .

We have the following easy impossibility result.

Proposition 69

There is no VCCR satisfying Local- $\alpha$ , Availability, and Binary Majoritarianism.

Proof

Consider a profile $\mathbf{P}$ with $X(\mathbf{P})=\{x,y,z\}$ and a majority cycle $x\to y\to z\to x$ . By Availability, there is some $a\in \{x,y,z\}$ who is undefeated in $\mathbf{P}$ according to $f$ . Since there is a majority cycle, there is some $b\in \{x,y,z\}$ such that $b\to a$ . Hence by Binary Majoritarianism, $b$ defeats $a$ in ${\mathbf{P}}_{\mid \{a,b\}}$ according to $f$ . Thus, we have $a\in \{a,b\}\cap {\mathcal{L}}_f(\mathbf{P},\{x,y,z\})$ but $a\notin {\mathcal{L}}_f({\mathbf{P}}_{\mid \{a,b\}},\{a,b\})$ , so $f$ violates Local- $\alpha$ . □

Combining Propositions 67.1 and 69, we have the analog of Proposition 69 under VIIA.

Corollary 70

There is no VCCR satisfying VIIA, Availability, and Binary Majoritarianism.

Finally, let us come full circle and return to voting methods in the sense of Definition 6, as opposed to VCCRs. What are the implications of the impossibility result above for voting methods? To answer this question, we first adapt the definition of $\alpha$ to voting methods.

Definition 71

A voting method $F$ satisfies $\overline{\alpha }$ if for all profiles $\mathbf{P}$ and nonempty $Z\subseteq X(\mathbf{P})$ , $Z\cap F(\mathbf{P})\subseteq F({\mathbf{P}}_{\mid Z})$ . ³⁹

Simply put, $\overline{\alpha }$ states that if $x$ is a winner in an election represented by $\mathbf{P}$ , then $x$ would also have been a winner had some other candidates not participated in the election at all, while the remaining candidates—those in $Z$ —were ranked in the same way, as represented by ${\mathbf{P}}_{\mid Z}$ . Although a candidate’s never appearing on the ballot in the first place is conceptually different than their appearing on the ballot but then withdrawing or being incapacitated after the ballots are collected—as in our interpretation of the choice functional setting above—nonetheless, there is a formal connection: the satisfaction of $\overline{\alpha }$ by a voting method is equivalent to the satisfaction of Local- $\alpha$ by any VCCR that defeat rationalizes the voting method.

Lemma 72

If $F$ is a voting method that is defeat rationalized by a VCCR $f$ , then $F$ satisfies $\overline{\alpha }$ if and only if $f$ satisfies Local- $\alpha$ .

Proof

Since $F$ is defeat rationalized by $f$ , $F(\mathbf{P})$ is the set of undefeated candidates in $\mathbf{P}$ according to $f$ , which is also equal to ${\mathcal{L}}_f(\mathbf{P},X(\mathbf{P}))$ . Thus, for all nonempty $Z\subseteq Y\subseteq X(\mathbf{P})$ , we have

$$\begin{array}{rl}Z\cap F({\mathbf{P}}_{\mid Y})& \subseteq F({\mathbf{P}}_{\mid Z})\\ ⟺Z\cap {\mathcal{L}}_f(\mathbf{P},Y)& \subseteq {\mathcal{L}}_f(\mathbf{P},Z).\end{array}$$

Hence $F$ satisfies $\overline{\alpha }$ (in the equivalent form given in Endnote 39) if and only if $f$ satisfies Local- $\alpha$ .  □

We can now answer our question about voting methods with the following impossibility result, whose proof is easily obtained by adapting that of Proposition 69.

Proposition 73

There is no voting method satisfying $\overline{\alpha }$ and Binary Majoritarianism.

As a voting method (respectively, VCCR) Split Cycle satisfies Binary Majoritarianism but not $\overline{\alpha }$ (respectively, Local- $\alpha$ ). The mistake of insisting on $\overline{\alpha }$ for voting is essentially the same as the mistake of insisting on IIA, which can be seen by reformulating $\overline{\alpha }$ as follows: for all nonempty $Z\subseteq X(\mathbf{P})$ , if $x\in Z$ but $x\notin F({\mathbf{P}}_{\mid Z})$ , then $x\notin F(\mathbf{P})$ . In terms of a defeat rationalization of $F$ , this means that if $x$ is defeated in the smaller profile ${\mathbf{P}}_{\mid Z}$ then $x$ must also be defeated in the larger profile $\mathbf{P}$ . But this should not follow if the larger profile $\mathbf{P}$ is more incoherent than ${\mathbf{P}}_{\mid Z}$ . If $\mathbf{P}$ is sufficiently incoherent, we may need to suspend judgment on many defeat relations that we could coherently accept in ${\mathbf{P}}_{\mid Z}$ .

Example 74

The same example used against IIA in Example 36 can be adapted to argue against Local- $\alpha$ for VCCRs or $\overline{\alpha }$ for voting methods. Consider the following profiles $\mathbf{P}$ and ${\mathbf{P}}^{\prime }$ :

In the context of the perfectly coherent profile $\mathbf{P}$ , the margin of $n$ for $a$ over $b$ should be sufficient for $a$ to defeat $b$ , so $a$ should be the uniquely chosen winner. But in the context of the incoherent profile ${\mathbf{P}}^{\prime }$ , it is not sufficient: no one can be judged to defeat anyone else—this follows from Anonymity, Neutrality, and Availability—so all three must be included in the choice set to which a further tiebreaking process is applied. This is a counter example to Local- $\alpha$ and $\overline{\alpha }$ : $b$ is undefeated in ${\mathbf{P}}^{\prime }$ but not in ${\mathbf{P}}_{\mid \{a,b\}}^{\prime }=\mathbf{P}$ .

Our conclusion concerning $\alpha$ applied to voting is in the spirit of Sen’s (1993) view that “Violations of property $\alpha$ …can be related to various different types of reasons—easily understandable when the external context is spelled out” (p. 501). Sen (1993, 500–502) focuses on rationalizing violations of $\alpha$ in individual choice by reference to features of the context of choice. Here we have focused on rationalizing violations in voting by reference to features of the context given by the profile—namely, an increase in incoherence from one profile to another. To overlook this context would be to commit The Fallacy of IIA from Section 4.3.

7. Conclusion

The pessimistic conclusions about democracy that some have drawn from the Paradox of Voting and Arrow’s Impossibility Theorem are not justified. Like most voting theorists, we are more optimistic. In particular, we believe that many majority cycles can be resolved in a rational way, while respecting the principle of Majority Defeat, as shown by Split Cycle. Of course there remain some cycles, such as a perfect cycle $a\to b\to c\to a$ in which each candidate is majority preferred to the next by exactly the same margin (and there are no other candidates), which must lead to a tie between all candidates. But to think that democracy is devastated by the possibility of such ties seems almost as unreasonable as thinking that democracy is devastated by the possibility that in an election with only two candidates and an even number of voters, it could happen that half of the voters vote for $x$ over $y$ while half vote for $y$ over $x$ . The fact that the set of winners cannot always be a singleton—that some further tiebreaking mechanism must be in place—hardly warrants very pessimistic conclusions, especially if the probability of having many tied candidates is sufficiently low, as we expect when there are many voters compared to candidates (see Holliday and Pacuit 2020).

Far from justifying pessimism about democracy, social choice theory leads the way to voting procedures that can improve democratic decision making. We agree with Maskin and Sen (2017a, 2017b) that a major improvement would come in replacing Plurality voting with a voting procedure using ranked ballots that elects a Condorcet winner whenever there is one. In this paper, we have arrived at a unique collective choice rule, Split Cycle, via six axioms concerning when one candidate should defeat another in a democratic election—with the key axiom being the axiom of Coherent IIA that weakens Arrow’s IIA and explains why the latter is too strong. As theorists, we sleep well at night knowing that we have a solid theoretical justification for handling majority cycles in a certain way should they arise. As citizens and committee members, we hope that in practice our elections will have Condorcet winners and that we will elect them.