Good morning, I’d like to take this opportunity to tell you about some work that I’ve been currently doing
with my old friend and colleague Partha Dasgupta, it’s a project of long standing on voting.
I’m going to tell you a bit about one of the recent pieces of that long term project which focuses on strategic voting.
So let me try to set the scene.
In voting theory we typically study what is called a voting rule.
A voting rule is simply a method for choosing or electing a candidate to fill a particular office, say office of the president.
On the basis of voters preferences for the various candidates.
Preferences can be expressed by rankings, they can be expressed by utility functions,
they can be expressed sometimes in other ways.
So the voting rule would determine the winner on the basis of preferences
and also on the basis of who the actual set of candidates is.
Who are the people actually on the ballot.
And you're all familiar with some of the standard examples but let me run through a few of those examples.
First of all there is plurality rule, which in practice is probably the most widely used voting rule.
It’s used to elect members of parliaments in Britain, senators, representatives in the US.
In many countries it’s used to elect presidents such as in South Korea.
And the way it works is that the candidate who wins is the candidate who is ranked first by more voters than any other,
even if that candidate is not ranked first by a majority.
Then there is Majority Rule which was first studied in detail by the Marquis de Condorcet 200 years ago.
Possibly one of the best studied rules in theory.
And the way this works is when voters submit their preferences, the candidate who is elected winner is the one
who according to those preferences is preferred by a majority to each other candidate on the ballot.
So that’s Majority Rule.
Then there is run off voting, run off voting is used in presidential elections in France,
it’s used in presidential elections in Brazil, it’s used in many other parts of the world.
And here once again we look for a candidate who is ranked first by more voters than any other but if there is no candidate
who actually gets a majority of first place votes, then we go to a second round where the top 2 candidates,
sometimes it’s the top 2 candidates, sometimes it’s the top 3 candidates, there are variations on this rule,
but among the top 2 candidates we look then for the one who is preferred by a majority.
Then there is rank order voting.
It’s sometimes called the Borda count because it was particularly propounded by the arch rival to the Marquis de Condorcet
in the 18th century, French academy of sciences, Jean-Charles Borda and what Borda proposed
and you’ve probably used this method in some form yourself when you’ve served on a committee.
Every time a candidate is ranked first by a voter, she gets one point, if she’s ranked second she gets 2 points
and so on and then we simply add up a candidates points and whoever gets the lowest point total is the winner.
Notice that low point totals correspond to high rankings.
Let me mention one more potential voting rule although we don’t ordinarily think of it as a voting role.
There are reasons why we don’t normally use it as a voting rule and I will come to those later.
But this is utilitarianism, that is if we express people’s preferences by their utility functions,
then what we could do is to simply elect the candidates on the ballot who maximises the sum of voter’s utilities.
Think of that as a voting rule.
Ok well I’ve mentioned 5 possible voting rules and I could have mentioned many, many others
which have been used in practice and studied in theory.
This multiplicity gives rise to a natural question, which of the many possibilities should we actually use.
Well the answer to that question takes us back to a prior step where we ask ourselves
what is it that we actually want in a voting rule.
So this is what a voting theorist would do, a voting theorist would try to break up the problem,
which voting rule should we adopt into a more fundamental question or a series or more fundamental questions,
what is it that we want out of a voting rule and the way that we express what we want is through a set of criteria or axioms
that we would want the voting rule to satisfy.
And then we try to study which voting rules satisfy these axioms or at least come closest to satisfying them.
The particular criterion or axiom I want to emphasise today is non-manipulability or put the other way,
we want to prevent people from having the incentive to vote strategically.
Voters should not have reason to misrepresent their preferences, to vote other than the way they truly feel.
And there are a variety of reasons why non manipulability is an attractive axiom, an attractive criteria
and let me just mention 2.
One is simply the idea that if people are voting strategically we are distorting the input into the voting rule.
Think of a voting rule as a way of transforming the inputs, the preferences of voters in to an output namely who gets elected.
Well if we’re distorting the inputs, if people are not actually giving you their preferences, they’re giving you something else,
then we’re also distorting the output, we’re not actually implementing the voting rule we thought we were.
But I think an equally important reason for avoiding strategic voting is that we make it harder for voters
when we impose on them voting rules where strategic voting is a reasonable thing for them to do.
Why is that.
Well if you’re a voter, you have to expend a certain amount of time and energy and effort,
just figuring out what your own preferences are because you have to listen to the candidates,
you have to read up on their past records, you have to compare them with the other candidates, that can be a serious job.
If on top of that you also have to figure out how other voters are likely to rank the candidates.
And react against those other voters, that's what strategic voting is.
You’ve got a decision problem which is an order of magnitude more difficult.
So we are imposing a great burden on voters if we insist that to vote well they have to vote strategically.
Unfortunately as many of you may know from your theory classes, there’s negative results about strategic voting
which is called the Gibbard-Satterthwaite theorem, its closely related to another negative result,
the arrow and possibility theorem.
And it says that if there are 3 or more candidate on the ballot essentially no voting rule is always non-manipulable.
Now dictatorial rules are non-manipulable.
In a dictatorship there’s just one voter who matters and that voters preferences are translated into a winner
but since we tend not to like dictatorial rules we think of Gibbard-Satterthwaite as a negative result.
There’s a sense in which it’s too negative.
That is it insists when we impose non-manipulability that a voting will never be manipulable
but of course in practice there may be circumstances where manipulation could occur
but those circumstances just aren’t very likely, so we don’t worry about them very much.
So in our view the natural question given a negative result like Gibbard-Satterthwaite, is which voting rules are non-manipulable,
which reasonable voting rules because I’m going to impose other criteria as well,
which reasonable voting rules are non-manipulable most often.
And that’s the question that this particular paper tries to answer.
And in other papers in this project we are focusing on somewhat different criteria.
So let me tell you a little bit about how we tried to answer that question.
In particular what other properties, what other axioms we want voting rules to satisfy.
As you’ll see for those of you who have looked at voting at all, all of the axioms,
all of the principles I’ll be talking about here are very standard,
there’s nothing unconventional about the list of axioms at all.
That the first one I’m sure you're all familiar with, it’s the Pareto property and it simply says
that if all voters prefer candidate X to candidate Y and candidate Y happens to be on the ballots,
then we shouldn’t elect candidate X, it would be very perverse to elect X.
I’m sorry I got it the wrong way round.
X is preferred to Y, Y is on the ballot, we shouldn’t elect Y because everyone prefers X to Y.
It would be perverse to elect Y.
Another very compelling property is anonymity.
Which says that if we start with a distribution of preferences and now voters exchange their preferences,
so voter I gives his preferences to voter J and voter J gives her preferences to voter K and so on,
in other words we permute the preferences we should still get the same winner.
Because all we’ve done is to change the identities of the voters who have particular preferences,
we haven’t changed the distribution.
And that just says that only voter’s preferences matter, not who the voters are.
Or put still another way, voters should all be treated the same.
There’s an analogous property which says that just as we want to treat all voters equally we should treat all candidates equally.
The names of the candidates should not matter and that’s neutrality.
Now not surprisingly all the voting rules that I’ve mentioned in my introductory remarks, plurality rule, Majority Rule,
rank order voting, utilitarianism, satisfy these first 3 properties.
It would be a very strange voting rule indeed that violated any of them
but the next axiom does serve to start distinguishing among the voting rules.
And for that reason it’s also been the most controversial.
And indeed I’m going to drop it later on because of this controversy.
But let’s see where it leads to first.
The reason why I want to consider it is that despite the controversy around it, it has quite an attractive justification
and it also has a very good pedigree.
It was proposed in different forms more or less at the same time by Kenneth Arrow and John Nash.
And that is what in this context we might call independence of irrelevant candidates.
In other context it’s called independence of irrelevant alternatives.
And it just says that if we hold an election and candidate X wins and now we modify the ballots,
so that some of the non winning candidates are no longer on the ballot, well then candidate X really ought to continue to win
because after all the candidates who were removed from the ballot didn’t win anyway.
So why should removing them change.
By the way I’m giving you this axiom in the Nash formulation but I could have done it the Arrow way.
So on the face of it this sounds quite reasonable and in fact it was the violation of this axiom
that got people worked up in a number of recent real life political elections.
So some of you may remember the 2000 US Presidential election, it was a closely contested election between George W. Bush,
essentially between George W. Bush and Al Gore and you may know that that election was so close that it came down to one state,
the state of Florida which Bush ended up winning by fewer than 600 votes out of close to 6 million votes.
So Bush won and he became the president as a result.
But there was a third candidate on the ballot, Ralph Nader, who commanded a significant number of votes,
not nearly enough to be a serious candidate but he got almost 100,000 votes.
And we know from a variety of evidence that people who voted for Nader almost surely would have voted for Gore,
had Nader not been running, at least provided that they had voted at all.
So if Nader had not been on the ballots Gore would not only have won but he would have won quite comfortably.
And so Nader in effect spoiled the election, he changed the outcome of the election
even though he himself had no realistic chance of winning.
That is what independence is getting at, the idea that these marginal candidates like Nader
shouldn’t have the power to change the outcome of the entire election.
Well Majority Rule and utilitarianism clearly satisfy independence.
If candidate X beats the other candidates by a majority and we now delete some of those other candidates from the ballots,
candidate X continues to beat the remaining candidates by a majority.
So Majority Rule satisfies independence.
Similarly if candidate X maximises the sum of utilities, among a set of candidates, we make that set of candidates smaller,
it will, the same candidate will still maximise the sum.
But plurality rule clearly does not satisfy independence, in fact the Florida example shows us that.
By the way I picked on Florida but I could have given plenty of other examples, the French election,
the French presidential election of 2002 is another case where independence was quite clearly violated.
And here is a more formal example of why plurality rule violates independence.
I won’t labour that.
Rank order voting violates independence as well.
So I presented a set of pretty standard axioms
but the one I’ve reserved for last is the one I started with which is non-manipulability.
I talked about it informally as trying to eliminate strategic voting.
What does it mean expressed more carefully, expressed more formally, it means that if candidate X wins
when voters express their preferences truthfully and now some group of voters,
some coalition of voters manipulate their preferences, misrepresent them and now candidate X prime wins,
as a result of that manipulation.
Then it better be the case that at least one member of the coalition doesn’t gain from the manipulation.
In other words at least one member of the coalition is better off with X rather than X prime,
otherwise the coalition would have the incentive to do the misrepresentation.
And that’s what non-manipulability requires.
Now one immediate implication of non-manipulability is that a voting rule must be ordinal,
that is intensities of preferences, cardinal information cannot be used.
And so in particular this rules out utilitarianism, it’s pretty easy to see
that utilitarianism is going to violate non-manipulability because just let’s imagine that there are 2 candidates,
X and Y on the ballot and suppose that you actually prefer X to Y, but not by that much, I’m talking about your intensity,
your intensity, feeling for X versus Y is not all that strong.
Nevertheless when you go into the voting booth and you think that Y might win the election,
you have an incentive to express a very strong preference for X, to increase the chance that she wins.
So under utilitarianism there are very strong incentives for strategic voting.
Unfortunately Majority Rule also violates non-manipulability and this is a more subtle point.
The problem with Majority Rule and many of you I’m sure know this, is that it’s not even always well defined.
In fact this is a point that Condorcet himself made 200 years ago.
Here is an example of a configuration of preferences, the population breaks down into 3 groups,
35% of the population like candidate X the best and then Y and then Z, 33% Y, Z, X, the remaining 32% Z, X, Y.
For this configuration there is no majority winner because notice that a majority of people prefer X to Y.
I’m afraid, I know that there are 3 screens but I can’t use this laser pointer for all 3
so I’m going to use it for the middle screen.
I hope people on the sides can see.
These people prefer X to Y, these people prefer X to Y, so X beats Y, but Z beats X by a majority,
these people prefer Z to X, these people prefer Z to X, so X can’t be the majority winner either.
And Y beats Z, these people prefer Y to Z, these people prefer Y to Z, that constitutes a majority as well.
So there’s no majority winner and that means that we have to use some tie breaking rule to determine a winner.
This configuration of preferences is called a Condorcet cycle.
And when a Condorcet cycle occurs we have to extend Majority Rule or use a tie breaking rule.
One such tie breaking rule would be to use Majority Rule if a winner exists in say rank order voting,
if a majority winner does not exist, that's called Black’s method.
The problem is that such an extension, such a tie breaking rule makes Majority Rule manipulable.
So here is the same example I just used, the same configuration of preferences, there’s no majority winner.
If we use rank order voting to break the tie then X wins.
But it turns out that the people in the middle, this group of people now have the incentive to misrepresent their preferences
and say that they are Z, Y, X because if they do that now Z becomes the majority winner and they prefer Z to X.
Now I’ve listed 5 axioms, Pareto, anonymity, neutrality, independence, non-manipulability.
As I said there is no voting rule that satisfies them all, this is essentially the Gibbard-Satterthwaite theorem.
But this is overly pessimistic because there are many cases
in which some of the preference rankings that voters could have are very unlikely.
Think of Majority Rule for example.
It turns out that Majority Rule will satisfy all 5 properties including non-manipulability.
If we avoid preferences where there are Condorcet cycles.
And when can we rule out Condorcet cycles, well one case is where voters vote ideologically.
Let’s go back to this US presidential election of 2000.
From left to right the candidates on the ideological spectrum were Nader, Gore, Bush,
it’s unlikely that there were very many voters who say put Bush first and then Nader and then Gore or Nader first
and then Bush and then Gore because if you like Nader the best then Gore is closest to you ideologically,
Gore is closer than Bush so you’re not likely to have this ranking.
But if we rule out these rankings then it turns out that Majority Rule will satisfy all 5 properties.
There are other conditions under which Majority Rule will satisfy all 5 conditions.
And this leads us to a definition that a voting rule works well provided that it satisfies our 5 axioms
when preferences are restricted to some limited domain.
So we’re not allowing all possible preferences because not all preferences are likely.
We’re looking at a limited set of preferences and we’ll insist that a voting rule work well for that limited set.
So for example Majority Rule works well when preferences are single peaked.
But now we get the following theorem which tells us that if we start with any voting rule,
any voting rule F that works well for a particular domain of preferences,
then Majority Rule must also work well on that same domain.
And furthermore imagine that Majority Rule works well on a domain where it differs from the voting role that we started with, F.
Then there must exist a domain where Majority Rule works well and F does not.
In other words Majority Rule dominates each other voting rule in the sense that Majority Rule will work well
when the other voting rule works well and there will be some cases where Majority Rule works well
and the other voting rule does not.
Now I’d like to take one more minute to modify this theorem, I said that among all of the axioms that I’ve talked about,
it’s independence which is the most controversial.
So let me take one more minute to say what happens when we drop independence.
Well if we simply drop independence but we don’t do anything about preferences, we get an impossibility result again,
that’s the Gibbard-Satterthwaite result.
But what we can try to do is once again look at restricted classes of preferences and now since I used the word work well before,
I can’t repeat it because we have a different concept here,
so I’m going to say that a voting rule works nicely on a particular domain of preferences if it satisfies the 4 remaining axioms,
Pareto, anonymity, neutrality, non-manipulability on that domain.
And now we have theorem 2 which says that if, which looks very much like theorem 1 with one twist.
Suppose that a voting rule works nicely for a particular domain of preferences.
Then either Majority Rule or rank order voting or perhaps both also work nicely on that domain.
And conversely if one of the 2, Majority Rule or rank order voting works nicely on some domain
and it differs from the voting rule that we started with.
Then there will exist some other domain where Majority Rule or rank order voting works nicely
and the voting rule we started with does not.
So we get domination in the same sense as in the first result except that now it’s dominated by these 2 voting rules,
Majority Rule and rank order voting jointly.
And I’m not going to bother with the proof but let me conclude by saying that there’s something satisfying at least to me
that these 2 ancient voting rules, Majority Rule, rank order voting by far are the 2 best studied voting rules of all,
going back literally hundreds of years, emerge as best, at least according to this analysis.
It’s also nice to see that this ancient rivalry between Condorcet and Borda has a nice reconciliation,
that is there’s a sense in which Condorcet and Borda were both right.
Thank you very much.
(applause).