Eric S. Maskin

Elections and Strategic Voting: Condorcet and Borda

Category: Lectures

Date: 26 August 2011

Duration: 34 min

Quality: MD SD

Subtitles: EN DE

Eric S. Maskin (2011) - Elections and Strategic Voting: Condorcet and Borda

There are many different voting rules that could be used to elect a public official such as a president. Plurality rule (first-past-the-post), majority rule (Condorcet’s method), rank-order voting (Borda count), and runoff voting are just a few of the rules that have been used practically and studied theoretically

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

Guten Morgen. Ich möchte diesen Anlass nutzen, Ihnen davon zu erzählen, woran ich zuletzt mit meinem alten Freund und Kollegen Partha Dasgupta gearbeitet habe, nämlich an einem seit langem laufenden Projekt über das Abstimmen. Ich berichte über einen der jüngsten, mit dem strategischen Abstimmen befassten Teilaspekt dieses langfristigen Projekts. Worum geht es? In der Abstimmungstheorie untersuchen wir typischerweise etwas, das Abstimmungsregel genannt wird. Eine Abstimmungsregel ist eine Methode, nach der man sich für einen Kandidaten entscheidet bzw. einen Kandidaten wählt, der sich um ein bestimmtes Amt bewirbt, etwa um das Amt des Präsidenten, und zwar auf der Grundlage der Wählerpräferenzen für die verschiedenen Kandidaten. Präferenzen können durch Ranglisten ausgedrückt werden, sie können durch Nützlichkeitsfunktionen ausgedrückt werden, und manchmal können sie auch auf andere Arten ausgedrückt werden. Die Abstimmungsregel würde also den Sieger auf der Grundlage von Präferenzen und außerdem anhand dessen bestimmen, welche Kandidaten tatsächlich zur Wahl stehen, wer also die Menschen auf dem Wahlzettel eigentlich sind. Sie alle kennen natürlich die Standardbeispiele, doch lassen sie mich ein paar von diesen Beispielen durchleuchten. Zunächst haben wir die einfache Mehrheitsregel - in der Praxis wahrscheinlich die am weitesten verbreitete Abstimmungsregel. Nach dieser Regel wählt man Parlamentsabgeordnete in Großbritannien sowie Senatoren und Mitglieder des Repräsentantenhauses in den USA. In vielen Ländern, etwa in Südkorea, werden nach dieser Regel Präsidenten gewählt. Sie besagt Folgendes: Der siegreiche Kandidat ist jener Kandidat, der von mehr Wählern an die erste Stelle gesetzt wird als irgendein anderer, auch wenn der Kandidat nicht von einer Mehrheit an die erste Stelle gesetzt wird. Dann gibt es die Pluralitätsregel, die zuerst von Marquis de Condorcet vor 200 Jahren gründlich untersucht wurde. Das ist wahrscheinlich eine der in der Theorie am besten untersuchten Regeln. Sie besagt Folgendes: Wenn die Wähler ihre Präferenzen zuteilen, wird jener Kandidat zum Sieger gekürt, der gemäß diesen Präferenzen von einer Mehrheit allen anderen Kandidaten auf dem Stimmzettel vorgezogen wird. Das ist also die Pluralitätsregel. Dann gibt es die Stichwahlregel. Das Stichwahlverfahren kommt bei den Präsidentschaftswahlen in Frankreich und Brasilien sowie in vielen anderen Teilen der Welt zum Einsatz. Auch hier suchen wir einen Kandidaten, der von mehr Wählern an die erste Stelle gesetzt wird als irgendein anderer, doch wenn im ersten Wahlgang kein Kandidat die Mehrheit der Stimmen erringt, gibt es einen zweiten Wahlgang mit den beiden erstplatzierten Kandidaten. Das heißt: Manchmal sind es die zwei erstplatzierten Kandidaten, manchmal sind es die ersten drei, diese Regel wird unterschiedlich gehandhabt. Doch unter den beiden erstplatzierten Kandidaten wird derjenige ermittelt, der von einer Mehrheit bevorzugt wird. Dann gibt es das Rangsummenverfahren. Dieses Verfahren wird manchmal Borda-Regel genannt, weil es insbesondere vom Erzrivalen des Marquis de Condercet in der französischen Akademie der Wissenschaften des 18. Jahrhunderts vertreten wurde, von Jean-Charles Borda. Die von Borda vorgeschlagene Methode haben Sie wahrscheinlich in der einen oder anderen Form selbst schon angewandt, wenn sie einem Ausschuss angehörten. Wenn ein Kandidat von einem Wähler an die erste Stelle gesetzt wird, erhält er einen Punkt, wird er an die zweite Stelle gesetzt, erhält er zwei Punkte und so weiter. Am Schluss zählen wir die Punkte eines Kandidaten einfach zusammen, und wer die niedrigste Gesamtzahl von Punkten erhalten hat, ist der Sieger. Beachten Sie bitte, dass niedrige Punktzahlen hohen Rangstellen entsprechen. Lassen Sie mich eine weitere mögliche Abstimmungsregel ansprechen, auch wenn wir sie für gewöhnlich nicht als Abstimmungsregel betrachten. Es gibt Gründe dafür, warum wir sie normalerweise nicht als Abstimmungsregel heranziehen; darauf werde ich später zurückkommen. Es handelt sich dabei um den Grundsatz des Utilitarismus: Wenn wir die Präferenzen der Menschen durch ihre Nützlichkeitsfunktionen ausdrücken, könnten wir einfach denjenigen Kandidaten auf dem Stimmzettel küren, der die Summe der Nutzen für den Wähler maximiert. Betrachten Sie das als Abstimmungsregel. Ich habe jetzt also fünf mögliche Abstimmungsregeln erwähnt. Ich hätte noch viele, viele andere ansprechen können, die in der Praxis angewandt und in der Theorie untersucht wurden. Diese Vielfalt führt natürlich zu der Frage, für welche der vielen Möglichkeiten wir uns entscheiden sollten. Die Antwort auf diese Frage führt uns zurück zu einem vorgelagerten Schritt, bei dem wir uns fragen, was wir mit einer Abstimmungsregel eigentlich erreichen wollen. Ein Abstimmungstheoretiker würde versuchen, das Problem, welche Abstimmungsregel wir übernehmen sollen, in eine grundlegendere Frage bzw. eine Reihe grundlegenderer Fragen zu zerlegen: Was wollen wir mit einer Abstimmungsregel erreichen? Das, was wir erreichen wollen, drücken wir durch bestimmte Kriterien oder Grundsätze aus, denen die Abstimmungsregel nach unserer Vorstellung gerecht werden soll. Und dann versuchen wir zu untersuchen, welche Abstimmungsregeln diesen Grundsätzen gerecht werden oder ihnen zumindest soweit wie möglich gerecht werden. Ich möchte heute ein bestimmtes Kriterium bzw. einen bestimmten Grundsatz hervorheben, nämlich die Nicht-Manipulierbarkeit. Anders ausgedrückt: Wir wollen erreichen, dass die Wähler keinen Anreiz haben, strategisch abzustimmen. Die Wähler sollen keinen Grund haben, ihre Präferenzen falsch wiederzugeben, also anders zu wählen, als sie es in Wahrheit für richtig halten. Es gibt eine Reihe von Gründen, warum Nicht-Manipulierbarkeit ein einleuchtender Grundsatz ist, ein einleuchtendes Kriterium. Zwei davon möchte ich ansprechen. Einer beruht auf der einfachen Vorstellung, dass dann, wenn die Menschen strategisch wählen, die Vorgaben der Abstimmungsregel verzerrt werden. Betrachten Sie eine Abstimmungsregel als Möglichkeit, die Beiträge der Wähler, ihre Präferenzen, in ein Ergebnis umzuwandeln - den siegreichen Kandidaten. Wenn wir nun die Beiträge verzerren, wenn die Menschen in Wirklichkeit ihre Präferenzen nicht preisgeben, sondern etwas anderes kundtun, dann verzerrt das auch das Ergebnis, und wir haben in Wirklichkeit nicht die Abstimmungsregel eingeführt, die wir uns vorgestellt haben. Ein ebenso wichtiger Grund für die Vermeidung strategischen Wählens besteht meiner Ansicht nach darin, dass wir es den Wählern schwerer machen, wenn wir ihnen Abstimmungsregeln vorgeben, nach denen es vernünftig ist, strategisch abzustimmen. Warum ist das so? Nun, als Wähler müssen Sie eine bestimmte Menge an Zeit, Energie und Mühen aufwenden, um herauszufinden, wo Ihre Präferenzen liegen, denn Sie müssen sich die Kandidaten anhören, Sie müssen nachlesen, was sie in der Vergangenheit gesagt haben, Sie müssen sie mit den anderen Kandidaten vergleichen - das kann eine schwere Aufgabe sein. Wenn Sie dazu noch herausfinden müssen, wie andere Wähler die Kandidaten vermutlich einstufen, um Ihre Reaktion an diesen anderen Wählern auszurichten - das ist strategisches Wählen -, dann bekommen Sie ein Entscheidungsproblem, das um Größenordnungen schwieriger ist. Wir bürden den Wählern also eine große Last auf, wenn wir darauf bestehen, dass sie strategisch abstimmen müssen, wenn sie gut abstimmen wollen. Wie wahrscheinlich viele von Ihnen aus dem theoretischen Unterricht wissen, führt das strategische Abstimmen leider zu einem negativen Resultat, dem Gibbard-Satterthwaite-Theorem, das eng verwandt ist mit einem anderen negativen Resultat, nämlich mit dem Arrow-Unmöglichkeitstheorem, welches besagt, dass dann, wenn drei oder mehr Kandidaten zur Wahl stehen, praktisch keine Abstimmungsregel durchgehend nicht manipulierbar ist. Nun - diktatorische Regeln sind nicht manipulierbar. In einer Diktatur gibt es nur einen Wähler von Belang, und die Präferenzen dieses Wählers werden in einen Wahlsieger umgewandelt. Da wir aber diktatorische Regeln eher ablehnen, halten wir Gibbard-Satterthwaite für ein negatives Ergebnis. In einem Sinn ist es zu negativ: Die Vorgabe der Nicht-Manipulierbarkeit verlangt, dass eine Abstimmung niemals manipulierbar ist. In der Praxis aber kann es natürlich Situationen geben, in denen Manipulationen vorkommen könnten. Da diese Situationen aber nicht sehr wahrscheinlich sind, machen wir uns über sie keine Gedanken. Unserer Ansicht nach stellt sich angesichts eines negativen Resultats wie des Gibbard-Satterthwaite-Theorems natürlich die Frage, welche Abstimmungsregeln nicht manipulierbar sind - welche vernünftigen Abstimmungsregeln, denn ich werde auch noch andere Kriterien vorgeben - welche vernünftigen Abstimmungsregeln also am ehesten nicht manipulierbar sind. Der Antwort auf diese Frage geht die genannte Abhandlung nach. In anderen Arbeiten des Projekts befassen wir uns mit etwas anderen Kriterien. Lassen Sie mich berichten, wie wir versucht haben, diese Frage zu beantworten. Insbesondere geht es darum, welche anderen Eigenschaften Abstimmungsregeln aufweisen sollten; welchen anderen Grundsätzen sie unserer Ansicht nach gerecht werden sollten. Wie diejenigen von Ihnen, die sich überhaupt mit Abstimmungen befasst haben, erkennen werden, sind diese anderen Grundsätze, die Prinzipien, von denen ich hier sprechen werde, ausnahmslos nichts Ungewöhnliches; an der Liste der Grundsätze ist nichts unkonventionell. Ich bin sicher, dass Sie alle den ersten Grundsatz kennen. Es handelt sich um die Pareto-Eigenschaft, die ganz einfach Folgendes besagt: Wenn alle Wähler den Kandidaten X dem Kandidaten Y vorziehen und Kandidat Y zur Wahl steht, dann sollten wir Kandidat X nicht wählen, es wäre widersinnig, Kandidat X zu wählen... Entschuldigung, es ist genau andersherum. X wird Y vorgezogen, Y steht zur Wahl, wir sollten Y nicht wählen, da jedermann X gegenüber Y bevorzugt. Es wäre widersinnig, Y zu wählen. Eine weitere höchst überzeugende Eigenschaft ist Anonymität. Das bedeutet: Wenn wir eine Verteilung der Präferenzen vornehmen und die Wähler ihre Präferenzen austauschen, wenn also Wähler I seine Präferenzen an Wähler J weitergibt und Wähler J seine Präferenzen an Wähler K und so weiter, wenn wir, anders ausgedrückt, die Präferenzen permutieren, sollten wir dennoch denselben Sieger erhalten. Denn wir haben nichts weiter getan, als die Identitäten der Wähler mit bestimmten Präferenzen zu ändern, wir haben nicht die Verteilung geändert. Das bedeutet, dass nur die Präferenzen der Wähler von Bedeutung sind, nicht wer die Wähler sind. Oder noch einmal anders ausgedrückt: Die Wähler sollten alle gleich behandelt werden. Es gibt eine entsprechende Eigenschaft, nach der wir ebenso, wie wir alle Wähler gleich behandeln wollen, auch alle Kandidaten gleich behandeln sollten. Die Namen der Kandidaten sollten keine Rolle spielen - das ist Neutralität. Es überrascht nicht, dass alle Abstimmungsregeln, die ich in meinen einleitenden Bemerkungen erwähnt habe - die Pluralitätsregel, die Mehrheitsregel, das Rangsummenverfahren, der Grundsatz des Utilitarismus - diese drei ersten Eigenschaften aufweisen. Eine Abstimmungsregel, die gegen eine dieser Vorgaben verstoßen würde, wäre wirklich sehr befremdlich. Doch der nächste Grundsatz kann tatsächlich dazu herangezogen werden, zwischen den Abstimmungsregeln zu unterscheiden. Deshalb ist er auch der am meisten umstrittene Grundsatz. Wegen dieser Kontroversen werde ich ihn später fallen lassen, doch zuerst wollen wir sehen, wohin er führt. Der Grund, warum ich mich mit ihm befassen möchte, liegt darin, dass er trotz der mit ihm verbundenen Kontroversen eine ziemlich überzeugende Begründung und außerdem einen illustren Stammbaum aufweist. Er wurde in verschiedenen Formen mehr oder weniger gleichzeitig von Kenneth Arrow und John Nash vorgeschlagen. Es handelt sich um einen Grundsatz, den wir im vorliegenden Zusammenhang Unabhängigkeit von irrelevanten Kandidaten nennen könnten. In einem anderen Kontext spricht man von der Unabhängigkeit von irrelevanten Alternativen. Er besagt Folgendes: Wenn Kandidat X eine Wahl gewinnt und daraufhin die Stimmzettel so geändert werden, dass einige der nicht gewählten Kandidaten nicht mehr zur Wahl stehen, dann sollte Kandidat X wiederum gewinnen, da schließlich alle vom Stimmzettel gestrichenen Kandidaten ohnehin nicht gewonnen haben. Warum also sollte sich dadurch, dass sie gestrichen werden, etwas ändern? Übrigens präsentiere ich Ihnen diesen Grundsatz in der Formulierung von Nash, aber ich hätte auch den Arrow-Weg einschlagen können. Auf den ersten Blick klingt er ziemlich vernünftig, und tatsächlich waren es Verstöße gegen diesen Grundsatz, die die Gemüter bei mehreren tatsächlichen politischen Wahlen erhitzten. Einige von Ihnen erinnern sich vielleicht noch an die amerikanische Präsidentschaftswahl des Jahres 2000. Es war eine hart umkämpfte Wahl zwischen George W. Bush, im Wesentlichen zwischen George W. Bush und Al Gore, und wie Sie vielleicht wissen, war diese Wahl so knapp, dass ein Staat den Ausschlag gab, der Staat Florida, den Bush schließlich mit weniger als 600 Stimmen Vorsprung bei annähernd sechs Millionen Wahlberechtigten gewann. Bush gewann also und wurde demzufolge Präsident. Aber es stand noch ein dritter Kandidat zur Wahl, Ralph Nader, der eine erhebliche Anzahl von Stimmen erhielt - nicht annähernd genug, um als ernsthafter Kandidat gelten zu können, doch er bekam fast 100.000 Stimmen. Und wir wissen anhand verschiedener Anhaltspunkte, dass diejenigen, die für Nader gestimmt hatten, so gut wie sicher für Gore gestimmt hätten, wenn Nader nicht kandidiert hätte, vorausgesetzt jedenfalls, sie hätten überhaupt gewählt. Wenn also Nader nicht zur Wahl gestanden hätte, dann hätte Gore nicht nur gewonnen; er hätte sogar mit einem komfortablen Vorsprung gewonnen. Und so kam es, dass Nader die Wahl faktisch auf den Kopf stellte. Er veränderte das Wahlergebnis, obwohl er selbst keine realistische Siegchance hatte. Das ist es, worauf der Grundsatz der Unabhängigkeit abzielt - es geht um die Vorstellung, dass diese unbedeutenden Kandidaten nicht in der Lage sein sollten, das Wahlergebnis insgesamt zu verändern. Nun, der Grundsatz der Unabhängigkeit wird durch die Mehrheitsregel ebenso wie durch den Utilitarismus klarerweise erfüllt. Wenn Kandidat X die anderen Kandidaten mit einer Stimmenmehrheit schlägt und wir einige dieser anderen Kandidaten vom Wahlzettel streichen, schlägt Kandidat X die verbliebenen Kandidaten immer noch mit der Mehrheit der Stimmen. Die Mehrheitsregel erfüllt also das Unabhängigkeitskriterium. Ebenso gilt: Wenn Kandidat X unter mehreren zur Wahl stehenden Kandidaten die Summe der Nützlichkeiten maximiert, verkleinern wir die Gruppe der Kandidaten. Derselbe Kandidat wird auch dann die Summe maximieren. Die Pluralitätsregel jedoch erfüllt den Grundsatz der Unabhängigkeit klarerweise nicht, wie uns das Beispiel Florida vor Augen führt. Übrigens hätte ich statt Florida zahlreiche andere Beispiele nennen können; die französische Präsidentschaftswahl von 2002 ist ein weiterer Fall, bei dem der Grundsatz der Unabhängigkeit ziemlich eindeutig verletzt wurde. Und hier haben wir ein eher formales Beispiel dafür, warum die Pluralitätsregel gegen den Grundsatz der Unabhängigkeit verstößt; darauf werde ich jetzt aber nicht eingehen. Das Rangsummenverfahren verstößt ebenfalls gegen den Grundsatz der Unabhängigkeit. Ich habe jetzt einige Standardgrundsätze vorgestellt, aber der, den ich mir bis zuletzt aufgehoben habe, ist der, mit dem ich begonnen habe, nämlich die Nicht-Manipulierbarkeit. Ich habe beiläufig erwähnt, dass dadurch versucht werde, strategisches Abstimmen zu unterbinden. Was bedeutet dieser Grundsatz, wenn man ihn sorgfältiger, formaler formuliert? Er bedeutet, dass Kandidat X dann gewinnt, wenn die Wähler ihre Präferenzen wahrheitsgemäß ausdrücken, dass aber dann, wenn eine Gruppe, eine Koalition von Wählern ihre Präferenzen manipuliert, sie falsch zum Ausdruck bringt, als Ergebnis dieser Manipulation Kandidat X' gewinnt. Dann soll es besser sein, wenn mindestens ein Mitglied der Koalition aus der Manipulation keinen Nutzen zieht, oder anders ausgedrückt: wenn mindestens einem Mitglied der Koalition mit X besser gedient ist als mit X', da sich die Koalition sonst veranlasst sehen würde, ihre Präferenzen falsch zum Ausdruck zu bringen. Das ist es, was Nicht-Manipulierbarkeit erfordert. Eine unmittelbare Folge der Nicht-Manipulierbarkeit besteht darin, dass eine Abstimmungsregel ordinal skaliert sein muss, was bedeutet, dass die Intensität von Präferenzen, dass eine kardinale Information unbrauchbar ist. Das schließt insbesondere den Grundsatz des Utilitarismus aus - es ist ziemlich einfach zu sehen, dass Utilitarismus den Grundsatz der Nicht-Manipulierbarkeit verletzt. Denn stellen wir uns vor, zwei Kandidaten, X und Y, stehen zur Wahl. Angenommen, Sie ziehen Kandidat X Kandidat Y vor, aber nicht sehr stark. Ich spreche hier über Ihre Intensität - die Intensität, mit der Sie X gegenüber Y bevorzugen, ist nicht besonders stark. Wenn Sie aber in die Wahlkabine gehen und glauben, dass Y die Wahl gewinnen könnte, ist das für Sie ein Anreiz, eine sehr starke Präferenz für X auszudrücken, um seine Siegchancen zu verbessern. Unter utilitaristischen Gesichtspunkten gibt es also sehr starke Anreize für strategisches Abstimmen. Leider verletzt auch die Mehrheitsregel den Grundsatz der Nicht-Manipulierbarkeit. Dieser Punkt ist etwas subtiler. Wie viele von Ihnen sicherlich wissen, besteht das Problem mit der Mehrheitsregel darin, dass sie nicht immer klar definiert ist. Darauf hat schon Condorcet selbst vor 200 Jahren hingewiesen. Hier sehen Sie ein Beispiel für eine Konfiguration von Präferenzen: Die Bevölkerung ist in drei Gruppen unterteilt - Für 33 % ist die Reihenfolge Y, Z, X; für die übrigen 32 % Z, X, Y. Bei dieser Konfiguration gibt es keinen Mehrheitssieger: Beachten Sie bitte, dass eine Mehrheit der Wähler X gegenüber Y bevorzugt. Es tut mir leid, ich weiß, dass es drei Bildschirme gibt, aber ich kann diesen Laserpointer nicht für alle drei verwenden, weshalb ich ihn für den mittleren Bildschirm verwende. Ich hoffe, dass auch die seitlich Sitzenden etwas sehen können. Diese Wähler bevorzugen X gegenüber Y, und diese Wähler bevorzugen ebenfalls X gegenüber Y. X schlägt also Y, doch Z schlägt X mit einer Mehrheit: Diese Wähler bevorzugen Z gegenüber X, und diese Wähler bevorzugen ebenfalls Z gegenüber X; X kann also auch nicht die Mehrheit erringen. Und Y schlägt Z - diese Wähler bevorzugen Y gegenüber Z, und diese Wähler bevorzugen ebenfalls Y gegenüber Z; auch das stellt eine Mehrheit dar. Es gibt also keinen Mehrheitssieger, was bedeutet, dass wir zur Ermittlung eines Siegers auf eine Ausnahmeregel zurückgreifen müssen. Diese Konfiguration von Präferenzen wird Condorcet-Paradoxon genannt. Wenn ein Condorcet-Paradoxon auftritt, müssen wir die Mehrheitsregel erweitern bzw. auf eine Ausnahmeregel zurückgreifen. Eine derartige Ausnahmeregel bestünde darin, die Mehrheitsregel heranzuziehen, wenn sie einen Sieger ergibt, und z.B. das Rangsummenverfahren heranzuziehen, wenn es keinen Mehrheitssieger gibt. Das nennt man die Black-Methode. Das Problem besteht darin, dass eine derartige Erweiterung bzw. Ausnahmeregel die Mehrheitsregel manipulierbar macht. Hier ist das Beispiel, das ich gerade verwendet habe, die gleiche Konfiguration von Präferenzen, es gibt keinen Mehrheitssieger. Wenn wir zur Herbeiführung einer Entscheidung das Rangsummenverfahren verwenden, dann gewinnt X. Es stellt sich jedoch heraus, dass die Wähler in der Mitte, dass diese Wählergruppe jetzt den Anreiz spürt, ihre Präferenzen falsch auszudrücken und die Reihenfolge Z, Y, X anzugeben, denn wenn sie das tut, wird Z der Mehrheitssieger, und sie bevorzugt ja Z gegenüber X. Ich habe fünf Grundsätze aufgeführt - Pareto, Anonymität, Neutralität, Unabhängigkeit und Nicht-Manipulierbarkeit. Wie ich schon sagte, gibt es keine Abstimmungsregel, die allen gerecht wird; so lautet im Wesentlichen das Gibbard-Satterthwaite-Theorem. Doch das ist allzu pessimistisch, denn es gibt viele Fälle, in denen einige der Präferenzranglisten, die von den Wählern erstellt werden können, sehr unwahrscheinlich sind. Denken Sie zum Beispiel an die Mehrheitsregel. Es erweist sich, dass die Mehrheitsregel alle fünf Eigenschaften aufweist, einschließlich der Nicht-Manipulierbarkeit - wenn wir Präferenzen vermeiden, bei denen es zu einem Condorcet-Paradoxon kommt. Und wann können wir ein Condorcet-Paradoxon ausschließen? Zum Beispiel in dem Fall, dass die Wähler ideologisch abstimmen. Kommen wir auf diese amerikanische Präsidentschaftswahl von 2000 zurück. Von links nach rechts im ideologischen Spektrum lautete die Reihenfolge der Kandidaten Nader, Gore, Bush. Es ist unwahrscheinlich, dass es viele Wähler gab, für die, sagen wir, Bush an erster Stelle kam, dann Nader und dann Gore oder Nader an erster Stelle, dann Bush und dann Gore, denn wenn Ihnen Nader am besten gefällt, dann steht Ihnen Gore ideologisch näher, Gore steht Ihnen näher als Bush. Es ist also unwahrscheinlich, dass Sie die genannte Rangordnung erstellen. Wenn wir aber diese Rangordnungen ausschließen können, dann stellt sich heraus, dass die Mehrheitsregel alle fünf Eigenschaften aufweist. Es gibt noch weitere Bedingungen, unter denen die Mehrheitsregel alle fünf Vorgaben erfüllt. Das führt uns zu einer Definition, wonach eine Abstimmungsregel unter der Voraussetzung gut funktioniert, dass sie unsere fünf Grundsätze dann erfüllt, wenn Präferenzen auf einen begrenzten Bereich beschränkt sind. Wir erlauben also nicht alle möglichen Präferenzen, da nicht alle Präferenzen wahrscheinlich sind. Wir betrachten eine begrenzte Gruppe von Präferenzen und behaupten, dass eine Abstimmungsregel für diese begrenzte Gruppe gut funktioniert. Zum Beispiel funktioniert die Mehrheitsregel gut, wenn Präferenzen eingipflig sind. Doch nun erhalten wir das folgende Theorem. Es sagt uns, dass dann, wenn wir mit einer beliebigen Abstimmungsregel beginnen, einer Abstimmungsregel F, die für einen bestimmten Bereich von Präferenzen gut funktioniert, dass dann die Mehrheitsregel im gleichen Bereich ebenfalls gut funktionieren muss. Stellen Sie sich außerdem vor, dass die Mehrheitsregel in einem Bereich gut funktioniert, in dem sie sich von der Abstimmungsregel, mit der wir begonnen haben - also von F - abweicht. Dann muss es einen Bereich geben, in dem die Mehrheitsregel gut funktioniert, F aber nicht. Anders ausgedrückt: Die Mehrheitsregel dominiert jede andere Abstimmungsregel in dem Sinn, dass sie gut funktioniert, wenn die andere Abstimmungsregel gut funktioniert, und dass es einige Fälle gibt, in denen die Mehrheitsregel gut funktioniert, nicht aber die anderen Abstimmungsregeln. Ich brauche noch eine Minute, um dieses Theorem zu modifizieren. Ich habe gesagt, dass unter allen Grundsätzen, die ich angesprochen habe, der Grundsatz der Unabhängigkeit am stärksten umstritten ist. Geben Sie mir noch eine Minute, um zu erklären, was passiert, wenn wir den Grundsatz der Unabhängigkeit fallen lassen. Nun, wenn wir den Grundsatz der Unabhängigkeit einfach aufgeben, die Präferenzen aber unberührt lassen, dann erhalten wir wieder ein unmögliches Resultat, nämlich das Gibbard-Satterthwaite-Resultat. Wir können aber versuchen, erneut eingeschränkte Klassen von Präferenzen zu betrachten. Den Ausdruck "gut funktionieren", den ich vorhin benutzt habe, kann ich übrigens nicht wiederholen, da es sich hier um ein unterschiedliches Konzept handelt. Ich werde also sagen, dass eine Abstimmungsregel für einen bestimmten Bereich von Präferenzen angemessen funktioniert, wenn sie in diesem Bereich die vier übrigen Grundsätze erfüllt - Pareto, Anonymität, Neutralität, Nicht-Manipulierbarkeit. Und nun haben wir Theorem 2, das ganz ähnlich aussieht wie Theorem 1, mit einer Änderung. Nehmen wir an, dass eine Abstimmungsregel für einen bestimmten Bereich von Präferenzen angemessen funktioniert. Dann funktioniert entweder die Mehrheitsregel oder das Rangsummenverfahren für diesen Bereich ebenfalls angemessen, oder vielleicht sogar beide. Umgekehrt gilt: Wenn eine der beiden Regeln, die Mehrheitsregel oder das Rangsummenverfahren, für einen bestimmten Bereich angemessen funktioniert und von der Abstimmungsregel, mit der wir begonnen haben, abweicht, dann gibt es einen anderen Bereich, für den die Mehrheitsregel oder das Rangsummenverfahren angemessen funktioniert, nicht aber die Abstimmungsregel, mit der wir begonnen haben. Damit erhalten wir Dominanz in demselben Sinn wie beim ersten Resultat, nur dass jetzt diese beiden Abstimmungsregeln, die Mehrheitsregel und das Rangsummenverfahren, gemeinsam dominieren. Den Beweis hierfür spare ich mir, doch lassen Sie mich abschließend sagen, dass es zumindest für mich zufriedenstellend ist, dass diese zwei altehrwürdigen Abstimmungsregeln - die Mehrheitsregel und das Rangsummenverfahren sind die zwei über hunderte von Jahren mit Abstand am gründlichsten untersuchten Abstimmungsregeln - dass sich diese beiden als die besten erweisen, jedenfalls nach dem Ergebnis dieser Untersuchung. Es ist auch schön zu sehen, dass die alte Fehde zwischen Condorcet und Borda auf elegante Weise beigelegt werden kann - in einem gewissen Sinn hatten sie beide Recht. Vielen Dank.

Abstract

There are many different voting rules that could be used to elect a public official such as a president. Plurality rule (first-past-the-post), majority rule (Condorcet’s method), rank-order voting (Borda count), and runoff voting are just a few of the rules that have been used practically and studied theoretically.

One way to decide which rule is “best” is to proceed axiomatically. We can specify a set of desiderata (axioms) that we would like a voting rule to satisfy and then determine which rule(s) come closest to satisfying them.

Unfortunately, the best-known result in the voting literature is negative: the Gibbard-Satterthwaite theorem implies that there is no voting rule that always satisfies the following axioms: Pareto efficiency, anonymity (all voters should be treated equally), neutrality (all candidates should be treated equally), decisiveness (there should be a clear-cut winner), independence of irrelevant alternatives (the election outcome should be insensitive to removing marginal candidates from the ballot), and strategy-proofness (there should be no incentive to vote strategically, i.e., to vote for candidate A even though one prefers B). We show, however, that there is a sense in which majority rule satisfies these axioms more often than any other. If we drop the independence axiom, then majority rule and rank-order voting jointly satisfy the axioms the most often.

(P. Dasgupta and E. Maskin)