Top

Social Choice and Welfare

Published in:

25-01-2023 | Original Paper

Vote swapping in irresolute two-tier voting procedures

Authors: Hayrullah Dindar, Jean Lainé

Published in: Social Choice and Welfare | Issue 2/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

next article Mechanism design with model specification

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

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.

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).

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.

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.

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”.

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

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

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.

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.

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

(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.

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.

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}\).

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

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\).

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

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.

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

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.

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

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.

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.

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

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

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

\({\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\}\).

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.

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.

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.

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

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.

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.

Bandyopadhyay T (1982) Threats, counter-threats and strategic manipulation for non-binary group decision rules. Math Soc Sci 2:145–155CrossRef

Bandyopadhyay T (1983) Multi-valued decision rules and coalitional non-manipulability. Econ Lett 13:37–44CrossRef

Barberà S (1977a) Manipulation of social decision functions. J Econ Theory 15:266–278CrossRef

Barberà S (1977b) The manipulation of social choice mechanisms that do not leave “too much’’ to chance. Econometrica 45:1573–1588CrossRef

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–832CrossRef

Barberà S, Dutta B, Sen A (2001) Strategy-proof social choice correspondences. J Econ Theory 101:374–394CrossRef

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–977CrossRef

Bervoets S, Merlin V (2012) Gerrymander-proof representative democracies. Internat J Game Theory 41:473–488CrossRef

Bervoets S, Merlin V (2016) On avoiding vote swapping. Soc Choice Welf 46:495–509CrossRef

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–804CrossRef

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–1130CrossRef

Chambers CP (2008) Consistent representative democracy. Games Econ Behav 62:348–363CrossRef

Chambers CP (2009) An axiomatic theory of political representation. J Econ Theory 144:375–389CrossRef

Ching S, Zhou L (2002) Multi-valued strategy-proof social choice rules. Soc Choice Welf 19:569–580CrossRef

Coffman KB (2016) Representative democracy and the implementation of majority-preferred alternatives. Soc Choice Welf 46:477–494CrossRef

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–107CrossRef

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–239CrossRef

Dindar H, Laffond G, Lainé J (2017) The Strong referendum paradox. Qual Quant 51:1707–1731CrossRef

Duggan J, Schwartz T (2000) Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized. Soc Choice Welf 17:85–93CrossRef

Elkind E, Piotr Faliszewski P, Piotr Skowron P, Arkadii Slinko A (2017) Properties of multiwinner voting rules. Soc Choice Welf 48:599–632CrossRef

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–482CrossRef

Feldman A (1979b) Nonmanipulable multi-valued social decision functions. Public Choice 34:177–188CrossRef

Fishburn PC (1972) Even-chance lotteries in social choice theory. Theor Decis 3:18–40CrossRef

Gärdenfors P (1976) Manipulation of social choice functions. J Econ Theory 13:217–228CrossRef

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–48CrossRef

Hartvigsen D (2008) The manipulation of voting systems. J Bus Ethics 80:13–21CrossRef

Kelly JS (1977) Strategy-proofness and social choice functions without single-valuedness. Econometrica 45:439–446CrossRef

Lacy D, Niou EMS (2000) A Problem with referendums. J Theor Polit 12:5–31CrossRef

Laffond G, Lainé J (2000) Representation in majority tournaments. Math Soc Sci 39:35–53CrossRef

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–610CrossRef

Mac Intyre I, Pattanaik PK (1981) Strategic voting under minimally binary group decision functions. J Econ Theory 25:338–352CrossRef

Nehring K (2000) Monotonicity implies generalized strategy-proofness for correspondences. Soc Choice Welf 17:367–375CrossRef

Nurmi H (1998) Voting paradoxes and referenda. Soc Choice Welf 15:333–350CrossRef

Nurmi H (1999) Voting paradoxes and how to deal with them. Springer Verlag, BerlinCrossRef

Sato S (2008) On strategy-proof social choice correspondences. Soc Choice Welfare 31:331–343CrossRef

Umezawa M (2009) Coalitionally strategy-proof social choice correspondences and the Pareto rule. Soc Choice Welfare 33:151–158CrossRef

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 / Issue 2/2023
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-022-01445-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2023

Moral awareness polarizes people’s fairness judgments

Centrality measures in networks

Unanimity and local incentive compatibility in sparsely connected domains

Forward induction and market entry with an endogenous outside option

Taxonomy of powerful voters and manipulation in the framework of social choice functions

Positional preferences and efficiency in a dynamic economy