An individual manipulability of positional voting rules

Aleskerov, Fuad; Karabekyan, Daniel; Sanver, M. Remzi; Yakuba, Vyacheslav Article An individual manipulability of positional voting rules SERIEs - Journal of the Spanish Economic Association Provided in Cooperation with: Spanish Economic Association Suggested Citation: Aleskerov, Fuad; Karabekyan, Daniel; Sanver, M. Remzi; Yakuba, Vyacheslav (2011) : An individual manipulability of positional voting rules, SERIEs - Journal of the Spanish Economic Association, ISSN 1869-4195, Springer, Heidelberg, Vol. 2, Iss. 4, pp. 431-446, https://doi.org/10.1007/s13209-011-0050-y This Version is available at: https://hdl.handle.net/10419/77764 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/2.0/ SERIEs (2011) 2:431–446 DOI 10.1007/s13209-011-0050-y ORIGINAL ARTICLE An individual manipulability of positional voting rules Fuad Aleskerov ·Daniel Karabekyan · M. Remzi Sanver ·Vyacheslav Yakuba Received: 17 February 2011 / Accepted: 28 February 2011 / Published online: 15 March 2011 © The Author(s) 2011. This article is published with open access at SpringerLink.com Abstract We study a problem of individual manipulation in an impartial culture (IC) framework using computer modeling. We estimate the degree of manipulability of ten positional voting rules in the case of multiple choice for 3 and 4 alternatives. Keywords Manipulability ·Positional voting rules ·Multiple choice · Extended preferences JEL Classification D7 1 Introduction Gibbard (1973) and Satterthwaite (1975) showed that for at least 3 alternatives and any single-valued choice rule every non-dictatorial voting rule is individually manipulable. Later Duggan and Schwartz (2000) generalized this result for the case of multiple choice (when more than 1 alternative can be socially chosen). But if we know that F. Aleskerov (B )·D. Karabekyan National Research University Higher School of Economics, Moscow, Russia e-mail: [email protected] D. Karabekyan e-mail: [email protected] F. Aleskerov ·V. Yakuba Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia e-mail: [email protected] M. R. Sanver Istanbul Bilgi University, Istanbul, Turkey e-mail: [email protected] 123 432 SERIEs (2011) 2:431–446 every social choice rule is manipulable, how can we find the least manipulable one? A non-exhaustive list of papers studying to which extent known social choice rules are manipulable includes Chamberlin (1985), Nitzan (1985), Kelly (1993), Aleskerov and Kurbanov (1999), Smith (1999), Favardin and Lepelley (2006), Pritchard and Wilson (2007) and Aleskerov et al. (2011a,b). All those papers differ in main assumptions about profile probability distributions, a measure of manipulability, tie-breaking assumptions and sets of rules under study. There are several assumptions about individual preferences interdependence, but the most popular are impartial culture (IC) and impartial anonymous culture assumptions (IAC). Under the IC it is assumed that all individual orderings over alternatives are equally possible and individual preferences are independent. Thus, in this model one studies all profiles of preferences which are equally possible. Under IAC one looks only on those profiles which cannot be constructed one from another by changing the order of preferences in a given profile. Those profiles are called voting situations and under IAC it is assumed that these situations are equally possible. IAC is useful when one wants to find an exact formula for the number of manipulable voting situations (Gehrlein and Fishburn 1976). In this work we use Impartial Culture model in order to estimate the degree of manipulability of known voting rules. We use several measures of manipulability including most popular and most native one: the share of all manipulable profiles. This measure is used almost in all papers in this field. The next important feature is the way to deal with the possibility of multiple choice. For all rules there are some profiles where these rules give a tie as the result of voting. Most of the papers use alphabetical tie-breaking rules: in the case of tie first alternative in alphabetical order is chosen (for example, see Nitzan 1985,Aleskerov and Kurbanov 1999,Favardin and Lepelley 2006). The deficiency of this method is that it breaks symmetry between the alternatives because first alternatives in alphabetical order have more chances to be selected as the final outcome. Pritchard and Wilson (2007) use the random tie-breaking rule where in the case of a tie the final outcome is choosing randomly. In this case one can compare some sets of alternatives using some stochastic order. Voting rules in a more general framework of multiple choice were studied in Aleskerov et al. (2011a,b). In our research we use the same model and estimate the degree of manipulability of ten positional voting rules in the case of multiple choice. The structure of the paper is as follows. Section 2introduces the basic notation and concepts. Section 3presents the indices to measure the degree of manipulability of social choice rules and explains the computational scheme. Section 4presents the social choice rules under study. Section 5presents and discusses the results. 2 The framework Here we use the same notations as in Aleskerov and Kurbanov (1999) and almost the same model as in Aleskerov et al. (2011b). We consider a finite set Aconsisting of m alternatives, m=3,4. Let A=2A\{∅}denote the set of all non-empty subsets of A. Each agent from a finite set N={1,...,n},n>1, is assumed to have a preference Pi∈Lover alternatives where Lis the set of linear orders on A. 123 SERIEs (2011) 2:431–446 433 An ordered n-tuple of preferences Piis called a (preference) profile, P. A group decision is made by a social choice rule based on  Pand is considered to be an element of A. Thus we define a social choice rule as a mapping C:Ln→A. Every agent iis assumed to have an extended preference E Piover Awhich is induced by her preference Piover A. There are many preference extension axioms. One can find them, for example, in Barbera (1977), Gärdenfors (1976) and Kelly (1977). The detailed survey can be found in Barbera et al. (2004). In this paper we use the concepts of weak and strong manipulation. In the weak manipulation case we assume that not all possible sets can be compared by an agent. In this paper to describe the weak manipulation case we use Kelly’s Dominance Axiom (strong version) introduced in Kelly (1977) and presented according to Pattanaik (1978). Kelly’s DominanceAxiom(strong version) ∀i∈N and ∀ P, P∈Ln,if [(∀x∈C ( P)and ∀y∈C(−→ P)⇒xP iyorx=y)and (∃z∈C(−→ P)and ∃w∈C(−→ P)]⇒ zP iw)]then C(−→ P)EP iC(−→ P). For the strong manipulation case we use several concepts. First of all we consider two methods to obtain EP ifrom Pi, both of which are based on lexicographic comparisons used by Pattanaik (1978). The methods we consider are the leximax and leximin extensions, as described by Ozyurt and Sanver (2009). Under the leximax extension, two sets are compared according to their best elements. If they are the same, then the ordering is made according to the second best elements, etc. The elements according to which the sets are compared will disagree at some step—except possibly when one set is a subset of the other, in which case the smaller set is preferred. Formally, take any Pi∈Land any distinct X,Y∈A. Write X={x1,...,x|X|},Y={y1,...,y|Y|}and let, without loss of generality, ∀j∈{1,...,|X|−1},xj+1Pixjand ∀j∈{1,...,|Y|−1}yj+1Piyj. The leximax extended preference EP iis defined as follows 1. If |X|=|Y|, then XEP iYiff xhPiyhfor the smallest h∈{1,...,k}for which xh= yh. 2. If |X| =|Y|and ∃h∈{1,...,min{|X|,|Y|}} for which xh= yh, then XEP iY iff xhPiyhfor the smallest h∈{1,...,min{|X|,|Y|}} for which xh= yh. 3. If|X| =|Y|and ∀h∈{1,...,min{|X|,|Y|}} xh=yhthenXEP iYiff|X|<|Y|. The concept of the leximin extension is defined similarly so that it is based on the ordering of two sets according to a lexicographic comparison of their worst elements. Again the elements according to which the sets are compared will disagree at some step—except possibly when one set is a subset of the other, in which case the larger set ispreferred.So,givenany Pi∈Landanydistinct X,Y∈A,where X={x1,...,x|X|} and Y={y1,...,y|Y|}are such that ∀j∈{1,...,|X|−1}xj+1Pixjand ∀j∈{1,...,|Y|−1}yj+1Piyj, the leximin extended preference EP iis defined as follows 1. If |X|=|Y|, then XEP iYiff xhPiyhfor the greatest h∈{1,...,k}for which xh= yh. 2. If |X| =|Y|and ∃h∈{1,...,min{|X|,|Y|}} for which xh= yh, then XEP iY iff xhPiyhfor the smallest h∈{1,...,min{|X|,|Y|}} for which xh= yh. 123 434 SERIEs (2011) 2:431–446 3. If |X| =|Y|and xh=yh∀h∈{1,...,min{|X|,|Y|}} then XEP iYiff |X|>|Y|. We also introduce two probabilistic methods of preference extension. In contrast to lexicographic methods, these methods of preferences extension suggest that for a voter not only the presence of the alternative in a social choice is important, but the probability that this alternative would be the final outcome is important as well.Heretwoalgorithms areconsidered:an orderingisconstructedbased ontheprobability of the best alternative and an ordering is constructed based on the probability of the worst alternative. Ordering based on the probability of the best alternative is produced on the element-wise comparison of two social choices. If the best alternatives of two sets are the same, then the set, in which the probability that this alternative would be the final outcome is higher, is more preferable. In fact, it will be the smaller set. If the best alternatives are the same and have equal probability to be the final outcome, then next alternatives are compared in the same way. Example In the set {a,b,c}the probability that alternative awould be the final outcome equals 1 3(we assume that each alternative of the winning set has an equal probability to be chosen as the final outcome). In the set {a,c}this probability equals 1 2. In other words, if the preference over alternatives is aP ibP ic, in the extended preference based on the probability of the best alternative algorithm these sets are ordered as {a,c}EP i{a,b,c}. Let us describe this method formally. From the preferences Pi∈Lwe can get extended preferences EP ibased on the probability of the best alternative by the following algorithm. Two social choices X,Y∈Aare compared. Let us sort alternatives from each social choice from the most preferred to the least one, i.e., let X={x1,...,x|X|} and Y={y1,...,y|Y|}, where ∀j∈{1,...,|X|−1}xjPixj+1and ∀j∈ {1,...,|Y|−1}yjPiyj+1. We put •If x1Piy1, then XEP iY. •If x1=y1and |X|<|Y|, then XEP iY. •If x1=y1and |X|=|Y|=k, where k∈{2,...,m−1}, then XEP iYif and only if xhPiyhfor the least h∈{2,...,k}for which xh= yh. For example, for three alternatives and the preference relation aP ibP icover them, the extended preferences EP ibased on the probability of the best alternative are {a}EP i{a,b}EP i{a,c}EP i{a,b,c}EP i{b}EP i{b,c}EP i{c} The ordering based on the probability of the worst alternative is similar to the previous one, but in this case the probability of the worst alternative is considered. The set in which this probability is higher is less preferable. Let us give it formally. Two social choices X,Y∈Aare compared. Let us sort alternatives from each social choice from the most preferred to the least one, i.e., X={x1,...,x|X|}and Y={y1,...,y|Y|}, where ∀j∈{1,...,|X|−1}xjPixj+1 and ∀j∈{1,...,|Y|−1}yjPiyj+1. We put 123 SERIEs (2011) 2:431–446 435 •If x|X|Piy|Y|, then XEP iY. •If x|X|=y|Y|and |X|>|Y|, then XEP iY. •If x|X|=y|Y|and |X|=|Y|=k, where k∈{2,...,m−1}, then XEP iYif and only if xhPiyhfor the least h∈{2,...,k}for which xh= yh. For example, for 3 alternatives and preferences aP ibP icover them, extended preferences EP ibased on the probability of the worst alternative will be {a}EP i{a,b}EP i{b}EP i{a,b,c}EP i{a,c}EP i{b,c}EP i{c} 3 Manipulability indices and computation scheme Number of alternatives being m, the total number of possible linear orders is equal to m!, and the total number of profiles with nagents is equal to (m!)n.Nitzan (1985) introducesthefollowingindex,which wasalso usedbyKelly(1993). We callthisindex as Nitzan–Kelly’s index and denote as NK, to measure the degree of manipulability of social choice rules NK =d0 (m!)n, where d0is the number of profiles in which manipulation takes place. Aleskerov and Kurbanov (1999) introduce an index to measure the freedom of manipulation.InAleskerov et al. (2011a) we introduced two similar indices: the degree of nonsensitivity to a preference change and the probability of getting worse. Here we also introduce the degree of an uncertain change. This index is used here because we consider the case of weak manipulation, where not all outcomes of voting can be compared. Let us note that for an agent there are (m!−1)linear orders to use instead of her sincere preference. Denote as κ+ ij (i=1,...,n;0≤κ+ ij ≤m!−1) the number of orderings in which voter iis better off in the jth profile. Similarly, κ0 ij is the number of orderings in which the result of voting remains the same, κ− ij is the number of orderings in which the voter is worse off and κ? ij is the number of orderings in which the result of voting changes to the outcome incomparable by the given extension axiom.1It is obvious that κ+ ij +κ0 ij +κ− ij +κ? ij =(m!−1). Dividing each κij by (m!−1)one can find the share of each type of orderings for an agent iin the jth profile. Summing up each share over all agents and dividing it by none can find the average share in the given profile. Summing the share over all profiles and dividing this sum to (m!)nwe obtain four indices I+ 1=(m!)n j=1n i=1κ+ ij (m!)n·n·(m!−1);I0 1=(m!)n j=1n i=1κ0 ij (m!)n·n·(m!−1); I− 1=− (m!)n j=1n i=1κ− ij (m!)n·n·(m!−1);I? 1=(m!)n j=1n i=1κ? ij (m!)n·n·(m!−1). 1The last number is always equal to zero in the case of strong manipulation because all sets can be compared. 123 436 SERIEs (2011) 2:431–446 It is obvious that I+ 1+I0 1+I− 1+I? 1=1. We performed the calculation of indices for 3 and 4 alternatives. For 3, 4 and 5 voters, the respective indices are computed exhaustively (i.e., all possible profiles are checked for the manipulability), and for larger number of voters the statistical scheme is used. In both exhaustive and statistical schemes, for each profile under consideration, all (m!−1)manipulating orderings for each voter are generated and the respective choice sets of manipulating profiles are compared with the choice of the original profile. All indices were calculated for the rules defined in the next session. 4 Voting rules We consider the following ten social choice rules. 1. Plurality Rule Choose alternatives that are ranked first by the maximum number of agents, i.e. a∈C( P)⇔[∀x∈An +(a, P)≥n+(x, P)], where n+(a, P)=card{i∈N|∀y∈AaP iy} 2. q-Approval Let us define n+(a, P,q)=card{i∈N|card{Di(a)}≤q−1}, where Di(a)={y∈A:yP ia}is the upper contour set of a∈Ain Pi∈L.Let n+(a, P,q)be the number of agents for which ais ranked among the first qalternatives in their preference ordering. The integer qcan be called as the degree of the procedure. We define q-Approval as follows a∈C( P)⇔[∀x∈An +(a, P,q)≥n+(x, P,q)], i.e., the alternatives which are admitted to be among the qbest by the highest number of agents are chosen. It can be easily seen that Plurality Rule is a special case of q-Approval where q=1. 3. Borda’s Rule Let ri(x, P)be the cardinality of the lower contour set of x∈A in Pi∈ P, i.e. ri(x, P)=|Li(x)|=|{b∈A:xP ib}|.Thesumofri(x, P)over all i∈Nis called the Borda score of alternative a. r(a, P)= n  i=1 ri(a,Pi). The alternatives with maximum Borda score are chosen., i.e. a∈C( P)⇔[∀b∈A,r(a, P)≥r(b, P)]. 123 SERIEs (2011) 2:431–446 437 4. Black’s Procedure Let us define the majority relation μfor a given profile  P xμy⇔card{i∈N|xP iy}>card{i∈N|yP ix}. CondorcetwinnerCW( P)intheprofile  Pisanelement undominatedinthemajority relation μ(constructed according to the profile), i.e. CW( P)=[a|¬∃x∈A,xμa] Black’s rule picks the unique Condorcet winner if it exists and the Borda winner(s) otherwise. 5. Threshold rule (Aleskerov et al. 2010)Letv1(x)be the number of agents for which the alternative xis the worst in their ordering, v2(x)—is the number of agents placing xthe second worst, and so on, vm(x)—the number of agents considering the alternative xas their best one. Then we order the alternatives lexicographically. The alternative xis said to V-dominate the alternative yif v1(x)<v 1(y)or, if there exists knot more than m, s.t. vi(x)=vi(y), i=1,...,k−1, and vk(x)<v k(y). In other words, first, the number of worst places are compared, if these numbers are equal then the number of second worst places are compared and so on. The alternatives which are not dominated by other alternatives via Vare chosen. 6. Hare’s Procedure First, if an alternative is chosen by a simple majority of voters, then this alternative is chosen, and the procedure stops. Otherwise, the alternative a with the minimum number of votes is omitted. Then the procedure is applied to the set X=A\{a}and to the profile  P/Xuntil the alternative ranked first by a simple majority is found. 7.AntipluralityRuleThe alternative, whichisregardedasthe worst bytheminimum number of agents, is chosen, i.e., a∈C( P)⇔[∀x∈An −(a, P)≤n−(x, P)], where n−(a, P)=card{i∈N|∀y∈AyP ia}. 8. Inverse Borda’s Procedure For each alternative Borda’s count is calculated. Then the alternative awith the minimum count is omitted. Borda’s count are re-calculated for profile  P/X,X=A\{a}, and procedure is repeated until choice is found. 9. Nanson’s Procedure (modified)2For each alternative Borda’s count is calculated. Then average count is calculated, r=(a∈Ar(a, P))/|A|,and alternatives c∈A are omitted for which r(c, P)<r. Then the set X={a∈A:r(a, P)≥r}is considered, and the procedure is applied to the profile  P/X. Such procedure is repeated until choice set will not be empty. 10. Coombs’ Procedure Alternative awhich is the worst for the maximum number of agents is omitted. Then the profile is contracted to the  P/X,X=A\{a}, and the procedure is repeated until the choice set will not be empty. 2As anonymous referee pointed out, in original Nanson’s rule alternatives with the average Borda score are also eliminated. 123 438 SERIEs (2011) 2:431–446 5 Results When we use all preferences extension methods defined above for three alternatives aP ibP icwe have four linear extended orderings 1. (Leximin3){a}EP i{a,b}EP i{b}EP i{a,c}EP i{a,b,c}EP i{b,c}EP i{c} 2. (Leximax3){a}EP i{a,b}EP i{a,b,c}EP i{a,c}EP i{b}EP i{b,c}EP i{c} 3. (PWorst3){a}EP i{a,b}EP i{b}EP i{a,b,c}EP i{a,c}EP i{b,c}EP i{c} 4. (PBest3){a}EP i{a,b}EP i{a,c}EP i{a,b,c}EP i{b}EP i{b,c}EP i{c} For Kelly’s Dominance Axiom we have only the following relations in the extended preferences (KellyDA3) {a}EP i{a,b}EP i{b}EP i{b,c}EP i{c} {a}EP i{a,c}EP i{c} {a}EP i{a,b,c}EP i{c} In Tables 1and 2the results of the NK index calculation for 3 alternatives and 3 and 4 voters are given. We also provide here the results from our previous papers. For comparison with the case of the single-valued choice, we provide in the TBR column, the results for alphabetical tie-breaking rule. For all rules except the Threshold rule the same results were obtained in Aleskerov and Kurbanov (1999). As it is seen from the Tables the degree of manipulability of most social choice rules is underestimated in the case of the alphabetical tie-breaking rule. It is easy to show an example of profile which is manipulable for the extended preferences and not manipulable for tie-breaking framework. For the case of a random tie-breaking there are the results from Pritchard and Wilson (2007) for the first three rules. An interesting fact is that the results coincide with the results for KellyDA3. It can be explained by the fact that the algorithm used for the random tie-breaking mechanism gives the similar extended preferences as KellyDA for 3 alternatives. Table 1 NK index for 3 alternatives and 3 voters Rule Extension Leximin3 Leximax3 PWorst3 PBest3 KellyDA3 TBR Plurality 0.2222 0 0.2222 0 0 0.1667 q-Approval q = 2 0.1111 0.6111 0.1111 0.6111 0.1111 0.2639 Borda 0.3056 0.4167 0.3056 0.4167 0.25 0.2361 Black 0.0556 0.1667 0.0556 0.1667 0 0.1111 Threshold 0.3056 0.4167 0.3056 0.4167 0.25 0.3611 Hare 0.2222 0 0.2222 0 0 0.1111 Inverse Borda 0.0556 0.1667 0.0556 0.1667 0 0.1111 Nanson 0.0556 0.1667 0.0556 0.1667 0 0.1111 Coombs 0.2222 0.5000 0.2222 0.5000 0.1667 0.2222 123 SERIEs (2011) 2:431–446 445 One can see that the value of I? 1in KellyDA3 is mainly added to the I− 1value when we use stronger axioms. Moreover, I? 1is rather small, that is why the results of the strong and weak manipulability do not differ a lot. In this paper we have compared ten different positional rules from their vulnerability to manipulation point of view using different measures and extension axioms. We show that there is no rule which dominates the others for all extension methods, but from several points of view Nanson’s and Hare’s rules are the least manipulable. It is important to note that if we add additional rules to our analysis they can outperform these rules in terms of manipulabilty. Acknowledgements The work of Fuad Aleskerov and Daniel Karabekyan is partially supported by the Scientific Foundation of the Higher School of Economics (grants # 08-04-0008 and # 10-04-0030), Russian Foundation for Basic Research (grant # 08-01-00039a) and Laboratory DECAN of Higher School of Economics. Remzi Sanver acknowledges the support of the Turkish Academy of Sciences Distinguished Young Scientist Award Program (TUBA-GEBIP) and the Scientific and Technological Research Council of Turkey (TUBITAK) through the project # 107K560. The work of Vyacheslav Yakuba is also supported by Russian Foundation for Basic Research (grant # 08-01-00039a). William Zwicker took part at the very beginning of this project. His ideas and comments were very useful. We also thank an anonymous referee, whose comments allow us to improve the text. Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution and reproduction in any medium, provided the original author(s) and source are credited. References Aleskerov F, Chistyakov V, Kalyagin V (2010) The threshold aggregation. Econ Lett 107:261–262 Aleskerov F, Karabekyan D, Sanver R, Yakuba V (2011a) On the degree of manipulability of multi-valued social choice rules. Essays in Honor of Hannu Nurmi, Homo Oeconomicus 28 (1/2):205–216 Aleskerov F, Karabekyan D, Sanver R, Yakuba V (2011b) On manipulability of voting rules in the case of multiple choice. Math Soc Sci (forthcoming) Aleskerov F, Kurbanov E (1999) Degree of manipulability of social choice procedures. Alkan et al (eds) Current trends in economics. Springer, Berlin, pp 13–28 Barbera S (1977) The manipulability of social choice mechanisms that do not leave too much to chance. Econometrica 45:1572–1588 Barbera S, Bossert W, Pattanaik P (2004) Ranking Sets of Objects. In: Barbera S, Hammond PJ, Seidl C (eds) Handbook of utility theory, vol 2. Kluwer Academic Publishers, Boston Chamberlin JR (1985) An investigation into the relative manipulability of four voting systems. Behav Sci 30(4):195–203 Duggan J, Schwartz T (2000) Strategic manipulability without resoluteness or shared beliefs: Gibbard– Satterthwaite generalized. Soc Choice Welf 17:85–93 Favardin P, Lepelley D (2006) Some further results on the manipulability of social choice rules. Soc Choice Welf 26:485–509 Gärdenfors P (1976) Manipulation of social choice functions. J Econ Theory 13:217–228 Gehrlein WV, Fishburn PC (1976) Condorcet’s paradox and anonymous preference profiles. Public Choice 26:1–18 Gibbard A (1973) Manipulation of voting schemes. Econometrica 41:587–601 Kelly J (1977) Strategy-proofness and social choice functions without single-valuedness. Econometrica 45:439–446 Kelly J (1993) Almost all social choice rules are highly manipulable, but few aren’t. Soc Choice Welf 10:161–175 Nitzan S (1985) The vulnerability of point-voting schemes to preference variation and strategic manipulation. Public Choice 47:349–370 123 446 SERIEs (2011) 2:431–446 Ozyurt S, Sanver MR (2009) A general impossibility result on strategy-proof social choice hyperfunctions. Games Econ Behav 66:880–892 Pattanaik P (1978) Strategy and group choice. North-Holland, Amsterdam Pritchard G, Wilson M (2007) Exact results on manipulability of positional voting rules. Soc Choice Welf 29:487–513 SatterthwaiteM (1975) Strategy-proofnessandArrow’sconditions:existenceandcorrespondencetheorems for voting procedures and social welfare functions. J Econ Theory 10:187–217 Smith D (1999) Manipulability measures of common social choice functions. Soc Choice Welf 16(4): 639–661 123