Judgment Aggregation. Gabriella Pigozzi

Чтение книги онлайн.

СКАЧАТЬ of Victoria in 1882, published in a British Government Blue Book of 1907, and languished there undiscussed until 1958. C. L. Dodgson (‘Lewis Carroll’) discussed Condorcet and Borda methods, and procedures for breaking cycles, in three pamphlets printed in the 1870s; he worked in ignorance of his predecessors, and again was not understood until 1958. [McL90, p. 99]

      However, there have been precedents to the work of those scholars. In particular, McLean [McL90] discovered that a method developed by Condorcet was proposed as early as in the thirteenth century by Ramon Lull, and that a method developed by Borda was introduced in the fifteenth century by Nicolas Cusanus. So, what are these Condorcet and Borda methods and why are they so important in the history of social choice?

       Borda

      Jean-Charles de Borda, a French mathematician member of the Academy of Sciences, developed the first mathematical theory of elections. According to Black,¹ Borda read the paper before the Academy of Sciences already in 1770. However, the report that was supposed to be written about Borda’s essay was never accomplished. Fourteen years later, a report on a manuscript by Marie Jean Antoine Nicolas Caritat (better known as the Marquis de Condorcet) was presented at the Academy. Few days later, Borda read for the second time his paper, which was printed in 1781, but published only in 1784 [Bor84]. Borda method was adopted by the Academy as the method to elect its members. It was used until 1800 when a new member, Napoleon Bonaparte, attacked it.

      Figure 1.1: A problem with plurality voting.

      In his Mémoire sur les élections au scrutin, Borda first showed that plurality voting, probably the most well-known voting method, is not satisfactory as it may elect the wrong candidate. In plurality voting, each individual votes one candidate, and the candidate that receives the greatest number of votes is elected. The problem with this procedure is that it ignores the individual preferences over candidates. Suppose, for example, that there are three alternatives x, y and z and 60 voters. Of these 60 voters, 25 prefer x to y and y to z, 20 prefer y to z and z to x and, finally, 15 prefer z to y and y to x, as shown in Figure 1.1, where preferences are given in a left to right order.

      Assuming that the individuals vote for the candidate at the top of their preferences, we obtain that x gets 25 votes, y gets 20 votes and z only 15. Thus, if plurality vote is used, x will be selected. However, Borda noticed that for a majority of the voters, x is the least preferred candidate: pairwise majority comparison shows that 35 voters against 25 would prefer both y and z to x. Plurality vote selects the candidate that receives the most votes but not necessarily more than half of the votes in pairwise comparisons. Thus, the two procedures (plurality and pairwise majority) can lead to different outcomes. What is interesting is that, as observed by Black, in his argument Borda really made use of what is now known as the Condorcet criterion, according to which a voting system should select the candidate that defeats every other candidate. When it exists, such a candidate is unique and is called the Condorcet winner. However, Borda did not develop this line of thought. We have to await Condorcet for such a principle to be clearly put forward.

      The solution proposed by Borda to the fact that plurality may select the wrong candidate is a method which makes use of the entire order in the voters’ preferences. In his method, voters rank all the candidates (assumed to be finite). If there are n candidates, each top place candidate gets n points, each candidate at the second place gets n − 1 points, and so on until the least preferred candidate, which gets 1 point. The alternative with the highest total score is elected. Borda’s rank-order method is an example of what we would call today a scoring rule.² Scoring rules are a class of standard aggregation rules in preference aggregation [You74, You75].

      Let us suppose that a voter prefers x to y and y to z. The Borda method rests on two assumptions. The first is the measurability of utility, i.e. (paraphrasing Borda) that the degree of superiority that the voter gives to x over y should be considered the same as the degree of superiority that he gives to y over z. The second is interpersonal utility, that is, how different individual utilities can be measured. In Borda method, voters are given equal weight. The justification that Borda provides for the first assumption is based on ignorance: there is no reason to assume that, by placing y between x and z, the voter wanted to place y nearer to x than to z. The second is justified on the basis of equality among voters. At the end of his paper, he claims that his method can be used in any kind of committee decision. Even though Borda fails to thoroughly examine the nature of collective decisions [Bla58], he realized that his method was open to manipulation, that is, to the possibility of voters misrepresenting their true preferences to the rule in order to elect a better (according to their true preferences) candidate.³ In particular, a voter could place the strongest competitors to his most preferred candidate at the end of the ranking. Addressing this issue Borda famously replied: “My scheme is only intended for honest men.”

       Condorcet

      The other famous member of the Academy of Sciences was Condorcet. His work on the theory of elections is mostly contained in the mathematical (and hardly readable) Essai sur l’Application de l’Analyse à la Probabilité des Décisions Rendues à la Pluralité des Voix [Con85]. Borda and Condorcet were friends and in a footnote in his Essai, Condorcet says that he completed his work before he was acquainted with Borda’s method.

      As Black traced back, there are really two approaches in Condorcet’s work. The first contribution is in line with Borda. Like Borda, Condorcet observes that plurality vote may result in the election of a candidate against which each of the other candidates has a majority. This led to the formulation of the above mentioned Condorcet criterion, that is, the candidate to be elected is the one that receives a majority against each other candidate (instead of just the highest number of votes). Whereas Borda employed a positional approach, Condorcet recommended a method based on the pairwise comparison of alternatives. Given a set of individual preferences, the method suggested by Condorcet consisted in the comparison of each of the alternatives in pairs. For each pair, the winner is determined by majority voting, and the final collective ordering is obtained by a combination of all partial results. The Condorcet winner is the candidate that beats every other alternative in a pairwise majority comparison. However, he also discovered a disturbing problem of majority voting, now known as the Condorcet paradox. He discovered that pairwise majority comparison may lead a group to hold an intransitive preference (or a cycle, as later called by Dodgson) of the type that x is preferred to y, y is preferred to z, and z to x. This is the cycle we obtain if we consider, for example, three voters expressing preferences as in Figure 1.2, where preferences are given in a left to right order and voter 1 prefers x to y and y to z, voter 2 prefers y to z and z to x, while voter 3 prefers z to x and x to y.

      Figure 1.2: An illustration of the Condorcet paradox.

      The trouble with a majority cycle is that the group seems unable to single out the ‘best’ alternative in a principled manner. Note also that devising rules fixing some order in which the alternatives are to be compared does not solve the problem. For instance, if in the example above we fix a rule that compares alternatives x and y first and the winner is then pitted against z, СКАЧАТЬ