Tag Archives: voting

Distance-based voting rules

After a long gestation period in which I seemed to be publishing nothing, a few projects have reached maturity. With Benjamin Hadjibeyli, I have a preprint studying so-called distance rationalizable voting rules, which we recently submitted. These are voting rules in which we specify some notion of consensus winner, set up a distance measure on elections, and then choose the winner(s) based on minimizing the distance to a consensus election. This framework has been used by other authors over the years, particularly by Edith Elkind, Piotr Faliszewksi and Arkadii Slinko in a series of papers.

We deal with a lot of foundational issues and give some insight into the way Minkowski geometry relates to decisiveness of such rules. This includes both positive and negative results.

This work was inspired by discussions with Elchanan Mossel and Miklos Racz in Berkeley in 2013, about whether the Dodgson rule is a so-called hyperplane rule. That question is still not answered, but now the underbrush has been cleared, it makes sense to go back to it.

Paradoxes of runoff voting

The New Zealand Labour party will soon have an election for leader of its Parliamentary caucus. The voting system is a weighted form of instant runoff using the single seat version of Hare’s method (instant runoff/IRV/alternative vote). IRV works as follows. Each voter submits a full preference order of the candidates (I am not sure what happens if a voter doesn’t rank all candidates but presumably the method can still work). In each round, the voter with smallest number of first preferences (the plurality loser) is eliminated, and the candidate removed from the preference orders, keeping the order of the other candidates the same. If there is a tie for the plurality loser in a round, this must be broken somehow.

The NZLP variant differs from the above only in that not all voters have the same weight. In fact, the caucus (34 members) has a total weight of 40%, the party members (tens of thousands, presumably) have total weight 40%, and the 6 affiliated trade unions have total weight 20%, the weight being proportional to their size. It is not completely clear to me how the unions vote, but it seems that most of them will give all their weight to a single preference order, decided by union leaders with some level of consultation with members. Thus in effect there are 34 voters each with weight 20/17, 6 with total weight 20, and the rest of the weight (total 40) is distributed equally among tens of thousands of voters. Note that the total weight of the unions is half the total weight of the caucus, which equals the total weight of the individual members.

IRV is known to be susceptible to several paradoxes. Of course essentially all voting rules are, but the particular ones for IRV include the participation paradoxes which have always seemed to me to be particularly bad. It is possible, for example, for a candidate to win when some of his supporters fail to vote, but lose when they come out to vote for him, without any change in other voters’ behaviour (Positive Participation Paradox). This can’t happen with three candidates, which is the situation we are interested in (we denote the candidates C, J, R). But the Negative Participation Paradox can occur: a losing candidate becomes a winner when new voters ranking him last turn out to vote.

The particular election is interesting because there is no clear front-runner and the three groups of voters apparently have quite different opinions. Recent polling suggests that the unions mostly will vote CJR. In the caucus, more than half have R as first choice, and many apparently have C as last. Less information is available about the party members but it seems likely that C has most first preferences, followed by J and R.

The following scenario on preference orders is consistent with this data: RCJ 25%, RJC 7%, CRJ 10%, CJR 30%, JRC 20%, JCR 8%. In this case, J is eliminated in the first round and R wins over C in the final round by 52% to 48%. Suppose now that instead of abstaining, enough previously unmotivated voters decide to vote JRC (perhaps because of positive media coverage for J and a deep dislike of C). Here “enough” means “more than 4% of the total turnout before they changed their minds, but not more than 30%”. Then R is eliminated in the first round, and C wins easily over J. So by trying to support J and signal displeasure with C, these extra voters help to achieve a worse outcome than if they had stayed at home.

The result of the election will be announced within a week, and I may perhaps say more then.

The Complexity of Safe Manipulation under Scoring Rules

This paper will appear in Proceedings of IJCAI ’11 and be presented at the conference in Barcelona in July.

Abstract: Slinko and White have recently introduced a new model of coalitional
manipulation of voting rules under limited communication, which they
call {em safe strategic voting}. The computational aspects of this
model were first studied by Hazon and Elkind, who provide
polynomial-time algorithms for finding a safe strategic vote under
$k$-approval and the Bucklin rule. In this paper, we answer an open
question of Hazon and Elkind by presenting a polynomial-time algorithm
for finding a safe strategic vote under the Borda rule. Our results for
Borda generalize to several interesting classes of scoring rules.

The probability of safe manipulation

This paper (joint with Reyhaneh Reyhani) will be presented at COMSOC 2010. It deals with the concept of “safe manipulation”, whereby an agent can attempt to manipulate the result of an election without risk, provided that voters of other preferences vote sincerely but irrespective of the number of like-minded voters that also try to vote strategically. It was introduced by Slinko and White in COMSOC 2008.

Abstract: The concept of safe manipulation has recently been introduced by Slinko and White. We show how to compute the asymptotic probability that a safe manipulation exists for a given scoring rule under the uniform distribution on voting situations (the so- called Impartial Anonymous Culture). The technique used is computation of volumes of convex polytopes. We present explicit numerical results in the 3-candidate case.

Download author copy

Probability calculations under the IAC hypothesis

Mark C. Wilson and Geoffrey  Pritchard, Mathematical Social Sciences 54 (2007), 244-256.

Download author version

Abstract: We show how powerful algorithms recently developed for counting lattice points and computing volumes of convex polyhedra can be used to compute probabilities of a wide variety of events of interest in social choice theory. Several illustrative examples are given.

Exact results on manipulability of positional voting rules

Geoffrey Pritchard and Mark C. Wilson, Social Choice and Welfare 29 (2007), 487-513.

Download author version

Abstract:

We consider 3-candidate elections under a general scoring rule and derive precise conditions for a given voting situation to be strategically manipulable by a given coalition of voters. We present an algorithm that makes use of these conditions to compute the minimum size M of a manipulating coalition for a given voting situation.

The algorithm works for any voter preference model — here we present numerical results for IC and for IAC, for a selection of scoring rules, and for numbers of voters up to 150. A full description of the distribution of M is obtained, generalizing all previous work on the topic.

The results obtained show interesting phenomena and suggest several conjectures. In particular we see that rules “between plurality and Borda” behave very differently from those “between Borda and antiplurality”.