## Swipe to navigate through the articles of this issue

25-01-2023 | Original Paper

# Vote swapping in irresolute two-tier voting procedures

Authors: Hayrullah Dindar, Jean Lainé

Published in: Social Choice and Welfare

## Abstract

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.

### Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

• über 69.000 Bücher
• über 500 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Nachhaltigkeit
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Maschinenbau + Werkstoffe
• Versicherung + Risiko

Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

### Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

• über 58.000 Bücher
• über 300 Zeitschriften

aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Versicherung + Risiko

Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

Appendix
Available only for authorised users
Footnotes
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 ab 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.

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 357, 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.

Literature
Bandyopadhyay T (1982) Threats, counter-threats and strategic manipulation for non-binary group decision rules. Math Soc Sci 2:145–155 CrossRef
Bandyopadhyay T (1983) Multi-valued decision rules and coalitional non-manipulability. Econ Lett 13:37–44 CrossRef
Barberà S (1977a) Manipulation of social decision functions. J Econ Theory 15:266–278 CrossRef
Barberà S (1977b) The manipulation of social choice mechanisms that do not leave “too much’’ to chance. Econometrica 45:1573–1588 CrossRef
Barberà S (2010) Strategy-proof social choice. In: Arrow K, Sen AK, Suzumura K (eds) Handbook of social choice and welfare, vol 2. Elsevier, Amsterdam, pp 731–832 CrossRef
Barberà S, Dutta B, Sen A (2001) Strategy-proof social choice correspondences. J Econ Theory 101:374–394 CrossRef
Barberà S, Bossert W, Pattanaik PK (2004) Ranking sets of objects. In: Barberà S, Hammond P, Seidl C (eds) Handbook of utility theory, vol 2. Springer, Boston, pp 893–977 CrossRef
Bervoets S, Merlin V (2012) Gerrymander-proof representative democracies. Internat J Game Theory 41:473–488 CrossRef
Bervoets S, Merlin V (2016) On avoiding vote swapping. Soc Choice Welf 46:495–509 CrossRef
Botan S, Endriss U (2021) Preserving Condorcet winners under strategic manipulation. In: Proceedings of the AAAI Conference on Artificial Intelligence 35(6):5202–5210
Brandt F (2011) Group strategy-proof irresolute social choice functions. In: Proceedings of the 22nd International Joint Conference on artificial intelligence (IJCAI), pp 79–84
Brandt F (2015) Set-monotonicity implies Kelly-strategy proofness. Soc Choice Welf 45:793–804 CrossRef
Brandt F, Brill M (2011) Necessary and sufficient conditions for the strategyproofness of irresolute social choice functions. In: Proceedings of the 13th conference on theoretical aspects of rationality and knowledge (TARK). ACM Press, pp 136–142
Brandt F, Lederer P (2022) Characterizing the top cycle via strategyproofness. Theoret Econ ( forthcoming)
Brandt F, Saile C, Stricker C (2021) Voting with ties: strong impossibilities via SAT solving. In: Proceedings of the 17th International Conference on autonomous agents and multiagent systems (AAMAS), pp 1285–1293
Brandt F, Bullinger M, Lederer P (2022) On the indecisiveness of Kelly-strategy-proof social choice functions. J Artif Intell Res 73:1093–1130 CrossRef
Chambers CP (2008) Consistent representative democracy. Games Econ Behav 62:348–363 CrossRef
Chambers CP (2009) An axiomatic theory of political representation. J Econ Theory 144:375–389 CrossRef
Ching S, Zhou L (2002) Multi-valued strategy-proof social choice rules. Soc Choice Welf 19:569–580 CrossRef
Coffman KB (2016) Representative democracy and the implementation of majority-preferred alternatives. Soc Choice Welf 46:477–494 CrossRef
Coppock A (2018) A field experimental test of vote swapping. Unpublished manuscript
Dindar H, Lainé J (2017) Manipulation of single-winner large elections by vote pairing. Econ Lett 161:105–107 CrossRef
Dindar H, Laffond G, Lainé J (2015) Vote swapping in representative democracy. In: Kamiński B, Kersten G, Szapiro T (eds) Outlooks and insights on group decision and negotiation, vol 218. Springer, Cham, pp 227–239 CrossRef
Dindar H, Laffond G, Lainé J (2017) The Strong referendum paradox. Qual Quant 51:1707–1731 CrossRef
Duggan J, Schwartz T (2000) Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized. Soc Choice Welf 17:85–93 CrossRef
Elkind E, Piotr Faliszewski P, Piotr Skowron P, Arkadii Slinko A (2017) Properties of multiwinner voting rules. Soc Choice Welf 48:599–632 CrossRef
Faliszewski P, Skowron P, Slinko A, Nimrod Talmon N (2017) Multiwinner voting: a new challenge for social choice theory. In: Endriss U (ed) Trends in computational social choice. AI Access, pp 27–47
Feldman A (1979a) Manipulation and the Pareto rule. J Econ Theory 21:473–482 CrossRef
Feldman A (1979b) Nonmanipulable multi-valued social decision functions. Public Choice 34:177–188 CrossRef
Fishburn PC (1972) Even-chance lotteries in social choice theory. Theor Decis 3:18–40 CrossRef
Gärdenfors P (1976) Manipulation of social choice functions. J Econ Theory 13:217–228 CrossRef
Gibbard A (1977) Manipulation of schemes that mix voting with chance. Econometrica 45(665):681
Hartvigsen D (2006) Vote trading in public elections. Math Soc Sci 52:31–48 CrossRef
Hartvigsen D (2008) The manipulation of voting systems. J Bus Ethics 80:13–21 CrossRef
Kelly JS (1977) Strategy-proofness and social choice functions without single-valuedness. Econometrica 45:439–446 CrossRef
Lacy D, Niou EMS (2000) A Problem with referendums. J Theor Polit 12:5–31 CrossRef
Laffond G, Lainé J (2000) Representation in majority tournaments. Math Soc Sci 39:35–53 CrossRef
Laslier JF (1997) Tournament solutions and majority voting. In: Studies in economic theory, vol 7. Springer Verlag, Berlin
Mac Garvey D (1953) A theorem on the construction of voting paradoxes. Econometrica 21:608–610 CrossRef
Mac Intyre I, Pattanaik PK (1981) Strategic voting under minimally binary group decision functions. J Econ Theory 25:338–352 CrossRef
Nehring K (2000) Monotonicity implies generalized strategy-proofness for correspondences. Soc Choice Welf 17:367–375 CrossRef
Nurmi H (1998) Voting paradoxes and referenda. Soc Choice Welf 15:333–350 CrossRef
Nurmi H (1999) Voting paradoxes and how to deal with them. Springer Verlag, Berlin CrossRef
Sato S (2008) On strategy-proof social choice correspondences. Soc Choice Welfare 31:331–343 CrossRef
Umezawa M (2009) Coalitionally strategy-proof social choice correspondences and the Pareto rule. Soc Choice Welfare 33:151–158 CrossRef
Title
Vote swapping in irresolute two-tier voting procedures
Authors
Hayrullah Dindar
Jean Lainé
Publication date
25-01-2023
Publisher
Springer Berlin Heidelberg
Published in
Social Choice and Welfare
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-022-01445-z