Vote swapping in irresolute two-tier voting procedures

We investigate a specific type of group manipulation in two-tier elections, which involves pairs of voters agreeing to exchange their votes. Two-tier elections are modeled as a two-stage choice procedure. In the first stage, voters are distributed into districts, and district preferences result from aggregating voters’ preferences district-wise through some aggregation rule. Final outcomes are obtained in the second stage by applying a social choice function that outputs one or several alternatives from the profile of district preferences. Combining an aggregation rule and a social choice function defines a constitution. Voter preferences, defined as linear orders, are extended to complete binary relations by means of some extension rule. A constitution is swap-proof w.r.t. a given extension rule if one cannot find pairs of voters who, by exchanging their preferences get better off (w.r.t. their extended preference over sets). We consider four specific extension rules: Nehring, Kelly, Fishburn, and Gärdenfors. We establish sufficient conditions for the swap-proofness of a constitution w.r.t. each extension rule. Special attention is paid to majority constitutions, where both the aggregation rule and the social choice function are based on simple majority voting. We show that swap-proofness for majority constitutions pertains to a specific weakening of group strategy-proofness. Moreover, we characterize swap-proof majority constitutions w.r.t. each extension rule. Finally, we show that no constitution based on scoring methods is swap-proof.

1. The reader may refer to Nurmi (1999), Lacy and Niou (2000), Laffond and Lainé (2000), Chambers (2008, 2009), Coffman (2016), Dindar et al. (2017), and the references quoted there.

2. Consider, for instance, the case of two alternatives, a,b, and 15 voters divided into 5 districts, each with size 3. Assume voters 1 to 9 rank a above b, and the remaining 6 voters rank b above a. Consider the partition that places voters 1, 2, 3 in the first district, voters 4, 5, 6 in the second district, and each of the three remaining supporters of a together with 2 supporters of b in one of the last 3 districts. Check that the voting procedure outputs b as the winner. Now, if the locations of voter 3 and one of the b supporters are exchanged, a wins. This example relates to the referendum paradox [see Nurmi 1998, 1999; Lacy and Niou 2000], which holds when indirect majority voting is inconsistent with direct majority voting (i.e., when the choice is made from the voters’ preferences).

3. The interested reader may consult the website https://www.washingtonpost.com/news/wonk/wp/2014/05/15/americas-most-gerrymandered-congressional-districts/ where real districts exhibiting weird shapes are shown.

4. The possibility of reshaping the district map by vote swapping is considered in Bervoets and Merlin (2016). However, their approach does not incorporate any strategic incentives pertaining to voters’ preferences.

5. A good illustration was provided by the (now closed) website http://www.votepair.ca. On the welcome page of this website, the following text appears: “You should pair vote if either: You want to keep a political party from winning. You don’t feel that there is any point in voting for who you want, as the candidate or party has no chance of getting elected. You are tired of your vote not being represented in Parliament”.

6. Once threatened by the California Secretary of State, the websites voteswap2000.com and votexchange2000.com immediately shut their virtual doors.

7. The reader can also refer to Hartvigsen (2008) for a discussion of ethical issues related to vote swapping.

8. This makes it hard to interpret district preferences as those of representatives. However, non-transitive district preferences may naturally arise in real-life elections, as discussed in Sect. 7.

9. Neutrality for aggregation rules \(\theta _{k}\) and an SCF F means that the names of alternatives play no role in the construction of district preferences and in the computation of the outcome from district preferences. Moreover, \(\theta _{k}\) is continuous if whenever a district involves a large enough number of voters with the same preference, this preference defines the district preference.

10. Preliminary versions of some of our results can be found in Dindar et al. (2015).

11. (Group) strategy-proof SCFs (for different extended preferences over sets) are studied in particular by Gärdenfors (1976), Barberà (1977a, 1977b, 2010), Gibbard (1977), Kelly (1977), Feldman (1979a, 1979b), Mac Intyre and Pattanaik (1981), Bandyopadhyay (1982, 1983), Duggan and Schwartz (2000), Barberà et al. (2001), Ching and Zhou (2002), Sato (2008), Umezawa (2009), Brandt (2011, 2015), Brandt and Brill (2011), Brandt et al. (2021, 2022), Botan and Endriss (2021), Brandt and Lederer (2022), and. The relation between group strategy-proofness and swap-proofness is discussed in Sect. 4. In particular, this discussion highlights the close relationship between this paper and the last seven references above.

12. Loosely speaking, an SCF F is weakly group strategy-proof if one cannot find a preference profile and a group of voters that can jointly misrepresent their preferences and make each group member better off w.r.t. both their true and their reported preferences.

13. A linear order is a complete, reflexive, transitive, and antisymmetric binary relation over \(A^{2}\). A tournament is a complete and asymmetric (irreflexive and antisymmetric) binary relation over \(A^{2}\).

14. As neither m nor n is fixed, two voting situations may involve different numbers of alternatives and/or voters.

15. Note that if \(P_{k},P_{k}^{\prime }\) \(\in {\mathcal {C}}\) are asymmetric, \(P_{k}\setminus P_{k}^{\prime }=\) \(\{(a,b)\in A^{2}:a\ne b\), \(aP_{k}b\) and \(bP_{k}^{\prime }a\}\). In this case, \((a,b)\in P\setminus P^{\prime }\) \(\iff\) \((b,a)\in P^{\prime }\setminus P\).

16. Observe that every profile involving an odd number of tournaments is eligible.

17. Given two tournaments \(T,T^{\prime }\) in \({\mathcal {T}}\), the Kemeny distance between T and \(T^{\prime }\) is defined by \(d(T,T^{\prime })=\left| \{(a,b)\in A^{2}:aTb\text { and }bTa\}\right|\), that is the number of pairs of alternatives T and \(T^{\prime }\) disagree on.

18. See Barberà et al. (2004) for an extensive review.

19. An SCF satisfies set-monotonicity if the outcome is invariant under the weakening of unchosen alternatives. Formally, given a district profile P and 2 alternatives a, b with \(bP_{k}a\), let \(P^{k:ab}\) stand for the profile \((P_{1},\ldots ,P_{k-1},P_{k}\setminus \{(b,a)\}\cup \{(a,b)\},P_{k+1},\ldots ,P_{K})\). A SCF F defined on tournament profiles satisfies set-monotonicity for all \(P\in {\mathcal {T}}^{K}\), all \(k\in \{1,\ldots ,K\}\), all \(a\in A\) and all \(b\in F(P)^{C}\), we have \(F(P)=F(P^{k:a,b})\). Note that Brandt (2015) shows that set-monotonicity implies Kelly group strategy-proofness if preferences are linear orders.

20. UC is actually Kelly group strategy-proof. This can be shown by combining Theorem 3 in Brandt (2011) with Remark 2 in Brandt (2015).

21. The word ‘extreme’ refers to the property of either being chosen or being unchosen at both P and \(P^{\prime }\). It is obvious to see that F satisfies WSIUEA if either \(F(P)=F(P^{\prime })\) or [\(F(P)\ne F(P^{\prime })\) and \(|F(P)\cap F(P^{\prime })|>1\)] at any two profiles \(P,P^{\prime }\in {\mathcal {C}}^{K}\) such that \(P\setminus P^{\prime }\subseteq [F(P)^{C}]^{2}\cup [F(P^{\prime })^{C}]^{2}\cup ([F(P)\cap F(P^{\prime })]\otimes [F(P)\cup F(P^{\prime })]^{C})\). Hence, WSIUEA defines a relation between profiles that differ only on extreme alternatives.

22. Observe that a majority-based SCF F satisfies some property \(\overline{ Q }\) if and only if F satisfies Q in restriction to tournament profiles. Indeed, if F violates Q at a pair of tournament profiles \(\{P,P^{\prime }\}\), it also violates Q at the pair of two tournament profiles \(\{{\widetilde{P}},{\widetilde{P}}^{\prime }\}\) where \({\widetilde{P}}=(P,q,-q)\) and \({\widetilde{P}}^{\prime }=(P^{\prime },q,-q)\) with q arbitrarily chosen in \({\mathcal {L}}\). As \({\widetilde{P}}\) and \({\widetilde{P}}^{\prime }\) are weakly different, F violates \(\overline{ Q }\). The converse implication is obvious.

23. Observe that in contrast with WSIUEA, IEA allows profiles P and \(P^{\prime }\) to disagree on jointly chosen alternatives.

24. Computations of BP and UC are made from http://ml.dss.in.tum.de/?profile=1EADBC-1ABCDE-1CDBEA.

25. One can also observe that as UC violates IUA, \(\{\theta _{maj},UC\}\) is not F-SWP (whereas it is K-SWP).

26. \({\widetilde{G}}\) is not a Condorcet SCF. To see why, pick \(K>2\) and a district profile in \({\mathcal {L}}^{K}\) where a is ranked first in all district preferences but the last one, where b is ranked first. Clearly, a is the Condorcet winner in the district profile while \({\widetilde{G}}\) selects \(\{a,b\}\).

27. Finding Condorcet constitutions that are G-SWP but not Gärdenfors strategy-proof remains to be done. It can be shown that this is not possible with three alternatives.

28. According to this approach, one may assume either that candidates are distinct from voters or that some voters are themselves candidates. In both cases, voters’ preferences in each district are aggregated into the transitive preference of the elected candidate.

29. For instance, observe that in the proof of Theorem 6, the construction of successive intermediate profiles that relate P and \(P^{\prime }\) is no longer valid in restriction to linear profiles.

30. See, e.g., Elkind et al. (2017) and Faliszewski et al. (2017).

31. Theorem 5 can be generalized to any two weakly different profiles. Nonetheless, we state it for a specific subclass of weakly different tournament profiles in order to simplify the proofs of Theorems 3, 5, 7, and 9.

32. This construction may involve significant differences between district sizes. Nonetheless, all the districts have an even number of voters, and district sizes can be equalized by adding pairs of stationary voters who have inverse preferences with one another without harming the reasoning.

Authors and Affiliations

1. Efficient Algorithms, Technische Universität Berlin, 10587, Berlin, Germany

   Hayrullah Dindar

2. Murat Sertel Center for Advanced Economic Studies, Istanbul Bilgi University, Istanbul, Turkey

   Hayrullah Dindar & Jean Lainé

3. Conservatoire National des Arts et Métiers, Paris, France

   Jean Lainé

Corresponding author

Correspondence to Jean Lainé.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

We are indebted to two anonymous reviewers and the associate editor for their valuable comments on two previous versions of the paper. This research has been partially funded by the BILGI Research Development Innovation Programme, POlarization viewed from SOcial choice Perspective (POSOP).

Appendix: omitted proofs

1.1 Proof of Theorem 1

Proof of the necessity part:

We start by introducing some additional notation. Given any two alternatives a, b, and any linear order q over A, with a slight abuse of notation, we write [abq] (resp. [qab]) for an order that ranks a first, b second (resp. gives a rank \((m-1)\) and b rank m) and compares all other alternatives in \(A\setminus \{a,b\}\) according to q. Moreover, if \(\{B,B^{\prime }\}\) forms a partition of \(A\setminus \{a,b\}\) into two non-empty sets, and if q (resp. \(q^{\prime }\)) is a linear order over B (resp. \(B^{\prime }\)), we write \([qabq^{\prime }]\) for the order that (1) ranks all elements of B (resp. \(B^{\prime }\)) according to q (resp. \(q^{\prime }\)), (2) ranks a above b and b above all elements in \(B^{\prime }\), and (3) ranks all elements of B above all those in \(A\setminus B\).

We proceed by establishing an intermediate claim. Pick a majority-based SCF F and any two profiles \(P,P^{\prime }\in {\mathcal {T}}^{K}\) such that \(F(P)\ne F(P^{\prime })\). Define \(\varDelta =\{k\in \{1,\ldots ,K\}:\) \(P_{k}\setminus P_{k}^{\prime }\ne \emptyset \}\). Define \(\varGamma _{1}=[F(P^{\prime })^{C}]^{2}\), \(\varGamma _{2}=[F(P)^{C}]^{2}\), \(\varGamma _{3}=[F(P)\cap F(P^{\prime })]\otimes [F(P)\cup F(P^{\prime })]^{C}\), \(\varGamma _{4}=[F(P)\cap F(P^{\prime })]^{2}\), and \(\varGamma _{5}=[F(P)\cap F(P^{\prime })]\otimes ([F(P^{\prime })\setminus F(P^{\prime })]\cup [F(P)\setminus F(P^{\prime })])\).

Claim

If \(P\setminus P^{\prime }\) \(\subseteq \varGamma =\cup _{t=1}^{5}\varGamma _{t}\), there exists a voting situation \(\{{\overline{p}},D\}\) and a set \(\tau\) of swaps such that (1) \(F({\overline{P}}_{D,\theta _{maj}})=F(P)\), and (2) \(F({\overline{P}}_{D,\theta _{maj}}^{\tau })=F(P^{\prime })\).

Proof of Claim

Given that \(P,P^{\prime }\in {\mathcal {T}}^{K}\), we construct a voting situation involving \(K+2\) districts, the last two being given a specific role. District \(K+1\) is used as a reservoir for pairs of voters to be used in the swaps, plus a large enough number of voters with unanimous and arbitrary preferences, \({\tilde{q}}\), to ensure the district preference is \({\tilde{q}}\) (before and after the swaps). District \(K+2\) is used solely to give the inverse district preference \(-{\tilde{q}}\), so the majority tournament is not altered by the addition of these two districts. For each district k in \(\{1,\ldots ,K\}\) and each pair of alternatives (a, b), we assign a specific set of voters to district k with preferences that ensure: (i) \((P,{\tilde{q}},-{\tilde{q}})\) is the prevailing district profile and (ii) \((P^{\prime },{\tilde{q}},-{\tilde{q}})\) can be reached by a set of swaps involving some of these voters plus some voters in district \(K+1\).

Let q be an arbitrary order over A such that \((x,y)\in q\) for all \(x\in F(P^{\prime })\setminus F(P)\) and all \(y\in F(P)\setminus F(P^{\prime })\). Pick \(K+2\) districts \(D_{1},\ldots ,D_{K+2}\) and an arbitrary k in \(\{1,\ldots ,K\}\). For each \((a,b)\in P_{k}\cap P_{k}^{\prime }\), we assign to each district \(D_{k}\) exactly two voters with respective preferences [abq] and \([(-q)ab]\). Now, we consider pairs \((a,b)\in P_{k}\setminus P_{k}^{\prime }\). For each \((a,b)\in P_{k}\setminus P_{k}^{\prime }\), we assign exactly 4 voters \(i^{ab}\), \(j^{ab}\), \(h^{ab}\), \(l^{ab}\) to district \(D_{k}\) and 2 voters \(z^{ab}\), \(t^{ab}\) to district \(D_{K+1}\), whose respective preferences will depend on which set among \(\varGamma _{1},\ldots ,\varGamma _{5}\) the pair (a, b) belongs to.

• If \((a,b)\in \varGamma _{1}\), preferences of \(i^{ab}\), \(j^{ab}\), \(h^{ab}\), \(l^{ab}\) are defined by \(p_{i^{ab}}=p_{j^{ab}}=[abq]\), \(p_{h^{ab}}=[(-q)ab]\), \(p_{l^{ab}}=[(-q)ba]\). Moreover, both \(z^{ab}\), \(t^{ab}\) have preference [baq].

• If \((a,b)\in \varGamma _{2}\), preferences of \(i^{ab}\), \(j^{ab}\), \(h^{ab}\), \(l^{ab}\) are \(p_{i^{ab}}=p_{j^{ab}}=[qab]\), \(p_{h^{ab}}=[ab(-q)]\), and \(p_{l^{ab}}=[ba(-q)]\), while both \(z^{ab}\), \(t^{ab}\) have preference [qba].

• If \((a,b)\in \varGamma _{3}\cup \varGamma _{4}\cup \varGamma _{5}\), preferences of \(i^{ab}\), \(j^{ab}\), \(h^{ab}\), \(l^{ab}\) are \(p_{i^{ab}}=p_{j^{ab}}=[\overline{z }ab{\widehat{z}}]\), \(p_{h^{ab}}=[(-{\widehat{z}})ab(-{\overline{z}})]\), \(p_{l^{ab}}=[(-{\widehat{z}})ba(-{\overline{z}})]\), where \({\overline{z}}=q\mid _{F(P^{\prime })\setminus F(P)}\) and \({\widehat{z}}=q\mid _{A\setminus (\{a,b\}\cup [F(P)\setminus F(P^{\prime })])}\). Moreover, both \(z^{ab}\), \(t^{ab}\) have preference \([{\overline{z}}ba{\widehat{z}}]\).

We repeat the same process for each k in \(\{1,\ldots ,K\}\), it should be noted that, for a given pair a, b: district 1 may be assigned four voters \(i_{1}^{ab}\), \(j_{1}^{ab}\), \(h_{1}^{ab}\), \(l_{1}^{ab}\) with corresponding voters \(z_{1}^{ab}\), \(t_{1}^{ab}\) are added to district \(K+1\), and district 2 may be assigned four voters \(i_{2}^{ab}\), \(j_{2}^{ab}\), \(h_{2}^{ab}\), \(l_{2}^{ab}\) with corresponding voters \(z_{2}^{ab}\), \(t_{2}^{ab}\) are added to district \(K+1\). Nonetheless, we omitted the subscript referring to districts to avoid unnecessary indices.

Finally, denote by Z the number of voters assigned to \(D_{K+1}\) after having considered all pairs \((a,b)\in P\setminus P^{\prime }\). Then, we assign \(Z+1\) extra voters to \(D_{K+1}\) with an arbitrary linear order \({\tilde{q}}\) as preference, and we assign one voter to \(D_{K+2}\) with \(-\tilde{ q}\) as preference.

It is straightforward to check that \(\theta _{maj}\) makes \({\tilde{q}}\) as district preference in \(D_{K+1}\), \(-{\tilde{q}}\) as district preference in \(D_{K+2}\), and \(P_{k}\) as district preference in each \(D_{k}\) with \(k\in \{1,\ldots ,K\}\). It follows that the district profile \({\overline{P}} _{D,\theta _{maj}}\) generated by \(\theta _{maj}\) from \({\overline{p}}\) induces the same majority tournament as the one prevailing for P. Since F is majority-based, one gets \(F({\overline{P}}_{D,\theta _{maj}})=F(P)\). □

Now, consider the set \(\tau\) of swaps, where for each \(k\in \varDelta\), and each \((a,b)\in P_{k}\setminus P_{k}^{\prime }\), voter \(i^{ab}\) swaps with \(z^{ab}\), and voter \(j^{ab}\) swaps with \(t^{ab}\). It is rather obvious to check that

• \({\tilde{q}}\) remains as district preference in \(D_{K+1}\), and \(-{\tilde{q}}\) remains as district preference in \(D_{K+2}\),

• \(P_{k}^{\prime }\) becomes the district preference in each \(D_{k}\) with \(k\in \{1,\ldots ,K\}\).

This implies that \(F({\overline{P}}_{D,\theta _{maj}}^{\tau })=F(P^{\prime })\) , which proves the claim.

We are now ready to show the necessity part. Pick a majority-based SCF F that fails weak group strategy-proofness for \(\gamma \in \{N,K,F,G\}\). We will show that \(\{\theta _{maj},F\}\) is not \(\gamma -\)SWP. By assumption, we can find two profiles \(P=(P_{1},\ldots ,P_{K})\) and \(P^{\prime }=(P_{1}^{\prime },\ldots ,P_{K}^{\prime })\) in \({\mathcal {T}}^{K}\) such that \(\forall k\in \varDelta\), (1) \(F(P^{\prime })\) \(\gamma (P_{k})\) F(P), and (2) \(F(P^{\prime })\) \(\gamma (P_{k}^{\prime })\) F(P).

Suppose \(\gamma =N\). It follows that \(F(P)\cap F(P^{\prime })=\emptyset\) and \(P\setminus P^{\prime }\subseteq \varGamma _{1}\cup \varGamma _{2}\). Hence, we can build the voting situation within the above claim. Moreover, it follows from the definition of q in the proof of the claim that \(F(P^{\prime })\) \(p_{i}^{N}\) F(P) for all \(i\in S(\tau )\). This shows that \(\{\theta _{maj},F\}\) is not N-SWP. Similarly, if \(\gamma =K\), then \(\left| F(P)\cap F(P^{\prime })\right| =1\) and \(P\setminus P^{\prime }\subseteq \varGamma _{1}\cup \varGamma _{2}\cup \varGamma _{3}\). With the convention \(F(P)\cap F(P^{\prime })=\{a\}\), one also gets that \(F(P^{\prime })\) \(p_{i}^{K}\) F(P) for all \(i\in S(\tau )\), which leads to the same conclusion. Finally, if \(\gamma =F\) (resp. G), then \(P\setminus P^{\prime }\subseteq \varGamma \setminus \varGamma _{5}\) (resp. \(\varGamma\)). Hence, the argument above still applies, while it is straightforward to check that \(F(P^{\prime })\) \(p_{i}^{F}\) F(P) (resp. \(F(P^{\prime })\) \(p_{i}^{G}\) F(P)) for all \(i\in S(\tau )\). As \(\{\theta _{maj},F\}\) is not F-SWP (resp. G-SWP), the proof of the necessity part is complete.

Proof of the sufficiency part:

Pick a majority-based SCF F, we will show that if \(\{\theta _{maj},F\}\) is not K-SWP then F fails weak Kelly group strategy-proofness. To do so, we pick a voting situation where there is a profitable set of swaps. Then we associate with each district preference a fictitious voter. Finally, we derive from the resulting tournament profile another tournament profile where a group of voters has an incentive to manipulate.

Pick a voting situation \(\{p,D\}\) and a set \(\tau =\{\tau _{1},\ldots ,\tau _{H}\}\) of mutually disjoint transpositions of I such that \(F(P^{\prime })\) \(p_{i}^{K}\) F(P) for all \(i\in S(\tau )\), where \(P=P_{D,\theta ^{maj}}\) and \(P^{\prime }=P_{D,\theta ^{maj}}^{\tau }\). By definition of Kelly extension, we must have

1. (1)

   \(\forall k\in \{1,\ldots ,K\}\), \(P_{k}\setminus P_{k}^{\prime }\subseteq [F(P)^{C}]^{2}\cup [F(P^{\prime })^{C}]^{2}\cup ([F(P)\cap F(P^{\prime })]\otimes [F(P)\cup F(P^{\prime })]^{C})\).

   From this point on in the proof, we will treat each district \(k\in \{1,\ldots ,K\}\) as a fictitious individual with a tournament \(P_{k}\) as preference.

   Define \(\varDelta =\{\) \(k\in \{1,\ldots ,K\}\): \(P_{k}\ne P_{k}^{\prime }\}\). We construct two additional tournament profiles \({\bar{P}}\), \({\bar{P}}^{\prime }\) from P, \(P^{\prime }\) as follows:

   1. (i)

      \(\forall k\in \{1,\ldots ,K\}\setminus \varDelta\), \({\bar{P}}_{k}=P_{k}\) and \({\bar{P}}_{k}^{\prime }=P_{k}^{\prime }\),

   2. (ii)

      \(\forall k\in \varDelta\), \(\forall x\in F(P^{\prime })\setminus F(P)\), \(\forall y\in F(P^{\prime })\cap F(P)\), \(\forall z\in F(P)\setminus F(P^{\prime })\), x \({\bar{P}}_{k}\) y, z and y \({\bar{P}}_{k}\) z. Similarly x \({\bar{P}}_{k}^{\prime }\) y, z and y \({\bar{P}}_{k}^{\prime }\) z, while for any other pair of alternatives t, u, \({\bar{P}} _{k}|_{\{t,u\}}=P_{k}|_{\{t,u\}}\) and \({\bar{P}}_{k}^{\prime }|_{\{t,u\}}=P_{k}^{\prime }|_{\{t,u\}}\).

      Hence, \(T_{P}\) and \(T_{{\bar{P}}}\) (resp. \(T_{P^{\prime }}\) and \(T_{{\bar{P}} ^{\prime }}\)) only differ on pairs of alternatives involved in (ii). Moreover, \(T_{P}\) and \(T_{P^{\prime }}\) agree on these pairs of alternatives. Furthermore, (1) holds for \({\bar{P}}\) and \({\bar{P}}^{\prime }\), and by (ii) we have

2. (2)

   \(\forall k\in \varDelta\), \(F(P^{\prime })\) \({\bar{P}}_{k}^{K}\) F(P) and \(F(P^{\prime })\) \({\bar{P}}_{k}^{\prime K}\) F(P).

As a last step in the proof, we will define \({\tilde{P}}\) (resp. \({\tilde{P}} ^{\prime }\)) by enlarging \({\overline{P}}\) ( resp. \({\bar{P}}^{\prime }\)) with an even number of additional voters so that \(T_{{\widetilde{P}}}=T_{P}\) and \(T_{{\widetilde{P}}^{\prime }}=T_{P^{\prime }}\).

Take any \(x,y\in A\), define \(m_{xy}=1+|\{k\in \varDelta :xP_{k}y\) and \(y{\bar{P}} _{k}x\}|\), and set \(L_{xy}\)to be the even number in \(\{m_{xy}+1,m_{xy}+2\}\) . Take any linear order \({\tilde{q}}\) on A. Define preferences of the first half of the \(L_{xy}\) individuals to be \([xy{\tilde{q}}]\) and the other half to be \([(-{\tilde{q}})xy]\). Observe that this profile of \(L_{xy}\) voters gives a majority margin of at least \(m_{xy}+1\) in favor of x over y and is neutral regarding the comparison of any other alternatives. Next, we replicate the same procedure for every pair of alternatives in \(\varLambda =\{(x,y)\in A^{2}:xT_{P}y\) and \(yT_{{\bar{P}}}x\}\) by adding disjoint sets of voters. Following this procedure, we reach \({\tilde{P}}\) (resp. \({\tilde{P}} ^{\prime }\)) by enlarging \({\overline{P}}\) (resp. \({\bar{P}}^{\prime }\)) with \(L=\sum _{(x,y)\in \varLambda }L_{xy}\) additional individuals.

By construction, \(T_{{\tilde{P}}}=T_{P}\). Furthermore, note that since (1) holds for \({\bar{P}}\) and \({\bar{P}}^{\prime }\), and also for P and \(P^{\prime }\), then \(T_{{\tilde{P}}^{\prime }}=T_{P^{\prime }}\). As F is majority-based, we get \(F({\tilde{P}})=F(P)\) and \(F({\tilde{P}}^{\prime })=\) \(F(P^{\prime })\). Finally, since, \(\forall k\in \varDelta\), \({\tilde{P}}_{k}^{K}= {\bar{P}}_{k}^{K}\) and \({\tilde{P}}_{k}^{\prime K}={\bar{P}}_{k}^{\prime K}\), we get from (2) that \(\forall k\in \varDelta\), \(F({\tilde{P}}^{\prime })\) \({\tilde{P}} _{k}^{K}\) \(F({\tilde{P}})\) and \(F({\tilde{P}}^{\prime })\) \({\tilde{P}}_{k}^{\prime K}\) \(F({\tilde{P}})\). Therefore, F is not Kelly weakly group strategy-proof.

Finally, the proof is essentially the same for the three other preference extensions, up to relevant changes in (1), (ii), and (2) above.

1.2 Proof of Theorem 2

Let \(\{\theta ,F\}\) be a constitution where \(\theta\) satisfies IIA and F satisfies WSIUEA. Suppose \(\{\theta ,F\}\) is not K-SWP. Thus there exists a voting situation \(\{p,D\}\) and a set \(\tau =\{\tau _{1},\ldots ,\tau _{H}\}\) of mutually disjoint transpositions of I such that \(F(P^{\prime })\) \(p_{i}^{K}\) F(P) for all \(i\in S(\tau )\), with \(P=P_{D,\theta _{maj}}\) and \(P^{\prime }=P_{D,\theta _{maj}}^{\tau }\). From definition of K, we get

1. (1)

   \(F(P)\ne F(P^{\prime })\) and \(\left| F(P)\cap F(P^{\prime })\right| \le 1\),

2. (2)

   \(\forall i\in S(\tau )\), \(p_{i}\cap p_{i}^{\tau }\subseteq F(P)\otimes F(P^{\prime })\).

Since \(p_{i}\setminus p_{i}^{\tau }\ne \emptyset\) if and only if \(i\in S(\tau )\), (2) combined with IIA imply \(\forall k\in \{1,\ldots ,K\}\), \(P_{k}^{\prime }\cap P_{k}\subseteq F(P)\otimes F(P^{\prime })\). Therefore \(P^{\prime }\setminus P\subseteq F(P)\otimes F(P^{\prime })\). Finally, by WSIUEA, either \(F(P)=F(P^{\prime })\) or \(\left| F(P)\cap F(P^{\prime })\right| \le 1\), in contradiction with (1).

1.3 Proof of Theorem 4

Let \(\{\theta ,F\}\) be a constitution where \(\theta\) satisfies IIA and F satisfies WSIUA. Suppose \(\{\theta ,F\}\) is not N-SWP. Thus, there exist a voting situation \(\{p,D\}\) and a set \(\tau =\{\tau _{1},\ldots ,\tau _{H}\}\) of mutually disjoint transpositions of I such that \(F(P^{\prime })\) \(p_{i}^{N}\) F(P) for all \(i\in S(\tau )\), where \(P=P_{D,\theta }\) and \(P^{\prime }=P_{D,\theta }^{\tau }\). By the definition of N, we have

1. (1)

   \(F(P)\cap F(P^{\prime })=\emptyset\) .

2. (2)

   \(\forall i\in I\), \(p_{i}^{\tau }\cap p_{i}\supseteq F(P)\otimes F(P^{\prime })\).

Since \(p_{i}\setminus p_{i}^{\tau }\ne \emptyset\) if and only if \(i\in S(\tau )\), by IIA combined with (2) we get \(\forall k\in \{1,\ldots ,K\}\), \(P_{k}\cap P_{k}^{\prime }\supseteq F(P)\otimes F(P^{\prime })\). Hence, \(P^{\prime }\cap P\supseteq F(P)\otimes F(P^{\prime })\). Finally, by WSIUA, \(F(P)\cap F(P^{\prime })\ne \emptyset\), in contradiction with (1).

1.4 Proof of Theorem 6

Let \(\{\theta ,F\}\) be a constitution such that \(\theta\) satisfies IIA, and F satisfies IUA and IEA. Suppose \(\{\theta ,F\}\) is not F-SWP. Thus, there exist a voting situation \(\{p,D\}\) and a set \(\tau\) of mutually disjoint transpositions of N such that \(F(P_{D,\theta }^{\tau })\) \(p_{i}^{F}\) \(F(P_{D,\theta })\) for all \(i\in S(\tau )\). To simplify notations, we write \(P=P_{D,\theta }\) and \(P^{\prime }=P_{D,\theta }^{\tau }\). Clearly, we have \(F(P)\ne F(P^{\prime })\). Pick any \(i\in S(\tau )\), and consider \((a,b)\in p_{i}^{\tau }\setminus p_{i}\). By definition of the Fishburn preference extension, one of the following two cases must hold:

1. (1)

   \((a,b)\in [F(P^{\prime })\setminus F(P)]^{2}\cup [F(P)\setminus F(P^{\prime })]^{2}\cup [F(P^{\prime })\cap F(P)]^{2}\),

2. (2)

   \((a,b)\in [F(P^{\prime })^{C}\cap F(P)^{C}]\otimes A\),

Clearly, in both cases, \((a,b)\in [F(P)^{C}]^{2}\cup [F(P^{\prime })^{C}]^{2}\cup [F(P^{\prime })\cap F(P)]^{2}\cup ([F(P)\cap F(P^{\prime })]\otimes [F(P^{\prime })^{C}\cap F(P)^{C}])\) . By IIA, we get \(P^{\prime }\setminus P\subseteq [F(P)^{C}]^{2}\cup [F(P^{\prime })^{C}]^{2}\cup [F(P^{\prime })\cap F(P)]^{2}\cup ([F(P)\cap F(P^{\prime })]\otimes [F(P^{\prime })\cup F(P)]^{C})\). Finally, by IUA combined with IEA, one can show that \(F(P)=F(P^{\prime })\). To do that, define \({\bar{P}}\) by \(\forall (a,b)\notin [F(P)^{C}]^{2}\) \({\bar{P}} |_{\{a,b\}}=P|_{\{a,b\}}\) and \(\forall (a,b)\in [F(P)^{C}]^{2}\) \(\bar{ P}|_{\{a,b\}}=P^{\prime }|_{\{a,b\}}\). Similarly, define \({\bar{P}}^{\prime }\) by \(\forall (a,b)\notin [F(P^{\prime })^{C}]^{2}\setminus [F(P)^{C}]^{2}\) \({\bar{P}}^{\prime }|_{\{a,b\}}=P^{\prime }|_{\{a,b\}}\) and \(\forall (a,b)\in [F(P^{\prime })^{C}]^{2}\setminus [F(P)^{C}]^{2}\) \({\bar{P}}^{\prime }|_{\{a,b\}}=P|_{\{a,b\}}\). By IUA, \(F({\bar{P}})=F(P)\) and \(F({\bar{P}}^{\prime })=F(P^{\prime })\). By definition of \({\bar{P}}\) and \({\bar{P}}^{\prime }\), \({\bar{P}}\setminus {\bar{P}}^{\prime }\subseteq [F({\bar{P}}^{\prime })\cap F({\bar{P}})]^{2}\cup ([F({\bar{P}} )\cap F({\bar{P}}^{\prime })]\otimes [F({\bar{P}}^{\prime })^{C}\cap F( {\bar{P}})^{C}])\), thus \(F({\bar{P}})=F({\bar{P}}^{\prime })\) by IEA. This implies \(F(P)=F(P^{\prime })\), the desired contradiction.

1.5 Proof of Theorem 8

Take a constitution \(\{\theta ,F\}\) where \(\theta\) satisfies IIA and F satisfies IUA, IEA, and SDP. Suppose \(\{\theta ,F\}\) is not G-SWP. Thus, there exist a voting situation \(\{p,D\}\) and a set \(\tau\) of mutually disjoint transpositions of N such that \(\emptyset \ne S\subseteq V\) such that \(F(P^{\prime })\) \(p_{i}^{G}\) F(P) for all \(i\in S(\tau )\), with \(P=P_{D,\theta }\) and \(P^{\prime }=P_{D,\theta }^{\tau }\). Clearly, \(F(P)\ne F(P^{\prime })\). We distinguish between three possible cases:

Case 1: \(F(P^{\prime })\subset F(P)\) or \(F(P)\subset F(P^{\prime })\) .

Since the Gärdenfors and Fishburn preference extensions agree on the comparison of \(F(P^{\prime })\) and F(P) sets, by the same argument as in the proof of Theorem 6 (which combines IUA with IEA), we get \(F(P)=F(P^{\prime })\), a contradiction.

Case 2: Neither \(F(P^{\prime })\subset F(P)\) nor \(F(P)\subset F(P^{\prime })\) and \(\forall i\in S(\tau )\), \(xp_{i}y\) for all \(x\in F(P^{\prime })\setminus F(P)\) and \(y\in F(P)\setminus F(P^{\prime })\).

By IIA, \(P_{k}|_{\{a,b\}}=P_{k}^{\prime }|_{\{a,b\}}\) for all \(k\in \{1,\ldots ,K\}\) and all \(a,b\in A\) with \(a\in F(P)\setminus F(P^{\prime })\) and \(b\in F(P^{\prime })\setminus F(P)\). By SDP, we get either \(F(P)\subseteq F(P^{\prime })\) or \(F(P^{\prime })\subseteq F(P)\), a contradiction.

1.6 Proofs of Theorems 3, 5, 7, and 9

1.6.1 A representation result

First, observe that the sufficiency part of Theorem 3 (resp. 5, 7, 9) follows from Theorem 2 (resp. 4, 6, 8). We establish below a result that will play an important role in the proof of the necessary parts of Theorems 3, 5, 7, and 9. This result states that any two weakly different tournament profiles can be derived from each other by means of a set of disjoint transpositions of the set of voters. The proof is based on a construction similar to the one used in McGarvey (1953) to show that every tournament can be obtained by computing all majority pairwise comparisons at some profile of linear orders.

Proposition 5

Take any two weakly different tournament profiles P and \(P^{\prime }\), and take an SCF F such that \((P\setminus P^{\prime })\cap ([F(P^{\prime })\setminus F(P)]\otimes [F(P)\setminus F(P^{\prime })])=\emptyset\). There exist a voting situation \(\{p,D\}\) and a set \(\tau\) of mutually disjoint transpositions of N such that (1) \(P=P_{D,\theta _{maj}}\) and (2) \(P^{\prime }=P_{D,\theta _{maj}}^{\tau }\).^{Footnote 31}

Proof

Notation [abq], [qab],  and \([qabq^{\prime }]\) means the same as in the proof of theorem 1. We will construct a specific voter profile by successively considering all pairs of alternatives \(\{a,b\}\) in \(P\setminus P^{\prime }\). Pick any \((a,b)\in P\setminus P^{\prime }\), and assume w.l.o.g. that \(1\in {\mathcal {D}} _{ab}\). Hence, \(aP_{1}b\) and \(bP_{1}^{\prime }a\). Take any linear order \({\widetilde{q}}\) over A such that \(\forall x\in F(P)\setminus F(P^{\prime })\) , \(\forall y\in F(P)\cap F(P^{\prime })\), and \(\forall z\in F(P^{\prime })\setminus F(P)\) we have \(x{\widetilde{q}}y\), \(x{\widetilde{q}}z\), and \(y {\widetilde{q}}z\). Now, consider the following possible cases:

Case 1: \({\mathcal {D}}_{ba}\ne \emptyset\).

Hence, one can find at least one \(k\in \{2,\ldots ,K\}\) such that \((b,a)\in P_{k}\setminus P_{k}^{\prime }\). Pick any such k. We assign to district \(D_{1}\) the set of voters \(I^{1k}(a,b)=\{1_{1k}^{ab},\ldots ,6_{1k}^{ab}\}\) and we assign to district \(D_{k}\) the set of voters \(I^{k1}(a,b)= \{1_{k1}^{ab},\ldots ,6_{k1}^{ab}\}\) with preferences depending on which of the three possible situations below prevails.

Case 1.a: \(\{a,b\}\subseteq F(P)^{C}\).

Voters in \(I^{1k}(a,b)\) and voters in \(I^{k1}(a,b)\) have preferences below:

Case 1.b: \(\{a,b\}\subseteq F(P^{\prime })^{C}\).

Voters in \(I^{1k}(a,b)\) and voters in \(I^{k1}(a,b)\) have preferences below:

Case 1.c: \(\{a,b\}\cap [F(P)\cap F(P^{\prime })]\ne \emptyset\).

To simplify notation in the following two tables, we write \({\hat{q}}= {\widetilde{q}}|_{F(P^{\prime })}\)and \(\check{q}={\widetilde{q}}|_{F(P^{\prime })^{C}}\).

Voters in \(I^{1k}(a,b)\) and voters in \(I^{k1}(a,b)\) have preferences below:

Now, for any \(k^{\prime }\in {\mathcal {D}}_{ba}\setminus \{k\}\), we replicate the same procedure by assigning respectively to districts \(D_{1}\) and \(D_{k^{\prime }}\) mutually disjoint sets of voters \(I^{1k^{\prime }}(a,b)\) and \(I^{k^{\prime }1}(a,b)\) defined as above. Thus, \(\forall k,k^{\prime }\in {\mathcal {D}}_{ba}\) with \(k\ne k^{\prime }\), we have \(I^{1k}(a,b)\cap I^{1k^{\prime }}(a,b)=\emptyset\) and \(I^{k1}(a,b)\cap I^{k^{\prime }1}(a,b)=\emptyset\).

Case 2: \({\mathcal {D}}_{ba}=\emptyset\).

Thus, \(\forall k\ne 1\), either \(k\in {\mathcal {D}}_{ab}\) or \((a,b)\in P_{k}\cap P_{k}^{\prime }\) or \((b,a)\in P_{k}\cap P_{k}^{\prime }\). Since P , \(P^{\prime }\) are weakly different, there exists \(k\ne 1\) such that \((a,b)\in P_{k}\cap P_{k}^{\prime }\) or \((b,a)\in P_{k}\cap P_{k}^{\prime }\). We assign the set of voters \(I^{1k}(a,b)=\{1_{1k}^{ab},\ldots ,6_{1k}^{ab}\}\) to district \(D_{1}\) and the set of voters \(I^{k1}(a,b)=\{1_{k1}^{ab},\ldots ,8_{k1}^{ab}\}\) to \(D_{k}\), with respective preferences depending on three possible situations:

Case 2.a: \(\{a,b\}\subseteq F(P)^{C}\).

Voters in \(I^{1k}(a,b)\) have the same preferences as in case 1a, and voters in \(I^{k1}(a,b)=\{1_{k1}^{ab},\ldots ,8_{k1}^{ab}\}\) have preferences as below:

• if \((a,b)\in P_{k}\cap P_{k}^{\prime }\),

  $$\begin{aligned} \textit{Table 7 }p\mid _{I^{k1}(a,b)}=\left( \begin{array}{ccc} p_{i},i\in \{1_{k1}^{ab},2_{k1}^{ab}\} &{} p_{i},i\in \{3_{k1}^{ab},4_{k1}^{ab}\} &{} p_{i},i\in \{5_{k1}^{ab},\ldots ,8_{k1}^{ab}\} \\ \hline [ba{\widetilde{q}}] &{} [ab{\widetilde{q}}] &{} [(-{\widetilde{q}})ab] \end{array} \right) , \end{aligned}$$

• if \((b,a)\in P_{k}\cap P_{k}^{\prime } ,\)

  $$\begin{aligned} \textit{Table 8 }p\mid _{I^{k1}(a,b)}=\left( \begin{array}{ccc} p_{i},i\in \{1_{k1}^{ab},2_{k1}^{ab}\} &{} p_{i},i\in \{3_{k1}^{ab},4_{k1}^{ab}\} &{} p_{i},i\in \{5_{k1}^{ab},\ldots ,8_{k1}^{ab}\} \\ \hline [ba{\widetilde{q}}] &{} [ba{\widetilde{q}}] &{} [(-{\widetilde{q}})ba] \end{array} \right) . \end{aligned}$$

  Case 2.b: \(\{a,b\}\subseteq F(P^{\prime })^{C}\).

  Voters in \(I^{1k}(a,b)\) have the same preferences as in case 1a, and voters in \(I^{k1}(a,b)=\{1_{k1}^{ab},\ldots ,8_{k1}^{ab}\}\) have preferences as below:

• if \((a,b)\in P_{k}\cap P_{k}^{\prime }\),

  $$\begin{aligned} \textit{Table 9 }p\mid _{I^{k1}(a,b)}=\left( \begin{array}{ccc} p_{i},i\in \{1_{k1}^{ab},2_{k1}^{ab}\} &{} p_{i},i\in \{3_{k1}^{ab},4_{k1}^{ab}\} &{} p_{i},i\in \{5_{k1}^{ab},\ldots ,8_{k1}^{ab}\} \\ \hline [{\widetilde{q}}ba] &{} [{\widetilde{q}}ab] &{} [ab(-{\widetilde{q}})] \end{array} \right) , \end{aligned}$$

• if \((b,a)\in P_{k}\cap P_{k}^{\prime } ,\)

  $$\begin{aligned} \textit{Table 10 }p\mid _{I^{k1}(a,b)}=\left( \begin{array}{ccc} p_{i},i\in \{1_{k1}^{ab},2_{k1}^{ab}\} &{} p_{i},i\in \{3_{k1}^{ab},4_{k1}^{ab}\} &{} p_{i},i\in \{5_{k1}^{ab},\ldots ,8_{k1}^{ab}\} \\ \hline [{\widetilde{q}}ba] &{} [{\widetilde{q}}ba] &{} [ba(-{\widetilde{q}})] \end{array} \right) . \end{aligned}$$

  Case 2.c: \(\{a,b\}\cap [F(P)\cap F(P^{\prime })]\ne \emptyset\).

  Voters in \(I^{1k}(a,b)\) have the same preferences as in case 1a, and voters in \(I^{k1}(a,b)=\{1_{k1}^{ab},\ldots ,8_{k1}^{ab}\}\) have preferences as below:

• if \((a,b)\in P_{k}\cap P_{k}^{\prime }\),

  $$\begin{aligned} \textit{Table 11 }p\mid _{I^{k1}(a,b)}=\left( \begin{array}{ccc} p_{i},i\in \{1_{k1}^{ab},2_{k1}^{ab}\} &{} p_{i},i\in \{3_{k1}^{ab},4_{k1}^{ab}\} &{} p_{i},i\in \{5_{k1}^{ab},\ldots ,8_{k1}^{ab}\} \\ \hline [{\hat{q}}ba\check{q}] &{} [{\hat{q}}ab\check{q}] &{} [(-\check{q})ab(- {\hat{q}})] \end{array} \right) , \end{aligned}$$

• if \((b,a)\in P_{k}\cap P_{k}^{\prime }\),

  $$\begin{aligned} \textit{Table 12 }p\mid _{I^{k1}(a,b)}=\left( \begin{array}{ccc} p_{i},i\in \{1_{k1}^{ab},2_{k1}^{ab}\} &{} p_{i},i\in \{3_{k1}^{ab},4_{k1}^{ab}\} &{} p_{i},i\in \{5_{k1}^{ab},\ldots ,8_{k1}^{ab}\} \\ \hline [{\hat{q}}ba\check{q}] &{} [{\hat{q}}ba\check{q}] &{} [(-\check{q})ba(- {\hat{q}})] \end{array} \right) . \end{aligned}$$

We replicate the same construction for all h with \(h\in {\mathcal {D}} _{ab}\setminus \{1\}\), leading to additional mutually disjoint sets of voters. Hence, for any \(h,h^{\prime }\in {\mathcal {D}}_{ab}\) with and any \(k,k^{\prime }\notin {\mathcal {D}}_{ab}\), we have \(I^{hk}(a,b)\cap I^{hk^{\prime }}(a,b)=\emptyset\), \(I^{kh}(a,b)\cap I^{k^{\prime }h}(a,b)=\emptyset\), and \(I^{hk}(a,b)\cap I^{h^{\prime }k^{\prime }}(a,b)=\emptyset\).

Next, we replicate the same procedure for all pairs \((a^{\prime },b^{\prime })\ne (a,b)\) with \({\mathcal {D}}_{a^{\prime }b^{\prime }}\ne \emptyset\), all corresponding assigned sets of voters being disjoint from those assigned for (a, b). Hence, \(I^{hk}(a,b)\cap I^{hk}(a^{\prime },b^{\prime })=\emptyset\) for all \(h,k\in \{1,\ldots ,K\}\).

Finally, consider any \((a,b)\in P\cap P^{\prime }\). Hence, for all \(k\in \{1,\ldots ,K\}\), either \((a,b)\in P_{k}\cap P_{k}^{\prime }\) or \((b,a)\in P_{k}\cap P_{k}^{\prime }\). Assuming w.l.o.g. that \(\forall k\in \{1,\ldots ,K\}\), \((a,b)\in P_{k}\cap P_{k}^{\prime }\), we assign to each \(D_{k}\) a set voters evenly distributed between two types \(1_{k}^{ab},2_{k}^{ab}\) with respective preferences as below:

It is straightforward to check that the resulting voter profile p satisfies condition (1). Indeed, take any \((a,b)\in P\setminus P^{\prime }\) , and pick any \(k\in \{1,\ldots ,K\}\). If \(k\in {\mathcal {D}}_{ab}\), then \(D_{k}\) involves one set or several disjoint sets of voters, and in each set, a wins against b with a majority of two voters. If \(k\notin {\mathcal {D}} _{ab}\cup {\mathcal {D}}_{ba}\) and \(aP_{k}b\), a wins against b with a majority of four voters in each of the mutually disjoint sets of voters in \(D_{k}\).

To show that condition (2) holds, pick any \((a,b)\in P\setminus P^{\prime }\) , and pick all \(h\in {\mathcal {D}}_{ab}\). If \({\mathcal {D}}_{ba}\ne \emptyset\) , pick all \(k\in {\mathcal {D}}_{ba}\) and let voters \(1_{hk}^{ab}\) and \(2_{hk}^{ab}\) in each \(D_{h}\) swap their preferences with voters \(1_{kh}^{ab}\) and \(2_{kh}^{ab}\). It follows that the majority will between a and b is reversed in both \(P_{h}\) and \(P_{k}\). Similarly, if \({\mathcal {D}} _{ba}=\emptyset\), let voters \(1_{hk}^{ab}\) and \(2_{hk}^{ab}\) swap their preference with voters \(1_{kh}^{ab},2_{kh}^{ab}\). These swaps reverse the majority will in \(P_{h}\) but not in \(P_{k}\). Finally, observe that these swaps do not bring any change in the comparison of any other alternatives, since preferences in all assigned subsets of voters create ties in all pairwise majority comparisons but the one involving a and b.^{Footnote 32} □

We are now ready to prove Theorems 3, 5, 7 and 9. Proofs are very similar, and all are by contradiction. Assuming that one relevant property for F is violated at some pair of weakly different district profiles \(\{P,P^{\prime }\}\), we first derive the relation which prevails between \(P\setminus P^{\prime }\), F(P), and \(F(P^{\prime })\). It turns out that regardless of this relation, one always has \((P\setminus P^{\prime })\cap ([F(P^{\prime })\setminus\) \(F(P)]\otimes [F(P)\setminus\) \(F(P^{\prime })])=\emptyset\). Hence, Proposition 5 applies. Then we show that swap-proofness is violated by taking the voting situation \(\{p,D\}\) built in the proof of Proposition 5, and by considering the set \(\tau\) of mutually disjoint transpositions where for all \(h\in \mathcal { D}_{ab}\) and \(k\notin {\mathcal {D}}_{ab}\), voters \(1_{hk}^{ab}\) and \(2_{hk}^{ab}\) in \(D_{h}\) swap their preferences with voters \(1_{kh}^{ab}\) and \(2_{kh}^{ab}\) in \(D_{k}\). Hence, \(S(\tau )=\cup _{(a,b)\in P\setminus P^{\prime }}S^{ab}(\tau )\), where \(S^{ab}(\tau )\) contains all sets \(\{1_{kh}^{ab},2_{kh}^{ab},1_{hk}^{ab},2_{hk}^{ab}\}\) with \(h\in {\mathcal {D}} _{ab}\) and \(k\notin {\mathcal {D}}_{ab}\). Observe that by construction, all sets \(S^{ab}(\tau )\) are mutually disjoint. Thus, to show that swap-proofness does not hold for \(\gamma \in \{N,K,F,G\}\), it suffices to show that \(F(P^{\prime })\) \(\gamma (p_{i})\) F(P) for all \(i\in S^{ab}(\tau )\) and all \((a,b)\in P\setminus P^{\prime }\). To avoid unnecessary repetition in the proofs below, we will simply write “Proposition 5 applies” to refer to this construction, and continue by arguing why extension-specific preferences hold for all voters in \(S(\tau )\).

1.6.2 Proofs of Theorems 3 and 5

Pick a majority-based SCF \(F:{\mathcal {T}}^{K}\rightarrow A\).

Suppose that F violates \(\overline{ WSIUEA }\). Thus, there exist two weakly different profiles \(P,P^{\prime }\in {\mathcal {T}}^{K}\) such that \(P\setminus P^{\prime }\subseteq [F(P)^{C}]^{2}\cup [F(P^{\prime })^{C}]^{2}\cup ([F(P)\cap F(P^{\prime })]\otimes [F(P)\cup F(P^{\prime })]^{C})\), \(F(P)\ne F(P^{\prime })\) and \(|F(P)\cap F(P^{\prime })|\) \(\le 1\). This in turn implies \((P\setminus P^{\prime })\cap ([F(P^{\prime })\setminus\) \(F(P)]\otimes [F(P)\setminus\) \(F(P^{\prime })])=\emptyset\), and thus Proposition 5 applies.

Pick any \((a,b)\in P\setminus P^{\prime }\). We claim that \(F(P^{\prime })\) \(p_{i}^{K}\) F(P) for all \(i\in S^{ab}(\tau )\).

To see why, suppose that \((a,b)\in [F(P)\cap F(P^{\prime })]\times [F(P)\cup F(P^{\prime })]^{C}\). The definition of p in cases 1.c and 2.c in the proof of Proposition 5 combined with the definition of \({\widetilde{q}}\) obviously implies \(F(P^{\prime })\) \(p_{i}^{K}\) F(P) for all \(i\in S^{ab}(\tau )\). The same conclusion holds if either \(\{a,b\}\subseteq F(P)^{C}\) or \(\{a,b\}\subseteq F(P^{\prime })^{C}\). This shows that \(\{\theta _{maj},F\}\) is not K-SWP, which completes the proof of Theorem 3.

Now, suppose that F violates \(\overline{ WSIUA }\). Thus, one can find two weakly different profiles \(P,P^{\prime }\in {\mathcal {T}}^{K}\) such that \(P\setminus P^{\prime }\subseteq [F(P)^{C}]^{2}\cup [F(P^{\prime })^{C}]^{2}\) and \(F(P)\cap F(P^{\prime })=\emptyset\). As for above, Proposition 5 applies since \((P\setminus P^{\prime })\cap ([F(P^{\prime })\setminus\) \(F(P)]\otimes [F(P)\setminus\) \(F(P^{\prime })])=\emptyset\). Pick any \((a,b)\in P\setminus P^{\prime }\). If \(\{a,b\}\subseteq F(P^{\prime })^{C}\), the definition of p in cases 1.b and 2.b in the proof of Proposition 5 combined with the definition of \({\widetilde{q}}\) obviously implies \(F(P^{\prime })\) \(p_{i}^{N}\) F(P) for all \(i\in S^{ab}(\tau )\). The same conclusion holds if \(\{a,b\}\subseteq F(P)^{C}\). Thus, \(\{\theta _{maj},F\}\) is not N-SWP, which completes the proof of Theorem 5.

1.6.3 Proof of Theorems 7 and 9

First, we claim that \(\overline{ IUA }\) can equivalently be defined as follows: Given any two weakly different profiles \(P,P^{\prime }\in {\mathcal {T}}^{K}\) such that \(P\setminus P^{\prime }\subseteq [F(P^{\prime })^{C}]^{2}\), we have \(F(P^{\prime })=F(P)\). To see why, take an SCF F that satisfies \(\overline{ IUA }\) and two weakly different tournament profiles \(P,P^{\prime }\in {\mathcal {T}}^{K}\). By definition of \(\overline{ IUA }\), we can write

• \(P^{\prime }\setminus P\subseteq [F(P^{\prime })^{C}]^{2}\Rightarrow F(P^{\prime })=F(P)\) (1).

Since \(P,P^{\prime }\in {\mathcal {T}}^{K}\), we have \(\forall a,b\in A\), \((a,b)\in P^{\prime }\setminus P\Leftrightarrow (b,a)\in P\setminus P^{\prime }\). Thus \(P\setminus P^{\prime }\subseteq [F(P^{\prime })^{C}]^{2}\Leftrightarrow P^{\prime }\setminus P\subseteq [F(P^{\prime })^{C}]^{2}\). By (1), we get \(F(P^{\prime })=F(P)\), which proves the claim.

To show Theorem 7, take a majority constitution \(\{\theta _{maj},F\}\) where F violates \(\overline{ IUA }\) and/or \(\overline{ IEA }\). Hence, there exist two weakly different profiles \(P,P^{\prime }\in {\mathcal {T}}^{K}\) such that \(F(P)\ne F(P^{\prime })\) while \(P\setminus P^{\prime }\subseteq [F(P^{\prime })^{C}]^{2}\cup [F(P^{\prime })\cap F(P)]^{2}\cup ([F(P)\cap F(P^{\prime })]\otimes [F(P)\cup F(P^{\prime })]^{C})\). Again, we have \((P\setminus P^{\prime })\cap ([F(P^{\prime })\setminus\) \(F(P)]\otimes [F(P)\setminus\) \(F(P^{\prime })])\) \(=\emptyset\), so Proposition 5 applies. Using the construction of p together with the definition of \({\widetilde{q}}\), it is straightforward to check that \(\forall\) \((a,b)\in P\setminus P^{\prime }\), \(\forall h\in {\mathcal {D}}_{ab}\), \(\forall i\in S^{ab}(\tau )\), we have \(F(P^{\prime })\) \(p_{i}^{F}\) F(P). Thus \(\{\theta _{maj},F\}\) is not F-SWP, which shows Theorem 7.

This shows that \(\overline{ IUA }\) and \(\overline{ IEA }\) are also necessary for \(\{\theta _{maj},F\}\) to be G-SWP. Suppose F violates \(\overline{ SDP }\) while satisfying \(\overline{ IUA }\) and \(\overline{ IEA }\). Thus, one can find two weakly different profiles \(P,P^{\prime }\in {\mathcal {T}}^{K}\) such that neither \(F(P)\subseteq F(P^{\prime })\) nor \(F(P^{\prime })\subseteq F(P)\) while \(P\setminus P^{\prime }\cap ([F(P)\setminus F(P^{\prime })]\otimes [F(P^{\prime })\setminus F(P^{\prime })])=\emptyset\), so Proposition 5 applies. Using again the construction of p together with the definition of \({\widetilde{q}}\), it is easily checked that \(\forall\) \((a,b)\in P\setminus P^{\prime }\), \(\forall i\in S^{ab}(\tau )\). Thus \(\{\theta _{maj},F\}\) is not G-SWP, which completes the proof of Theorem 9.

1.7 Proof of Proposition 3

Observe that at any tournament T,

1. (1)

   For all \(1\le y<z\le Z\), \(\forall a\in A_{T}^{y}\), \(\forall b\in A^{z}\) , aTb,

2. (2)

   \(\forall a,b\in A^{z}\) with \(z\in \{1,\ldots ,Z\}\), \(\exists \{a_{1},\ldots ,a_{H}\}\subseteq A^{z}\) such that \((a,a_{1})\), \((a_{1},a_{2})\), ... , \((a_{H-1},a_{H})\), \((a_{H},b)\) \(\in T\).

Observe that by (1), \(\forall a\in {\widetilde{S}}(T)\), \(\forall b\notin {\widetilde{S}}(T)\), aTb.

In the rest of the proof, for profiles \(P,P^{\prime }\in {\mathcal {T}}^{K}\), we will refer to their corresponding tournaments \(T_{P}\) and \(T_{P^{\prime }}\) respectively by T and \(T^{\prime }\).

We claim that \({\widetilde{F}}\) violates \(\overline{ IUA }\). To see why, take a profile P for which \(A_{T}^{1}=\{a_{1},a_{2},a_{3}\}\), \(A_{T}^{2}=\{b_{1},b_{2},b_{3}\}\), \(A_{T}^{3}=\{c\}\), and \(A_{T}^{4}=\{d_{1},d_{2},d_{3}\}\). Since \(Z=4\) and \(t_{Z}=3\), we have by definition \({\widetilde{F}}(P)=A^{1}\cup A^{2}=\{a_{1},a_{2},a_{3},b_{1},b_{2},b_{3}\}\). Pick any \(P^{\prime }\) such that \(T\setminus T^{\prime }=\{(c,d_{1})\}\). We get \(z_{T^{\prime }}=-\infty\), which implies \({\widetilde{F}}(P^{\prime })=\{a_{1},a_{2},a_{3}\}\ne {\widetilde{F}}(P)\). Since \(c,d_{1}\in {\widetilde{F}}(P)^{C}\), \(\overline{ IUA }\) does not hold.

Next, we claim that \({\widetilde{F}}\) satisfies \(\overline{ SDP }\). Suppose the contrary. Thus, \(\exists P,P^{\prime }\in {\mathcal {T}}^{K}\) with \({\widetilde{F}}(P)\setminus {\widetilde{F}}(P^{\prime })\ne \emptyset\), \({\widetilde{F}}(P^{\prime })\setminus {\widetilde{F}}(P)\ne \emptyset\), and \(P|_{[{\widetilde{F}}(P)\setminus {\widetilde{F}}(P^{\prime })]\otimes [{\widetilde{F}}(P^{\prime })\setminus {\widetilde{F}}(P)]}=P^{\prime }|_{[ {\widetilde{F}}(P)\setminus {\widetilde{F}}(P^{\prime })]\otimes [{\widetilde{F}}(P^{\prime })\setminus {\widetilde{F}}(P)]}\) (A). Pick \(a\in {\widetilde{F}}(P)\setminus {\widetilde{F}}(P^{\prime })\) and \(b\in {\widetilde{F}} (P^{\prime })\setminus {\widetilde{F}}(P)\). By (1), aTb and \(bT^{\prime }a\), which contradicts (A).

Finally, we claim that \({\widetilde{F}}\) satisfies \(\overline{ IEA }\). Suppose the contrary. Hence, \(\exists P,P^{\prime }\in {\mathcal {T}}^{K}\) with \({\widetilde{F}}(P)\ne {\widetilde{F}}(P^{\prime })\) and \(P\setminus P^{\prime }\subseteq [{\widetilde{F}}(P)\cap {\widetilde{F}}(P^{\prime })]^{2}\cup ([{\widetilde{F}}(P)\cap {\widetilde{F}}(P^{\prime })]\otimes [\widetilde{ F}(P)\cup {\widetilde{F}}(P^{\prime })]^{C})\) (B). Now, (B) implies (A), and by \(\overline{ SDP }\), either \({\widetilde{F}}(P)\subseteq {\widetilde{F}} (P^{\prime })\) or \({\widetilde{F}}(P^{\prime })\subseteq {\widetilde{F}}(P)\). Assume w.l.o.g. \({\widetilde{F}}(P^{\prime })\subseteq {\widetilde{F}}(P)\), since we also have \({\widetilde{F}}(P)\ne {\widetilde{F}}(P^{\prime })\), we get \({\widetilde{F}}(P^{\prime })\subset {\widetilde{F}}(P)\). Note that (B) reduces to \(P\setminus P^{\prime }\subseteq {\widetilde{F}}(P^{\prime })^{2}\cup [{\widetilde{F}}(P^{\prime })\otimes {\widetilde{F}}(P)^{C}]\). Furthermore, by (1), \(\forall a\in {\widetilde{F}}(P^{\prime })\), \(\forall b\in {\widetilde{F}}(P)^{C}\subset {\widetilde{F}}(P^{\prime })^{C}\), aTb and \(aT^{\prime }b\). Thus, we have \(P\setminus P^{\prime }\subseteq {\widetilde{F}} (P^{\prime })^{2}\) (C).

Suppose there exists \((a,b)\in [{\widetilde{F}}(P)\setminus \widetilde{F }(P^{\prime })]\times\) \({\widetilde{F}}(P^{\prime })\) with \(a,b\in A_{T}^{z}\) and \(z\in \{1,\ldots ,Z\}\). By (2) \(\exists \{a_{1},\ldots ,a_{H}\}\subseteq A_{T}^{z}\) such that \((a,a_{1})\), \((a_{1},a_{2})\), ... , \((a_{H-1},a_{H})\), \((a_{H},b)\) \(\in T\). By definition of \({\widetilde{F}}\), \(\{a_{1},\ldots ,a_{H}\}\subseteq {\widetilde{F}}(P)\). If \(a_{H}\notin {\widetilde{F}}(P^{\prime })\), then by (C), \((a_{H},b)\) \(\in T\) implies \((a_{H},b)\) \(\in T^{\prime }\). By (1), \(b\in {\widetilde{F}}(P^{\prime })\) implies \(b_{H}\in {\widetilde{F}}(P^{\prime })\). By the same argument, \(a_{H}\in {\widetilde{F}}(P^{\prime })\) implies \(a_{H-1}\in {\widetilde{F}} (P^{\prime })\), ..., \(a_{2}\in {\widetilde{F}}(P^{\prime })\) implies \(a_{1}\in {\widetilde{F}}(P^{\prime })\), and \(a_{1}\in {\widetilde{F}}(P^{\prime })\) implies \(a\in {\widetilde{F}}(P^{\prime })\), a contradiction.

Thus, no element a of \({\widetilde{F}}(P)\setminus {\widetilde{F}}(P^{\prime })\) and b of \({\widetilde{F}}(P^{\prime })\) belong to the same \(A_{T}^{z}\), where \(z\in \{1,\ldots ,Z\}\). By definition of \({\widetilde{F}}\), we must have \(z_{T}>2\). Note that by \({\widetilde{F}}(P^{\prime })\subset {\widetilde{F}}(P)\) , (1) applied to \(T^{\prime }\) and T, and (C), \(\forall b\in {\widetilde{F}} (P^{\prime })\), \(\forall a\in {\widetilde{F}}(P)\setminus {\widetilde{F}} (P^{\prime })\), \(\forall c\in {\widetilde{F}}(P)^{C}\), we have (b, a), (b, c) , \((a,c)\in T\cap T^{\prime }\) (D). Thus, \({\widetilde{F}}(P^{\prime })\subset {\widetilde{F}}(P)\) implies \(z^{*}<z_{T}-1\) where \(z^{*}\) is such that \(\cup _{z=1}^{z^{*}}A_{T}^{z}={\widetilde{F}}(P^{\prime })\) and \(\cup _{z=z^{*}}^{z_{T}-1}A_{T}^{z}={\widetilde{F}}(P)\setminus {\widetilde{F}} (P^{\prime })\) and \(A_{T}^{z_{T}}=\{a\}\in {\widetilde{F}}(P)^{C}\).

To conclude, consider \(T^{\prime }\). Since \(z_{T}>2\), we get from \({\widetilde{F}}(P^{\prime })\subset {\widetilde{F}}(P)\) together with (C) that \(z_{T^{\prime }}\ne -\infty\). By definition of \({\widetilde{F}}\), there exists \(a^{*}\in {\widetilde{F}}(P^{\prime })^{C}\) such that \(A_{T^{\prime }}^{z_{T^{\prime }}}=\{a^{*}\}\). Moreover, if \(a^{*}\in {\widetilde{F}} (P)^{C}\), by (D) we get \({\widetilde{F}}(P)\subseteq {\widetilde{F}}(P^{\prime })\), which is impossible. Thus, \(a^{*}\in {\widetilde{F}}(P)\setminus {\widetilde{F}}(P^{\prime })\). By (C), it follows that \(\{a^{*}\}\) forms a cycle in T, in contradiction with the definition of \(z_{T}\).

1.8 Proof of Proposition 4

Let \(A=\{a,b,c,d\}\). The set of 64 possible tournaments can be partitioned into 4 non-empty sets \({\mathcal {T}}_{1}\), \({\mathcal {T}}_{2}\), \({\mathcal {T}}_{3}\) , \({\mathcal {T}}_{4}\) where:

• \({\mathcal {T}}_{1}\) contains the 24 linear orders over A,

• \({\mathcal {T}}_{2}\) contains the 8 tournaments T having a Condorcet winner \(a^{*}\) and such that \(TC(T\mid _{A\setminus \{a^{*}\}})=A\setminus \{a^{*}\}\),

• \({\mathcal {T}}_{3}\) contains the 8 tournaments T such that \(|TC(T)|=3\),

• \({\mathcal {T}}_{4}\) contains the 24 tournaments obtained from a linear order [xyzt] by reversing the edge (x, t). We write these tournaments as [xyztx].

Since UC is a tournament solution, F obviously satisfies CC. By definition of UC, we have \(\forall T\in {\mathcal {T}}_{1}\cup {\mathcal {T}} _{2}\), \(UC(T)=\{a^{*}\}\), where \(a^{*}\) is the Condorcet winner of T. For any \(T\in {\mathcal {T}}_{3}\), \(UC(T)=TC(T)\). For any \(T=xyztx\in {\mathcal {T}}_{4}\) with \(x,y,z,t\in A\), \(UC(T)=\{x,y,t\}\).

First, we argue that F satisfies \(\overline{ IUA }\). Indeed, pick any two profiles \(P,P^{\prime }\) with \(T=T_{P}\) , \(T^{\prime }=T_{P^{\prime }}\), and \(T\setminus T^{\prime }\subseteq [UC(T)^{C}]^{2}\). If \(T\in {\mathcal {T}}_{1}\cup {\mathcal {T}}_{2}\), the Condorcet winner of T remains as such for \(T^{\prime }\). By CC, \(F(P)=F(P^{\prime })\). If \(T\in {\mathcal {T}}_{3}\cup {\mathcal {T}}_{4}\), \(\left| UC(T)^{C}\right| =1\) implies that \(\overline{ IUA }\) is trivially satisfied.

Next, we claim that F satisfies \(\overline{ IEA }\). Again, pick any two profiles \(P,P^{\prime }\) with \(T=T_{P}\) , \(T^{\prime }=T_{P^{\prime }}\) . We have 5 possible cases:

Case 1: Either \(T\in {\mathcal {T}}_{1}\), \(T^{\prime }\in {\mathcal {T}}_{1}\cup {\mathcal {T}}_{2}\), or \(T,T^{\prime }\in {\mathcal {T}}_{2}\).

Obviously, either \(UC(T)=UC(T^{\prime })\) or \(UC(T)\cap UC(T^{\prime })=\emptyset\). Hence, IEA is clearly satisfied.

Case 2: \(T\in {\mathcal {T}}_{1}\cup {\mathcal {T}}_{2}\) and \(T^{\prime }\in {\mathcal {T}}_{3}\cup {\mathcal {T}}_{4}\).

We claim that \(\overline{ IEA }\) is trivially satisfied. Indeed, either \(UC(T)\cap UC(T^{\prime })=\emptyset\), or \(UC(T)=\{x\}\) and \(UC(T^{\prime })=\{x,y,z\}\), where x is a Condorcet winner of P. In the former case, \(\overline{ IEA }\) is silent. In the latter case, we can assume w.l.o.g. that \((x,y)\in T\setminus T^{\prime }\). Since \(x\in UC(T)\cap UC(T^{\prime })\) and \(y\in UC(T^{\prime })\setminus UC(T)\), \(\overline{ IEA }\) is silent again.

Case 3: \(T,T^{\prime }\in {\mathcal {T}}_{3}\).

Either \(UC(T)=UC(T^{\prime })\) or \(UC(T)=\{x,y,z\}\) and \(UC(T^{\prime })=\{y,z,t\}\), where x is the Condorcet loser of \(P^{\prime }\), while \((x,y)\in T\) or \((x,z)\in T\). In the former situation, \(\overline{ IEA }\) obviously holds. In the latter situation, \(\overline{ IEA }\) is silent since \(x\in UC(T)\setminus UC(T^{\prime })\) and \(y,z\in UC(T)\cap UC(T^{\prime })\).

Case 4: \(T\in {\mathcal {T}}_{3}\), \(T^{\prime }\in {\mathcal {T}}_{4}\).

This case is very similar to the previous one. Either \(UC(T)=UC(T^{\prime })\) or \(UC(T)=\{x,y,z\}\) and \(UC(T^{\prime })=\{y,z,t\}\), where t is the Condorcet loser of P, while \((t,y)\in T^{\prime }\) or \((t,z)\in T^{\prime }\). In the former situation, \(\overline{ IEA }\) obviously holds. In the latter situation, \(\overline{ IEA }\) is silent since \(t\in UC(T^{\prime })\setminus UC(T)\) and \(y,z\in UC(T)\cap UC(T^{\prime })\).

Case 5: \(T,T^{\prime }\in {\mathcal {T}}_{4}\).

Suppose that \(T=[abcda]\) and \(T^{\prime }=[cbadc]\). By definition of F, \(F(P)=\{a,b,d\}\) and \(F(P^{\prime })=\{a,b,c\}\) where P and \(P^{\prime }\) are two profiles with \(T=T_{P}\) and \(T^{\prime }=T_{P^{\prime }}\). Observe that \(a\in UC(T^{\prime })\cap UC(T)\) and \(c\in UC(T^{\prime })\setminus UC(T)\). Since \((a,c)\in T\setminus T^{\prime }\), \(\overline{ IEA }\) trivially holds. It is rather straightforward to check that the same argument applies to all possible cases.

This shows that F satisfies \(\overline{ IEA }\). Finally, F violates \(\overline{ SDP }\). To see why, let \(T=[abcda]\) and \(T^{\prime }=[dabcd]\). We have \(T\setminus T^{\prime }=\{(b,d)\}\), \(UC(T)=\{a,b,d\}\) and \(UC(T^{\prime })=\{a,c,d\}\). Since \(UC(T)\setminus UC(T^{\prime })=\{b\}\) and \(UC(T^{\prime })\setminus UC(T)=\{c\}\) while \(T|_{\{b,c\}}=T^{\prime }|_{\{b,c\}}\), and since neither \(UC(T)\subseteq UC(T^{\prime })\) nor \(UC(T^{\prime })\subseteq UC(T)\), the conclusion follows.

1.9 Proof of Theorem 10

Take any positional constitution \(\{\theta ,F\}\) and consider voting situations with \(m=3\). Denote by s (resp. \({\overline{s}}\)) the score vector associated with \(\theta\) (resp. with F). Clearly, scores can be normalized so as to have \(s_{3}={\overline{s}}_{3}=0\). The proof investigates several cases:

Case 1: \(s_{2}=0\).

Case 1.1: \(s_{2}=0\), \({\overline{s}}_{1}>{\overline{s}}_{2}\).

Consider the voting situation \(\{p,D\}\) where \(D=\{D_{1},\ldots ,D_{5}\}\) is defined by \(D_{1}=\{1,2\}\), \(D_{2}=\{3,4\}\), \(D_{3}=\{5,6\}\), \(D_{4}=\{7,8\}\) , \(D_{5}=\{9,10\}\), and where the voter profile is

As \(s_{2}=0\), the district profile is

Clearly, as \({\overline{s}}_{1}>\) \({\overline{s}}_{2}\), one gets \(F(P)=\{a\}\). Now, if voter 2 swaps with 3 and voter 6 swaps with 7, the resulting district profile is

Finally, \({\overline{s}}_{1}>{\overline{s}}_{2}\) implies \(F(P^{\tau })=\{b\}\). Since b \(p_{i}\) a for all \(i\in \{2,3,6,7\}\), \(\{\theta ,F\}\) is not N-SWP.

Case 1.2: \(s_{2}=0\), \({\overline{s}}_{1}={\overline{s}}_{2}\).

Consider the voting situation \(\{p,D\}\) where \(D=\{D_{1},D_{2},D_{3}\}\) is defined by \(D_{1}=\{1,\ldots ,7\}\), \(D_{2}=\{8,\ldots ,13\}\), \(D_{3}=\{14,\ldots ,19\}\), and where the voter profile is

As \(s_{2}=0\), the district profile is

Now, \({\overline{s}}_{1}=\) \({\overline{s}}_{2}\), one gets \(F(P)=\{c\}\). If voter 8 swaps with 15 and voter 9 swaps with 16, the resulting district profile is

Finally, \({\overline{s}}_{1}=\) \({\overline{s}}_{2}\) implies \(F(P^{\tau })=\{a\}\) . Since a \(p_{i}\) c for all \(i\in \{8,9,15,16\}\), \(\{\theta ,F\}\) is not N-SWP.

Case 2: \(s_{2}>0\).

Case 2.1: \(s_{2}>0\), \(2{\overline{s}}_{2}>{\overline{s}}_{1}\).

Consider the voting situation \(\{p,D\}\) where \(D_{1}=\{1,2,3\}\), \(D_{2}=\{4,5,6\}\), \(D_{3}=\{7,8,9\}\), \(D_{4}=\{10,11,12\}\), \(D_{5}=\{13,14,15\}\), and where voters’ preferences are given by

Since \(s_{2}>0\), the district profile is

As \(2{\overline{s}}_{2}>{\overline{s}}_{1}\), one has \({\overline{s}}(a,P)=3 {\overline{s}}_{1}+2{\overline{s}}_{2}>{\overline{s}}(b,P)=4{\overline{s}}_{1}> {\overline{s}}(c,P)=2{\overline{s}}_{1}+{\overline{s}}_{2}\). Thus, \(F(P)=\{a\}\). If voter 3 swaps with 4 and voter 9 swaps with 10, the district profile becomes

Check that \(2{\overline{s}}_{2}>{\overline{s}}_{1}\) implies \(F(P^{\tau })=\{b\}\) . Since b \(p_{i}\) a for \(i\in \{3,4,9,10\}\), \(\{\theta ,F\}\) is not N-SWP.

Case 2.2: \(s_{2}>0\), \({\overline{s}}_{1}\ge 2{\overline{s}}_{2}>0\).

Case 2.2.1: \(s_{1}=s_{2}\), \({\overline{s}}_{1}\ge 2{\overline{s}} _{2}>0\).

Consider apportionment \(D=(D_{1},\ldots ,D_{5})\) with \(\left| D_{1}\right| =\left| D_{2}\right| =\left| D_{3}\right| =6\), and \(\left| D_{4}\right| =\left| D_{5}\right| =7\). Let \(D_{k}=\{1^{k},\ldots ,6^{k}\}\), for \(k\in \{1,2,3\}\), and \(D_{k}=\{1^{k},\ldots ,7^{k}\}\), for \(k\in \{4,5\}\). Preferences are defined by

Since \(s_{1}=s_{2}\), the district profile for this voting situation is

Now, replicate districts \(D_{3},D_{4},D_{5}\) exactly \(\alpha >1\) times, and denote the resulting district profile by \({\overline{P}}\). Since \({\overline{s}} _{1}\ge 2{\overline{s}}_{2}>0\), one gets \({\overline{s}}(a,{\overline{P}} )=(2\alpha +2){\overline{s}}_{1}>{\overline{s}}(b,{\overline{P}})=\alpha \overline{ s}_{1}+2\alpha {\overline{s}}_{2}>{\overline{s}}(c,{\overline{P}})=(2\alpha +2) {\overline{s}}_{2}\). Thus, \(F({\overline{P}})=\{a\}\). Considering again profile P, if voters with respective preferences \(p_{4^{4}}\) and \(p_{5^{4}}\) in each replica of \(D_{4}\) swap with two voters in \(\{p_{1^{5}},\ldots ,p_{6^{5}}\}\) in the corresponding replica of \(D_{5}\), the district profile becomes

It follows that after replication, profile \({\overline{P}}^{\tau }\) is such that \({\overline{s}}(a,{\overline{P}}^{\tau })=(\alpha +2){\overline{s}} _{1}+\alpha {\overline{s}}_{2}\), \({\overline{s}}(b,{\overline{P}}^{\tau })=\alpha {\overline{s}}_{1}+2\alpha {\overline{s}}_{2}\), and \({\overline{s}}(c,{\overline{P}} ^{\tau })=\alpha {\overline{s}}_{1}+(\alpha +2){\overline{s}}_{2}\). Clearly, since \({\overline{s}}_{2}>0\), \(\alpha\) can be chosen large enough in order to have \({\overline{s}}(b,{\overline{P}}^{\tau })>{\overline{s}}(a,{\overline{P}}^{\tau })>{\overline{s}}(c,{\overline{P}}^{\tau })\). Thus, \(F({\overline{P}}^{\tau })=\{b\}\). Since b \(p_{i}\) a for all voters in \(S(\tau )\), \(\{\theta ,F\}\) is not N-SWP.

Case 2.2.2: \(s_{1}>s_{2}>0\), \({\overline{s}}_{1}\ge 2{\overline{s}} _{2}>0\).

Consider apportionment \(D=(D_{1},\ldots ,D_{5})\) with \(\left| D_{1}\right| =\left| D_{2}\right| =\left| D_{3}\right| =\left| D_{4}\right| =4\), and \(\left| D_{5}\right| =5\). Let \(D_{4}=\{1,2,3,4\}\). Preferences are defined by

By \(s_{1}>s_{2}\), the district profile is

Now, replicate districts \(D_{2},D_{3},D_{4},D_{5}\) exactly \(\alpha >1\) times, and let \({\widetilde{P}}\) stand for the associated district profile. Check that \({\overline{s}}(a,{\widetilde{P}}^{\tau })=(3\alpha +1){\overline{s}} _{1}\), \({\overline{s}}(b,{\widetilde{P}}^{\tau })=2\alpha {\overline{s}} _{1}+2\alpha {\overline{s}}_{2}\), and \({\overline{s}}(c,{\widetilde{P}}^{\tau })=(2\alpha +1){\overline{s}}_{2}\). Since \({\overline{s}}_{1}\ge 2{\overline{s}} _{2}\), one has \({\overline{s}}(a,{\widetilde{P}}^{\tau })>{\overline{s}}(b, {\widetilde{P}}^{\tau })>{\overline{s}}(c,{\widetilde{P}}^{\tau })\). Thus, \(F( {\widetilde{P}})=\{a\}\). Suppose that voters with preferences \(p_{3},p_{4}\) in each replica of \(D_{4}\) swap with two voters in the corresponding replica of \(D_{5}\). The resulting district profile becomes

Check that \({\overline{s}}(a,{\widetilde{P}}^{\tau })=(2\alpha +1){\overline{s}} _{1}+\alpha {\overline{s}}_{2}\), \({\overline{s}}(b,{\widetilde{P}}^{\tau })=2\alpha {\overline{s}}_{1}+2\alpha {\overline{s}}_{2}\), and \({\overline{s}}(c, {\widetilde{P}}^{\tau })=(\alpha +1){\overline{s}}_{2}\). Clearly, \(\alpha\) can be chosen large enough to have \({\overline{s}}(b,{\widetilde{P}}^{\tau })> {\overline{s}}(a,{\widetilde{P}}^{\tau })>{\overline{s}}(c,{\widetilde{P}}^{\tau })\) . Thus, \(F({\widetilde{P}}^{\tau })=\{b\}\). Since b \(p_{i}\) a for all voters in \(S(\tau )\), \(\{\theta ,F\}\) is not N-SWP.

Case 2.3: \(s_{2}>0\), \({\overline{s}}_{2}=0\).

Consider apportionment \(D=(D_{1},D_{2},D_{3})\) with \(\left| D_{1}\right| =\left| D_{2}\right| =6\) and \(\left| D_{3}\right| =6\). Using the same notations as in case 2.2.1, preferences are defined by

Check that the district profile for this voting situation is

Since \({\overline{s}}_{2}=0\), \(F(P)=\{a\}\). Suppose that voters \(3^{1}\) and \(4^{1}\) swap with voters \(3^{3}\) and \(4^{3}\). Using \(s_{2}>0\), the form of the resulting district profile looks as below

Since \({\overline{s}}_{2}=0\), then \(F(P^{\tau })=\{b\}\). Since b \(p_{i}\) a for \(i\in \{3^{1},4^{1},3^{3},4^{3}\}\), \(\{\theta ,F\}\) is not N-SWP. This completes the proof.

Finally, observe that in all voting situations considered above, outcomes are singletons, and the difference between any two district sizes is at most one.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions