On avoiding vote swapping

Abstract

In this paper we analyse the problem of vote swapping in representative democracies. Vote swapping consists of exchanging votes between two voters from two different jurisdictions in order to beat a candidate that both voters dislike. The recent debates and legal disputes about this manipulation device raise some important ethical issues. We adopt an axiomatic approach, first establishing the relationship between vote swapping and a restricted form of gerrymandering, which is another way of manipulating elections in representative democracies. We then look for voting rules that are immune to such manipulations and show that any such voting rules only exist if either the voters or the candidates are given unreasonable power.

1 Introduction

This paper explores whether voting rules can be immune to vote swapping, a recently introduced manipulation device in elections taking place in representative democracies. In these elections, voters are partitioned into jurisdictions (or ridings) in which they cast their votes for candidates running in these jurisdictions. Jurisdictional winners are then aggregated in such a way as to elect a federal winner who is the overall winner of the election. Countries resorting to such procedures are called representative democracies; the United States, Canada, India, the United-Kingdom, Australia are prominent examples of representative democracies.

Vote swapping is an informal agreement where two voters from different jurisdictions and parties trade votes in order to obtain the election of representatives from their party while at the same time blocking the election of an unwanted third party. In representative democracies, the outcome of the election has been observed to be manipulable by vote swapping. Consider a very simple example in which the country is divided into three jurisdictions, $J_1, J_2$ and $J_3$, each formed of ten voters who can choose from three candidates, a, b or c. The votes are listed below.

$$\begin{aligned} \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} &{} J_1 &{} J_2 &{} J_3\\ a&{} 4 &{} 3 &{} 3 \\ b&{} 0 &{} 3 &{} 3 \\ c&{} 6 &{} 4 &{} 4 \end{array} \end{aligned}$$

If plurality rule¹ was applied in this country, candidate c would be elected in the three jurisdictions, while at the federal level, c having three votes against 0 for both a and b, candidate c would be elected.

Now, imagine that candidates a and b are similar ideologically and that their electors all rank c as their least desirable candidate. One way of changing the outcome of the election would be for candidate b voters in jurisdictions $J_2$ and $J_3$ to decide to vote for a instead. As a consequence, the new votes would be

$$\begin{aligned} \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} &{} J_1 &{} J_2 &{} J_3\\ a&{} 4 &{} 6 &{} 6 \\ b&{} 0 &{} 0 &{} 0 \\ c&{} 6 &{} 4 &{} 4 \end{array} \end{aligned}$$

Candidate a would now be elected in two jurisdictions out of three and would therefore be the federal winner in this country.

However, those voters who originally intended to vote for b might be left feeling cheated of expressing their true opinion and not fully represented by this outcome. This is where vote swapping makes decisions easier for voters. If voters can swap their votes, then some b voters in jurisdictions $J_2$ and $J_3$ could vote for a instead, while at the same time some a voters in jurisdiction $J_1$ would vote for b. If that happened, then the new votes would be

$$\begin{aligned} \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} &{} J_1 &{} J_2 &{} J_3\\ a&{} 0 &{} 5 &{} 5 \\ b&{} 4 &{} 1 &{} 1 \\ c&{} 6 &{} 4 &{} 4 \end{array} \end{aligned}$$

and candidate a would win. What vote swapping achieves is changing the election outcome without changing the voting situation, i.e. the number of votes for a, b or c. Because voters may prefer to swap rather than give up voting for their preferred candidate, manipulation by vote swapping has attracted attention.

Platforms enabling electors to swap votes are offered by many websites, such as http://votepair.org for the US (now hosted by http://oxhouse.org) or votepair.ca for Canada.² For instance, the website “Pair Vote Swap”³ in Canada introduces the concept of vote swapping to their readers by saying: “With over 25 % of ridings too close to call, and two parties running neck-and-neck in the polls, sending your preferred vote to another riding may matter more than ever. Use vote swapping when your vote won’t count locally to make a difference”. More recently, in the 2015 UK general election, the website VoteSwap⁴ claimed to have arranged 21,410 swaps between Green and Labour supporters to keep the Tories out.

Both on the legal side and from the social choice perspective, there are pros and cons to vote swapping. Because vote swapping has attracted attention, the US court of appeal has been asked to give a ruling: the court concluded that “vote swapping mechanisms as well as the communication and vote swaps that web sites enabled were constitutionally protected”.⁵ In Canada, the electoral watchdog Elections Canada, has declared that promoting vote swapping does not violate the Canada Elections Act.⁶ The basis for these judgments was that “encouraging electors to vote in a particular way is permissible under the Act, as is inviting electors to participate in organized strategic voting plans”.

However, the courts that pronounced the mechanisms legal were not judging the constitutionality of vote swapping itself. The main concern is that discussions about votes can turn into negotiations on votes, and the brokering of votes is usually prohibited, as it might lead to monetary transactions that would change vote swapping into vote selling.

Abstracting from the legal disputes, vote swapping also raises some ethical issues. As stated by the website “Pair Vote Swap”, the “overall priority is to counteract the distorted results of the current voting system”. The distortion alluded to refers to the fact that the indirect voting procedure of representative democracies sometimes fails to elect the candidate receiving the majority of votes. This is known as the referendum paradox. However, one can argue that this kind of distortion is a voluntary feature of representative democracies, which deliberately aims at giving different weights to different categories of individuals. Counteracting this specific distortion can then be seen as a way of circumventing the indirect, two-step voting procedure, in order to implement the outcome of a direct election.

Advocates of vote swapping also argue that it increases social welfare, because more voters will be satisfied with the outcome. Although our example in this introduction illustrates this fact, two points can be raised. First, candidate c receives 14 votes while candidate a only receives 10, and c wins in all three jurisdictions against a. There would be some justification, therefore, for considering candidate c as the “natural” winner of this election. If candidates a and b are so close ideologically that their supporters are considered as a majority (their votes sum up to 16), then in order to maximize the number of satisfied voters, b voters could change their vote to a, who would then win the election. If these voters are ready to do that, they do not need to resort to vote swapping to reach their preferred outcome. On the other hand, if they are not willing to do that, then c can arguably be considered as a winner representative of the will of the people.

Second, vote swapping can produce the reverse effect and reduce the number of voters that are satisfied with the outcome: in the above example, if candidate c had received 10 votes in jurisdiction $J_1$ instead of 6, then a majority of voters would have been happy with the outcome of the election without vote swapping, and would have ended up less happy with vote swapping.

As can be seen, there are no trivial arguments for or against vote swapping. In this paper we take an agnostic position on this issue and, leaving aside the legal issues,we simply ask the following question: is it possible to design electoral rules which are immune to vote swaps?

In Sect. 2 we present the setting. In particular, we consider that the boundaries of the jurisdictions are fixed, and that voters do not move. Hence the size of every jurisdiction is given, though jurisdictions may differ in size. The voting procedure involves two steps. First, votes are collected and aggregated within each jurisdiction, and local winners are designated by a local voting rule (voting rules may differ between jurisdictions). Next, all the local winners are aggregated by another voting rule, so as to elect the federal winner. We allow voters to swap their votes and we look for voting rules that are immune to manipulation by vote swapping.

In the rest of Sect. 2, we show that vote swapping is almost equivalent to another type of manipulation known under the name of gerrymandering, provided that the size of jurisdictions remains fixed. Gerrymandering is a term that describes the deliberate rearrangement of the boundaries of electoral districts in order to influence the outcome of elections. The original gerrymander was created in 1812 by Massachusetts governor Elbridge Gerry, who crafted a district for political purposes that looked like a sala-mander. The purpose of gerrymandering is to concentrate opposition votes into a few districts to gain more seats for the majority in surrounding districts (called packing), or to diffuse minority strength across many districts (called dilution). Because vote swapping is equivalent to gerrymandering with fixed size jurisdictions under a mild anonymity condition, our results for the former also apply to the latter.

In Sect. 3 we present our main result. We show that the set of voting rules that are swap-proof has very undesirable properties: either voters have a pivotal power against unanimity (i.e. whenever everyone votes for the same candidate except for one voter, this one voter can decide the outcome of the election), or the voting rules are such that a candidate can be elected despite having received no votes. If we require the voting rules not to confer a pivotal power on voters (axiom NoPiv) or only to select winners from the subset of candidates who received at least one vote (axiom MinRep—for Minimal Representativity), then we are left with no option but to accept that vote swapping can alter the result of the election. We also show through examples that these axioms are independent. This result is an impossibility theorem according to which indirect elections can neither be swap-proof nor gerrymander-proof when the size of jurisdictions is fixed.

Related literature

To the best of our knowledge, our contribution is the first to analyse the issue of vote swapping with some axiomatic foundation. The only other papers on vote swapping are by Hartvigsen (2006) and by Bervoets et al. (2015). In his paper, Hartvigsen analyses how websites can best implement vote swapping. He also shows that finding the best vote swapping strategy is NP-hard. In the specific case of equal size jurisdictions, Bervoets et al. prove that with two allied parties sharing a common opponent, the problem becomes polynomially solvable while it remains NP-hard for three allied parties or more.

Motivated by the analysis of the Ostrogorski paradox,⁷ Nermuth (1992) showed that the aggregation in two stages could lead to degenerate rules once mild conditions are imposed on the aggregator. Other papers (Bervoets and Merlin 2012; Chambers 2008; Perote Peña 2006) have analysed this problem in the gerrymandering context, using different settings but reaching the same conclusion: voting rules that survive gerrymander-proofness have undesirable properties. However, in each of these papers the authors allow the size of jurisdictions to fluctuate when the gerrymandering takes place. This constitutes a major limitation to these papers, because in real-life elections the size of jurisdictions cannot be arbitrarily changed. In this paper, we show the logical equivalence between the problem of vote swapping and that of gerrymandering with fixed jurisdiction size. Thus, our findings on vote swapping can be applied to gerrymandering with fixed jurisdiction size.

Aware of the criticism about fluctuating sizes, Puppe and Tasnádi (2009, 2015) address the issue of gerrymandering (named redistricting) with jurisdictions of equal size. Equal size is a special but important case of fixed size jurisdictions. In their first contribution, the authors show that the problem of finding a winning partition of electors is an NP-complete problem once this size constraint is introduced. In their second contribution, the authors introduce some geographical constraints to the districting problem, and investigate the normative properties of different rules. They show that any solution to the districting problem (defined as finding a partition of the voters that maximises a given objective function) must treat the candidates unequally. Our contribution differs from theirs because we investigate whether there are voting rules that are immune to gerrymandering with fixed size jurisdictions (through the analysis of vote swapping). Although it might be tempting to see fluctuating jurisdiction sizes as the explanation for the failure to identify gerrymander-proof voting rules, our findings here confirm these negative results even when jurisdiction sizes are fixed.

2 The general framework

2.1 Notations and definitions

Let $A= \{a,b,c, \ldots \}$ be a finite and fixed set of candidates and $N = \{1,\ldots , n\}$ the fixed set of voters, with $n \ge 3$. The country is divided into jurisdictions, the set of which is denoted by $J = \{J_1,\ldots , J_m\}$ with $m\ge 2$. The set of voters is partitioned into the m jurisdictions by a function $\sigma$ defined from N to $\{1, \ldots , m\}$ as $\sigma (i) = j \Leftrightarrow i \in J_j$.

We restrict our attention to the set $\Sigma$ of partitions such that $\bigcup _{j = 1, m}J_j = N$, $J_j \cap J_k = \emptyset$ when $j \ne k$ and $\sigma ^{-1}(j) \not = \emptyset$ for all j. If $\sigma \in \Sigma$ then no jurisdiction is empty and because $n > m$, there is at least one jurisdiction with strictly more than one voter. Throughout the paper we refer to a specific subset of $\Sigma$ for which the number of voters assigned to a jurisdiction $J_j$ is exogenously fixed to some positive number $n_j$. We denote this subset as $\Sigma ^{\mathbf{n}}$ where $\mathbf{n} = (n_1,\ldots , n_m)$ and $n = \sum _k n_k$.

Voters vote for one candidate in their jurisdiction and these votes are taken as given. $\pi \in A^n$ is a vote profile where $\pi |_i$ denotes voter i’s vote. For any subset S of N, we denote by $\pi |_S$ the restriction of $\pi$ to S. Votes are aggregated in two steps. First, there is a winner in every jurisdiction. This winner in $J_j$ is chosen through a social choice function $\phi _j$ : $\Sigma \times A^n \rightarrow A$ and we assume that jurisdictional winners are chosen only by the voters of that jurisdiction, i.e. $\phi _j(\sigma ,\pi ) = \phi _j(\sigma ,\pi ')$ when $\pi |_{J_j} = \pi '|_{J_j}$. The set of all social choice functions satisfying this mild condition is denoted by $\Phi$.

The m jurisdictional winners constitute a federal profile $\Pi \in A^m$. The federal winner is chosen through a social choice function⁸ $\Gamma$ : $A^m \rightarrow A$. For ease of exposition we denote the federal winner as $\Gamma \circ \phi (\sigma , \pi )$ where $\Gamma \circ \phi (\sigma , \pi )\equiv \Gamma ( \phi _1(\sigma ,\pi ), \ldots , \phi _m(\sigma ,\pi ))$. A representative democracy is given by $RD = (\Gamma , \phi _1, \ldots , \phi _m)$ with $\phi _j \in \Phi$ for all j.

Consider the example from the Introduction:

$$\begin{aligned} \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} &{} J_1 &{} J_2 &{} J_3\\ a&{} 4 &{} 3 &{} 3 \\ b&{} 0 &{} 3 &{} 3 \\ c&{} 6 &{} 4 &{} 4 \end{array} \end{aligned}$$

We have $A = \{a, b, c\}$, $N = \{1,\ldots , 30\}$, $J = \{J_1, J_2, J_3\}$, and $\sigma (1) = \cdots = \sigma (10) = 1$, $\sigma (11) = \cdots = \sigma (20) = 2$ and $\sigma (21) = \cdots = \sigma (30) = 3$. The vote profile is $\pi = aaaaccccccaaabbbccccaaabbbcccc$, $\phi _j$ is the plurality rule for every j, so that $\phi _1(\sigma , \pi ) = \phi _2(\sigma , \pi ) = \phi _3(\sigma , \pi ) = c$, and the federal profile is $\Pi = ccc$. The federal voting rule $\Gamma$ is the plurality rule, so that $\Gamma (\Pi ) = c$. Therefore, $\Gamma \circ \phi (\sigma , \pi ) = c$.

Remark 1

We assume that voters vote for only one candidate. However, our results extend to the case of preference aggregation. To see this, simply consider that there are p! possible rankings of p candidates, and assume that the voters choose one ranking out of the p! possible rankings instead of choosing one candidate out of p possible candidates.

2.2 Vote swapping and gerrymandering

In this section we explore the logical relations between the issue of vote swapping and that of gerrymandering. Bervoets and Merlin (2012) defined gerrymander-proofness as a very strong property: no group of voters (including single individuals) can change the outcome of an election by moving from one jurisdiction to another if they do not change their vote profile at the same time.

Gerrymander-proofness (G-P):

$$\begin{aligned} \text {For all } \pi \in A^n, \; \Gamma \circ \phi (\sigma , \pi )= \Gamma \circ \phi (\sigma ^{\prime }, \pi ) \quad \text {for all } \sigma , \, \sigma ^{\prime } \in \Sigma \end{aligned}$$

This condition implies that the result of an election should be the same whatever the partition of the voters. In particular, jurisdiction size can vary from one voter to almost all voters. These options allow for great flexibility in the design of partitions and this in large part explains the results obtained in Bervoets and Merlin (2012). Consider the following example with three jurisdictions and three candidates $\{a, b, c\}$, where voters of candidates b prefer candidate a to candidate c:

$$\begin{aligned} \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} &{} J_1 &{} J_2 &{} J_3\\ a&{} 4 &{} 4 &{} 4 \\ b&{} 2 &{} 2 &{} 2 \\ c&{} 10 &{} 10 &{} 10 \end{array} \end{aligned}$$

With this partition of voters, candidate c is elected in the three jurisdictions under plurality rule. Allowing for gerrymandering, voter partition can be changed so as to obtain the following:

$$\begin{aligned} \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} &{} J_1 &{} J_2 &{} J_3\\ a&{} 0 &{} 6 &{} 6 \\ b&{} 0 &{} 3 &{} 3 \\ c&{} 30 &{} 0 &{} 0 \end{array} \end{aligned}$$

Now candidate c wins in $J_1$, but a wins in $J_2$ and in $J_3$, and so he is the overall winner. However, this example illustrates how varying the size of every jurisdiction might be an unrealistic assumption. If the size of jurisdictions were to remain fixed, then in this example no gerrymandering would reverse the result. This is because candidate c receives too large a share of votes to lose the election. In this sense, we wish to weaken our condition by restricting gerrymandering to partitions of fixed size, the equal size case being a particular case.

Let $\sigma \in \Sigma ^{\mathbf{n}}$ be a partition. Then we define $\sigma _{ij}$ as the partition of voters such that $\sigma _{ij}(j) = \sigma (i)$ and $\sigma _{ij}(i) = \sigma (j)$ while $\sigma _{ij}(k) = \sigma (k)$ otherwise. Note that $\sigma _{ij} \in \Sigma ^{\mathbf{n}}$.

Gerrymander-proofness with fixed jurisdiction size (Fixed G-P):

$$\begin{aligned} \text {For all } \pi \in A^n, \; \Gamma \circ \phi (\sigma ,\pi )= \Gamma \circ \phi ( \sigma ^\prime ,\pi ) \quad \text {for all } \sigma , \, \sigma ^\prime \in \Sigma ^{\mathbf{n}} \end{aligned}$$

Of course, a voting rule satisfying G-P also satisfies Fixed G-P but the reverse is not true.

Now consider that gerrymandering is forbidden and voters stay in their home jurisdiction, but engage in vote swapping. When voters i and j exchange their votes, then the vote profile is changed from $\pi$ to $\pi _{ij}$, where $\pi _{ij}|_i = \pi |_j$, $\pi _{ij}|_j = \pi |_i$ and $\pi _{ij}|_{N {\setminus } \{i,j\}} = \pi |_{N{\setminus } \{i,j\}}$. We are now ready to state our definition of swap-proofness.

Swap-proofness (SwPr):

$$\begin{aligned} \text {For all } \pi \in A^n, \text {all } \sigma \in \Sigma , \Gamma \circ \phi (\sigma ,\pi )= \Gamma \circ \phi (\sigma ,\pi _{ij}) \quad \text { for all } i,j \in N \end{aligned}$$

Note that we impose SwPr on pairs of individuals only, although it could take more than two individuals engaging in vote swapping to reverse the outcome of an election. However, any pattern of vote swapping, no matter how complicated it might be, can be written as a sequence of swaps between pairs. The axiom SwPr holds for every pair, thus for any sequence of pairs.

Consider again the example from the Introduction

$$\begin{aligned} \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} &{} J_1 &{} J_2 &{} J_3\\ a&{} 4 &{} 3 &{} 3 \\ b&{} 0 &{} 3 &{} 3 \\ c&{} 6 &{} 4 &{} 4 \end{array} \end{aligned}$$

Clearly, there is a sequence of swaps between pairs of individuals that leads to the following situation:

$$\begin{aligned} \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} &{} J_1 &{} J_2 &{} J_3\\ a&{} 0 &{} 5 &{} 5 \\ b&{} 4 &{} 1 &{} 1 \\ c&{} 6 &{} 4 &{} 4 \end{array} \end{aligned}$$

This example illustrates the fact that the plurality rule, applied both at jurisdictional level and at federal level, does not guarantee swap-proof representative democracies.

Before describing the relations between gerrymandering and vote swapping, we need one last standard axiom of anonymity. In the setting of representative democracies, anonymity can be required either in jurisdictions, at federal level or both. However, we only need anonymity to hold at local level:

Let $n_j(\sigma ,\pi , a)$ be the number of voters who cast a vote in favour of candidate a in $J_j$, under partition $\sigma$ when the vote profile is $\pi$, and let $n_j (\sigma , \pi )= (n_j(\sigma ,\pi , a), n_j(\sigma ,\pi , b),\ldots )$.

Local Anonymity (LA): A representative democracy RD is said to be locally anonymous if, for every $j \in \{1, \ldots , m\}$,

$$\begin{aligned} n_j(\sigma , \pi ) = n_j (\sigma ',\pi ') \Longrightarrow \phi _j(\sigma ,\pi ) = \phi _j(\sigma ',\pi ') \end{aligned}$$

Proposition 1

Axioms Fixed G-P and SwPr are equivalent if and only if the representative democracy RD is locally anonymous.

Proof

First, we show through two examples that Local Anonymity is a necessary condition for the proposition to hold. Assume RD does not satisfy LA.

Example 1

Let $A = \{a,b \}$ and assume $\Gamma$ is such that $\Gamma (\Pi ) = \Pi _{|J_1}$, i.e. $J_1$ dictates his choice at federal level. Now consider that in any jurisdiction $J_j$, $\phi _j(\sigma ,\pi ) = a$ whenever $\sigma (1) = j$ while $\phi _j(\sigma ,\pi ) = b$ whenever $\sigma (1) \ne j$, i.e. jurisdiction $J_j$ elects a whenever voter 1 belongs to $J_j$ and b otherwise. Obviously, for $\sigma$ such that $\sigma (1) = 1$ and $\sigma '$ such that $\sigma '(1) \ne 1$, we have $\Gamma \circ \phi (\sigma ,\pi )= \Gamma \circ \phi (\sigma ,\pi _{ij}) \text { for all } i,j \in N$ but $\Gamma \circ \phi (\sigma ,\pi )\ne \Gamma \circ \phi (\sigma ^{\prime },\pi )$. Hence SwPr is satisfied while G-P is violated (as well as Fixed G-P).

Example 2

Let $A = \{a,b\}$ and define the priority rule for a as a voting rule electing candidate a when a receives at least one vote (b is only elected if he gets all the votes). Define the Constant rule for b as the voting rule electing b regardless of the vote profile, and finally, define the local dictatorship of voter i in jurisdiction $J_j$ as the voting rule such that $\phi _j(\sigma ,\pi ) = \pi _{|i}$. Assume $\Gamma$ is a priority rule for a, while every $\phi _j$ is the constant rule for b if voter 1 is not in $J_j$. If voter 1 is in $J_j$, then $\phi _j$ is a local dictatorship of voter 1 in jurisdiction $J_j$.

Fixed G-P is satisfied: If voter 1 votes for a, a will be the federal winner, whatever the partition of voters. If voter 1 votes for b then b will be the federal winner, whatever the partition of voters. However, SwPr is violated: consider the vote profile $\pi = a, b, \ldots , b$ where everyone votes for b except voter 1. Then the federal winner is a. Now swap the votes of voter 1 and any other voter, the federal winner is b.

Second, we show that Local Anonymity is a sufficient condition.

First part Assume that RD satisfies SwPr and LA, but violates Fixed G-P. Then, there are two partitions $\sigma , \sigma ' \in \Sigma ^{\mathbf{n}}$ such that $\Gamma \circ \phi (\sigma ,\pi ) \not = \Gamma \circ \phi (\sigma ',\pi )$. By standard arguments, it is easy to see that any partition $\sigma ' \in \Sigma ^{\mathbf{n}}$ can be reached from any other partition $\sigma \in \Sigma ^{\mathbf{n}}$ by a sequence of partitions $\sigma = \sigma _0, \sigma _1,\ldots , \sigma _p,\ldots , \sigma _m = \sigma '$ such that only two voters are exchanged between $\sigma _p$ and $\sigma _{p+1}$. Therefore, along this sequence, there is a step p when $\Gamma \circ \phi (\sigma _p,\pi ) \not = \Gamma \circ \phi (\sigma _{p+1},\pi )$, with $\sigma _p(k) = \sigma _{p+1}(k) \; \forall k \not = i,j$, $\sigma _p(i) = \sigma _{p+1}(j)$, $\sigma _p(j) = \sigma _{p+1}(i)$. Consider now a swap between voters i and j leading to $\pi _{ij}$. By SwPr, $\Gamma \circ \phi (\sigma _{p+1},\pi ) = \Gamma \circ \phi (\sigma _{p+1},\pi _{ij})$. As $n_k(\sigma _{p+1},\pi _{ij}, a) = n_k(\sigma _p,\pi , a)\, \forall a \in A$ and $\forall k \in \{1, \ldots , m\}$, LA implies $\Gamma \circ \phi (\sigma _{p+1},\pi _{ij}) = \Gamma \circ \phi (\sigma _p,\pi )$, a contradiction.

Second part Assume that RD satisfies Fixed G-P and LA, but violates SwPr. Thus, there is a profile $\pi _{ij}$ and a partition $\sigma$ such that $\Gamma \circ \phi (\sigma ,\pi ) \ne \Gamma \circ \phi (\sigma ,\pi _{ij})$. Assume that $\sigma (i) = \sigma (j) = p$. Then $n_p(\sigma , \pi , a ) = n_p(\sigma ,\pi _{ij}, a) \; \forall a$ and by LA, $\Gamma \circ \phi (\sigma ,\pi ) = \Gamma \circ \phi (\sigma ,\pi _{ij})$, a contradiction. Thus if there is a profile $\pi _{ij}$ and a partition $\sigma$ such that $\Gamma \circ \phi (\sigma ,\pi ) \ne \Gamma \circ \phi (\sigma ,\pi _{ij})$, it must be that $\sigma (i) =p \not = q = \sigma (j)$. Then consider $\sigma '$ such that $\sigma '(i) = q$, $\sigma '(j) = p$, and $\sigma (k) = \sigma '(k) \forall k \not = i,j$. Thus, by Fixed G-P, $\Gamma \circ \phi (\sigma ,\pi _{ij}) = \Gamma \circ \phi (\sigma ',\pi _{ij})$. By construction, $n_p(\sigma , \pi , a ) = n_p(\sigma ',\pi _{ij}, a) \; \forall a$ and $n_q(\sigma , \pi , a ) = n_q(\sigma ',\pi _{ij}, a) \; \forall a$. Hence, LA implies that $\Gamma \circ \phi (\sigma ',\pi _{ij}) = \Gamma \circ \phi (\sigma ,\pi )$, a contradiction. $\square$

Because this proposition holds, we focus in the remainder on the problem of vote swapping; however, it should be borne in mind that our findings also apply to the problem of gerrymandering in a context of fixed size jurisdictions if condition LA is satisfied.

2.3 Axioms

We define two properties that we consider as minimal democratic requirements. The first states that no candidate should have too much power, while the second states that no voter should have too much power.

Minimal Representativity (MinRep): For a candidate to be elected at jurisdictional level, at least one voter needs to have voted for him. In addition, the winner at federal level must have been elected in at least one jurisdiction.

The MinRep condition is a minimal requirement for voting rules aiming at representing the voters’ will. Indeed, any voting rule violating MinRep would allow a candidate to be elected without receiving any votes.

Before stating the second axiom we define the Unanimous vote profile for candidate z as the vote profile $\pi _z$ such that $\pi |_i = z$ for all i in N. We then say that a voter k has a pivotal power in favour of candidate y when, for any partition $\sigma$, we have $\Gamma \circ \phi (\sigma , \pi _z) \ne \Gamma \circ \phi (\sigma , \pi ')$, where $\pi '$ is such that $\pi '|_i = z$ for all $i \in N {\setminus } \{k\}$ and $\pi '|_k = y \not = z$. In other words, a voter with pivotal power can overrule unanimity on his own. Note that, although a voter with pivotal power cannot impose his choice on society, he can change the outcome of the election in one very special case: when all the others agree on the same candidate. We are ready to state our second axiom.

No Pivotal Power (NoPiv): No voter should have pivotal power in favour of any candidate.

This condition is a weakening of the No Veto Power condition introduced by Maskin (1999), which asserts that candidate a should be elected whenever all voters except one vote for him.

As minimal as these two requirements may seem, they are sufficient to rule out the existence of swap-proof representative democracies. This is what we show in the next section.

3 Main result

Theorem 1

Let A be a finite set of candidates. There is no Representative Democracy that simultaneously satisfies MinRep, NoPiv and SwPr.

The proof of this theorem can be found in the Appendix. As it is a constructive proof, it becomes tedious because the size of jurisdictions is fixed but arbitrary, and voting rules $\phi _1$ to $\phi _m$ can all be different. However, we present here the main mechanisms of the proof based on a simple example, so that the reader can grasp the principal ideas without going through the general proof.

Assume there are 2 candidates a and b, 2 jurisdictions $J_1$ and $J_2$ of size 3 each, and assume that $\phi _1 = \phi _2 = \phi$ (i.e. both jurisdictions use the same voting rule). Voters 1 to 3 are assigned to $J_1$, while voters 4 to 6 are assigned to $J_2$. There are four possible federal profiles: $\Pi _1 = \{a,a\}$, $\Pi _2 = \{a,b\}$, $\Pi _3 = \{b,a\}$, $\Pi _4 = \{b,b\}$. By MinRep, $\Gamma (\Pi _1) = a$ and $\Gamma (\Pi _4) = b$. Table 1 summarizes this information and shows that only two outcomes need to be determined. First we show that our axioms imply a federal anonymity condition: Assume $\Gamma (\Pi _2) = a$. Then we show that necessarily $\Gamma (\Pi _3) = a$ (i.e. federal anonymity is implied by the axioms). Consider the vote profile $\pi = \{a, a, a, b, b, b\}$ such that $\pi _{|J_1} = \{a,a,a\}$ and $\pi _{|J_2} = \{b,b,b\}$. By MinRep, the local winners are respectively a and b, so that the federal profile induced is $\Pi _2$. Now, by swapping the votes between 1 and 4, 2 and 5 and 3 and 6 we obtain the vote profile $\pi ' = \{b,b,b,a, a,a\}$ and the associated federal profile $\Pi _3$. By SwPr, the outcome must not have changed, and therefore $\Gamma (\Pi _3) = a$. This federal anonymity property allows us to focus only on federal profiles that are not permutations one of another. In this example, either $\Gamma (\Pi _1) = \Gamma (\Pi _2) = \Gamma (\Pi _3) = a$ and $\Gamma (\Pi _4) = b$ or $\Gamma (\Pi _1) = a$ and $\Gamma (\Pi _2) = \Gamma (\Pi _3) = \Gamma (\Pi _4) = b$.

Table 1 The four possible federal profiles

In the second step, we show that the jurisdictional rules that are consistent with these federal outcomes necessarily violate the NoPiv axiom. Consider the vote profile $\pi$ described above that generates the federal profile $\Pi _2$. When voters 1 and 4 swap their votes, we get ${\pi _{14}}_{|J_1} = \{b,a,a\}$ and ${\pi _{14}}_{|J_2} = \{a,b,b\}$. By SwPr, the winner should not change after a swap, so that $\Gamma \circ \phi (\sigma , \pi _{14}) = a$. Therefore, we cannot have both $\phi (\sigma , \{b,a,a\}) = b$ and $\phi (\sigma , \{a,b,b\}) = b$, otherwise we would have $\Gamma \circ \phi (\sigma , \pi _{14}) = \Gamma (\{b,b\}) = b$ and this would be a contradiction.

Assume $\phi (\sigma , \{b,a,a\}) = a$ and consider the vote profile $\tilde{\pi } = \{b,a,a,b,b,b\}$. Because $\phi (\sigma , \{b,a,a\})= a$ and $\phi (\sigma , \{b,b,b\}) = b$, the winner is a ($\Gamma \circ \phi (\sigma ,\tilde{\pi }) = \Gamma (\{a,b\}) = a$). We can exchange the votes of 2 and 6 and obtain $\tilde{\pi }_{26} = \{b,b,a,b,b,a\}$ and by SwPr, $\Gamma \circ \phi (\sigma ,\tilde{\pi }_{26}) = a$. Thus we must have $\phi (\sigma , \{b,b,a\}) = a$ (otherwise we would get $\Gamma (\{b,b\}) = \Gamma (\Pi _4) = b$, which would be a contradiction).

If one assumes on the contrary that $\phi (\sigma , \{b,a,a\}) = b$, then $\Gamma \circ \phi (\sigma ,\tilde{\pi }) = \Gamma (\{b,b\}) = b$. Once again, swapping votes between 2 and 6 implies that $\phi (\sigma , \{b,b,a\}) = b$. But then $\Gamma (\phi (\sigma , \{b,a,a\}), \phi (\sigma , \{b,b,a\})) = \Gamma (\{b,b\}) = b$, and by swapping votes between 1 and 6, we return to the vote profile $\pi = \{a,a,a,b,b,b\}$. By SwPr, $\Gamma (\phi (\sigma , \{a,a,a\}), \phi (\sigma , \{b,b,b\})) = \Gamma (\Pi _2) = b$, a contradiction.

In summary, we have shown that necessarily, $\phi (\sigma , \pi ) = a$ for any vote profile $\pi$ that contains at least one vote for a, while at the same time, $\Gamma (\Pi ) = a$ for any federal profile $\Pi$ that contains at least one vote for a. This is a voting procedure in which candidate b can only win if he gets every single vote in every jurisdiction. This rule thus gives every voter a pivotal power in favour of candidate a, which is a violation of our axiom NoPiv.

Proposition 2

Axioms MinRep, NoPiv and SwPr are independent.

Proof

We provide three voting rules, each of which satisfies two out of the three axioms.

MinRep and SwPr The priority rule for ordering P is defined as follows: Let $P = a_1 \succ a_2 \succ \cdots \succ a_k$ be a linear ordering over the set of candidates A. Then

• $\forall J_j$, $\phi _j(\sigma , \pi ) = a_t$ if and only if $n_j(\sigma ,\pi , a_s) = 0\; \forall s < t$ and $n_j(\sigma ,\pi , a_t) > 0$.

• $\Gamma (\Pi ) = a_t$ if and only if

  $Card(\{j; \phi _j(\sigma , \pi ) = a_s\}) = 0$ for all $s < t$ and $Card(\{j; \phi _j(\sigma , \pi ) = a_t\}) > 0$.

The priority rule for ordering P is a rule that elects the first candidate on a exogenous list that receives at least one vote. Of course, this rule gives every voter the power to overcome the unanimous decision of the other voters. However, this rule satisfies MinRep because the elected candidate has to receive at least one vote and it is swap-proof.

NoPiv and SwPr Let the constant rule be defined as $\Gamma (\Pi ) = a \forall \Pi \in A^m$. This rule elects candidate a whatever the outcome in the jurisdictions. This rule trivially satisfies NoPiv and SwPr, because the result is independent of what voters do, but it fails to satisfy MinRep.

MinRep and NoPiv Let every jurisdictional rule $\phi _j$ as well as $\Gamma$ be the plurality rule. Then MinRep and NoPiv are both satisfied. However, SwPr is violated. $\square$

Corollary 1

Let A be a finite set of candidates. Then there is no Representative Democracy that simultaneously satisfies LA, MinRep, NoPiv and Fixed G-P.

This corollary is a direct consequence of Proposition 1. It implies that the issues raised in Bervoets and Merlin (2012) about gerrymander-proof representative democracies are not the result of too much flexibility being offered to the manipulator. Rather, the problems are intrinsic to the concept of gerrymander-proofness itself.

4 Conclusion

We have analysed the problem of vote swapping from an axiomatic perspective, in order to find voting rules that are immune to such manipulations. We have imposed two very mild conditions: voters should not have too much individual power (in the sense that they cannot overrule unanimity) and candidates should not have too much power either (in the sense that a candidate must receive at least one vote in order to be elected). Despite the mildness of these axioms, it results that there are no representative democracies that resist manipulation by vote swapping. This is all the more puzzling since the practice of vote swapping is growing in popularity, even being declared legal in some countries.

A natural question that emerges for further research concerns the strategies that candidates and voters want to implement. Strategic considerations are particularly important here because the vote swapping situations we have described could very well be interpreted as a log-rolling situation. Log-rolling is a peculiar type of vote trading by legislative members to obtain the passage of bills of interest. Indeed, in the example used in the Introduction, jurisdictions $J_1$ to $J_3$ could be interpreted as three political issues (say gay marriage, legalisation of marijuana and tax reduction) with the three different parties a, b and c each proposing a particular position on these issues. In this case, an obvious alliance would be for partisans of policy a on issue $J_2$ to vote for b, while partisans of policy b on issue $J_3$ support a in exchange.

In the case of two parties a and b forming a coalition against a third party c, Hartvigsen (2006) offers a preliminary result, by showing that the optimal coordination for the two parties a and b is equivalent to a knapsack problem in terms of complexity.

With more candidates, if candidates a and b form a coalition against c and d for instance, and if voters of a and b engage in strategic swap, then obviously voters for c and d will react by engaging, in turn, in strategic swaps. This defines a game that could be analysed in further research, in order to determine optimal strategies and equilibria.

Further studies should also investigate how sensitive different voting rules are to this manipulation device, in order to compare their robustness to swaps.

Appendix

Proof of Theorem 1

We show that if a Representative Democracy satisfies MinRep and SwPr then it necessarily violates NoPiv. Axiom SwPr says that, for a given vote profile, the outcome of an election should be the same when swaps take place. This should be true for any given vote profile, especially for those vote profiles that contain only two candidates, say a and b. Hence we restrict our attention to these vote profiles and show that NoPiv will be violated.

Let $N(\Pi , a)$ be the number of jurisdictions that have elected candidate a when the federal profile is $\Pi$, and let $N(\Pi )= (N(\Pi , a), N(\Pi , b),\ldots )$.

Definition 1

A representative democracy RD satisfies Federal Anonymity if

$$\begin{aligned} N(\Pi ) = N(\Pi ') \Longrightarrow \Gamma (\Pi ) = \Gamma (\Pi ') \end{aligned}$$

We use the following lemma:

Lemma 1

Let $A = \{a,b\}$. If RD satisfies MinRep and SwPr then g satisfies Federal Anonymity.

Proof of Lemma 1

Consider any federal profile $\Pi$ and define $\Pi '$ such that $\Pi '|_k = \Pi |_k$ for $k \ne i,j$ and $\Pi '|_i = \Pi |_j$, $\Pi '|_j = \Pi |_i$. Assume without loss of generality that $\Pi |_i = a$ and $\Pi |_j = b$. Denote by $t_l^x(\sigma )$ the minimal number of votes for x in $J_l$ such that x is elected in $J_l$. By MinRep, $n_l \ge t_l^x(\sigma ) \ge 1$. Consider the vote profile $\pi$ such that $\pi |_{J_k} = \underbrace{\Pi |_k\ldots \Pi |_k}_{n_k}$ for all $k \ne i,j$, $\pi |_{J_i} = a \ldots a\underbrace{b \ldots b}_{t_i^b(\sigma )-1}$ and $\pi |_{J_j} = b \ldots b \underbrace{a \ldots a}_{t_j^a(\sigma )-1}$. By MinRep, this vote profile leads to $\phi _k(\sigma , \pi ) = \Pi |_k$ for any $k \ne i,j$, to $\phi _i (\sigma , \pi ) = a$ and $\phi _j (\sigma , \pi ) = b$, which is precisely the federal profile $\Pi$.

Now, consider the profile $\pi '$ in which a a voter from $J_i$ swaps his vote with a b voter from $J_j$. The vote profile $\pi '$ is unchanged in any jurisdiction $J_k$, $k \ne i,j$ and $\pi '|_{J_i} = a \ldots a\underbrace{b \ldots b}_{t_i^b(\sigma )}$ and $\pi '|_{J_j} = b \ldots b \underbrace{a \ldots a}_{t_j^a(\sigma )}$. This leads to the federal profile $\Pi '$. By SwPr, $\Gamma (\Pi ) = \Gamma (\Pi ')$. $\square$

Consider any partition $\sigma$ and the individual profile $\pi _a = a \ldots a$. By MinRep, $\phi _j(\sigma , \pi _a) = a$ for all j and thus $\Gamma (\Pi ) = a$ where $\Pi = a \ldots a$. We show that if $\Gamma \circ \phi (\sigma , \pi _a) = a$ then $\Gamma \circ \phi (\sigma , \pi _b) = a$, which clearly violates MinRep.

As in Lemma 1, let $t_j^b(\sigma )$ be the minimal number of votes for b in $J_j$ such that b is the winner in $J_j$. Of course, as the voting rules $\phi _j$ might not be anonymous, we could have $t_j^b(\sigma ) \ne t_j^b(\sigma ')$. However, MinRep guarantees that $0 < t_j^b(\sigma ) \le n_j$. For any federal profile $\Pi$, $N(\Pi ,b)$ is the number of jurisdictions which have elected b. Obviously, $N(\Pi ,b)$ ranges from 0 to m. We show by induction over natural numbers that [$\Gamma (\Pi ) = a$ when $N(\Pi ,b) \le k$] implies that [$\Gamma (\Pi ) = a$ for all $\Pi$ such that $N(\Pi ,b) = k+1$].

$\bullet$ Starting the induction: we have $\Gamma (\Pi ) = a$ when $N(\Pi ,b) = 0$. Consider any partition $\sigma$. Because $n > m$, there is at least one jurisdiction, say $J_j$, with strictly more than one voter. Consider then the vote profile $\pi _0$ such that $\pi _0|_{J_k} = a \ldots a$ for any $k \ne j$ and $\pi _0|_{J_j} = a \ldots ab$. Thus $\pi _0$ is the profile $\pi _a$ in which one single voter has changed his vote to b in jurisdiction $J_j$. By NoPiv, $\Gamma \circ \phi (\sigma , \pi _0) = a$, whether the candidate elected in $J_j$ is a or b.

If $\phi _j(\sigma , \pi _0) = b$, then we have found a federal profile $\Pi$ induced by $\sigma$ and $\pi _0$ such that $N(\Pi ,b) = 1$ and $\Gamma (\Pi ) = a$. By Lemma 1, it is true for any federal profile such that $N(\Pi ,b) = 1$, and thus the induction hypothesis is true for $k = 0$.

Conversely, if $\phi _j(\sigma , \pi _0) = a$, then consider the vote profile $\pi$ such that $\pi |_{J_k} = a \ldots a$ for any $k \ne i,j$, $\pi |_{J_i} = a \ldots a\underbrace{b \ldots b}_{t_i^b(\sigma )-1}$ and $\pi |_{J_j} = a \ldots ab = \pi _0|_{J_j}$.⁹ The corresponding federal profile is $\Pi = a \ldots a$ and therefore $\Gamma (\Pi ) = a$. Now, swap votes between an a voter in $J_i$ and the b voter in $J_j$. We end up with a vote profile $\pi _{ij}$ inducing a federal profile $\Pi _{ij}$ in which every jurisdiction has elected a except jurisdiction $J_i$ which has elected candidate b. By SwPr, the outcome of this election is still a and by Lemma 1, the induction hypothesis is again true for $k=0$.

$\bullet$ Assume $\Gamma (\Pi ) = a$ whenever $N(\Pi ,b) \le k$ (for $k < m$). For any given partition $\sigma$, we have two cases:

Case 1: there is a jurisdiction $J_l$ such that $t_l^b(\sigma ) < n_l$. Assume without loss of generality it is $J_k$ (i.e. $t_k^b(\sigma ) < n_k$). Consider then the profile $\pi$ such that $\pi |_{J_j} = b \ldots b$ for all $j < k$, $j \ne l$, $\pi |_{J_k} = a \ldots a\underbrace{b \ldots b}_{t_k^b(\sigma )+1}$ and $\pi |_{J_{k+1}} = a \ldots a \underbrace{b \ldots b}_{t_{k+1}^b(\sigma )-1}$, while all the voters in the potential remaining jurisdictions vote for a.¹⁰ We have $\phi _j(\sigma , \pi )=b$ for $j < k$, $\phi _j(\sigma , \pi )=a$ for $j> k$, and $\phi _k(\sigma , \pi )$ is not determined. However, the associated federal profile $\Pi$ is such that $N(\Pi ,b) < k$ (if $\phi _k(\sigma , \pi ) = a$) or $N(\Pi ,b) = k$ (if $\phi _k(\sigma , \pi ) = b$). By the induction hypothesis, $\Gamma (\Pi ) = a$.

Consider now that individual i who votes for b in $J_k$ swaps his vote with voter j who votes for a in $J_{k+1}$. With this new vote profile $\pi _{ij}$, the winners in the new federal profile $\Pi _{ij}$ remain the same except for $J_k$ and $J_{k+1}$. In $J_k$ and $J_{k+1}$, we have ${\pi _{ij}}|_{J_k} = a \ldots a\underbrace{b \ldots b}_{t_k^b(\sigma )}$ and ${\pi _{ij}}|_{J_{k+1}} = a \ldots a \underbrace{b \ldots b}_{t_{k+1}^b(\sigma )}$ and thus $\phi _k(\sigma , \pi _{ij}) = b$ and $\phi _{k+1}(\sigma , \pi _{ij}) = b$. By SwPr, the winner of the election should be candidate a, while $N(\Pi _{ij}, b) = k+1$. By Lemma 1, the conclusion obtains.

Case 2: for all l, $t_l^b(\sigma ) = n_l$. This implies that in every jurisdiction, for the given partition $\sigma$, candidate b can be elected only when he receives every vote. We need to distinguish two subcases: induction step k is either lower than $m-1$ or equal to $m-1$.

– Case 2a: $k < m-1$. By assumption, there is at least one jurisdiction with 2 voters. Assume w.l.o.g. that $|J_{k+2}| \ge 2$ and consider the profile $\pi$ such that $\pi |_{J_l} = b \ldots b$ for all $1 \le l \le k$, $\pi |_{J_{k+1}} = a \underbrace{b \ldots b}_{n_{k+1}-1}$ and $\pi |_{J_{k+2}} = \underbrace{a \ldots a}_{n_{k+2}-1} b$ while all voters in all other jurisdictions vote for a. The associated federal profile $\Pi$ is such that $N(\Pi , b) = k$, because $\phi _l(\sigma , \pi ) = a$ for every $l>k$. Swapping the b vote in $J_{k+2}$ with the a vote in $J_{k+1}$, jurisdictions $J_{k+1}$ and $J_{k+2}$ become unanimous respectively in b and in a, so by MinRep, $\phi _{k+1}(\sigma , \pi ) = b$ and $\phi _{k+2}(\sigma , \pi ) = a$. By SwPr the winner is a, although $N(\Pi _{ij}, b) = k+1$.

– Case 2b: $k=m-1$. The vote profile $\pi |_{J_l} = b \ldots b$ for all $1 \le l \le m-1$ and $\pi |_{J_m} = a \underbrace{b \ldots b}_{n_m -1}$ generates the federal profile with $m-1$ b’s and an a in $J_m$. The winner in such a case is candidate a by the induction hypothesis. Changing the sole vote for a into a vote for b cannot change the outcome of the election by virtue of NoPiv, so that the profile $\pi _b = b,\ldots , b$, which generates the unanimous federal profile in b, also elects a as the winner. This is a violation of MinRep. $\square$