On asymptotic strategy-proofness of the plurality and the run-off rules

In this paper we prove that the plurality rule and the run-off procedure are asymptotically strategy-proof for any number of alternatives and that the proportion of profiles, at which a successful attempt to manipulate might take place, is in both cases bounded from above by , where n is the number of participating agents and K does not depend on n. We also prove that for the plurality rule the proportion of manipulable profiles is asymptotically bounded from below by , where k also does not depend on n. Received: 10 February 2000/Accepted: 19 October 2000     

On Asymptotic Strategy-Proofness of Classical Social Choice Rules

We show that, when the number of participating agents n tends to infinity, all classical social choice rules are asymptotically strategy-proof with the proportion of manipulable profiles being of order O (1/n).     

On the Average Minimum Size of a Manipulating Coalition

We study the asymptotic average minimum manipulating coalition size as a characteristic of quality of a voting rule and show its serious drawback. We suggest using the asymptotic average threshold coalition size instead. We prove that, in large electorates, the asymptotic average threshold coalition size is maximised among all scoring rules by the Borda rule when the number m of alternatives is 3 or 4, and by -approval voting when m ≥ 5.     

Rationalizations of Condorcet-consistent rules via distances of hamming type

In voting, the main idea of the distance rationalizability framework is to view the voters’ preferences as an imperfect approximation to some kind of consensus. This approach, which is deeply rooted in the social choice literature, allows one to define (“rationalize”) voting rules via a consensus class of elections and a distance: a candidate is said to be an election winner if she is ranked first in one of the nearest (with respect to the given distance) consensus elections. It is known that many classic voting rules can be distance-rationalized. In this article, we provide new results on distance rationalizability of several Condorcet-consistent voting rules. In particular, we distance-rationalize the Young rule and Maximin using distances similar to the Hamming distance. It has been claimed that the Young rule can be rationalized by the Condorcet consensus class and the Hamming distance; we show that this claim is incorrect and, in fact, this consensus class and distance yield a new rule, which has not been studied before. We prove that, similarly to the Young rule, this new rule has a computationally hard winner determination problem.     

Self-selective social choice functions

It is not uncommon that a society facing a choice problem has also to choose the choice rule itself. In such situations, when information about voters’ preferences is complete, the voters’ preferences on alternatives induce voters’ preferences over the set of available voting rules. Such a setting immediately gives rise to a natural question concerning consistency between these two levels of choice. If a choice rule employed to resolve the society’s original choice problem does not choose itself, when it is also used for choosing the choice rule, then this phenomenon can be regarded as inconsistency of this choice rule as it rejects itself according to its own rationale. Koray (Econometrica 68: 981–995, 2000) proved that the only neutral, unanimous universally self-selective social choice functions are the dictatorial ones. Here we introduce to our society a constitution, which rules out inefficient social choice rules. When inefficient social choice rules become unavailable for comparison, the property of self-selectivity becomes more interesting and we show that some non-trivial self-selective social choice functions do exist. Under certain assumptions on the constitution we describe all of them.     

Is it ever safe to vote strategically?

There are many situations in which mis-coordinated strategic voting can leave strategic voters worse off than they would have been had they not tried to strategise. We analyse the simplest of such scenarios, in which a set of strategic voters all have the same sincere preferences and all contemplate casting the same strategic vote, while all other voters are not strategic. Most mis-coordinations in this framework can be classified as instances of either strategic overshooting (too many voted strategically) or strategic undershooting (too few). If mis-coordination can result in strategic voters ending up worse off than they would have been had they all just voted sincerely, we call the strategic vote unsafe. We show that under every onto and non-dictatorial social choice rule there exist circumstances where a voter has an incentive to cast a safe strategic vote. We extend the Gibbard–Satterthwaite Theorem by proving that every onto and non-dictatorial social choice rule can be individually manipulated by a voter casting a safe strategic vote.     

Approximability of Dodgson’s rule

It is known that Dodgson’s rule is computationally very demanding. Tideman (Soc Choice Welf 4:185–206, 1987) suggested an approximation to it but did not investigate how often his approximation selects the Dodgson winner. We show that under the Impartial Culture assumption the probability that the Tideman winner is the Dodgson winner converges to 1 as the number of voters increase. However we show that this convergence is not exponentially fast. We suggest another approximation—we call it Dodgson Quick—for which this convergence is exponentially fast. Also we show that the Simpson and Dodgson rules are asymptotically different.     

How the size of a coalition affects its chances to influence an election

Since voting rules are prototypes for many aggregation procedures, they also illuminate problems faced by economics and decision sciences. In this paper we are trying to answer the question: How large should a coalition be to have a chance to influence an election? We answer this question for all scoring rules and multistage elimination rules, under the Impartial Anonymous Culture assumption. We show that, when the number of participating agents n tends to infinity, the ratio of voting situations that can be influenced by a coalition of k voters to all voting situations is no greater than $D_{m} \frac{k}{n}Since voting rules are prototypes for many aggregation procedures, they also illuminate problems faced by economics and decision sciences. In this paper we are trying to answer the question: How large should a coalition be to have a chance to influence an election? We answer this question for all scoring rules and multistage elimination rules, under the Impartial Anonymous Culture assumption. We show that, when the number of participating agents n tends to infinity, the ratio of voting situations that can be influenced by a coalition of k voters to all voting situations is no greater than , where D _m is a constant which depends only on the number m of alternatives but not on k and n. Recent results on individual manipulability in three alternative elections show that this estimate is exact for k=1 and m=3.

Arkadii SlinkoEmail: