ТОП просматриваемых книг сайта:
Judgment Aggregation. Gabriella Pigozzi
Читать онлайн.Название Judgment Aggregation
Год выпуска 0
isbn 9781681731780
Автор произведения Gabriella Pigozzi
Жанр Компьютерное Железо
Серия Synthesis Lectures on Artificial Intelligence and Machine Learning
Издательство Ingram
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, alternative z would win the election. However, if we instead choose to compare x and z first and then to compare the winning alternative with y, we would get a different result, namely y would be the winning alternative.
Condorcet’s second main contribution employs probability theory to deal with the ‘jury problem’. Voters are seen like jurors who vote for the ‘correct’ alternative (or the ‘best’ candidate). The idea that groups make better decisions than individuals dates back to Rousseau [Rou62], according to whom, in voting, individuals express their opinions about the ‘best’ policy, rather than personal interests. Condorcet approached Rousseau’s position in probabilistic terms and aimed at an aggregation procedure that would maximize the probability that a group of people take the right decision. This led Condorcet to formulate the result now known as the Condorcet Jury Theorem, which provides an epistemic justification to majority rule [GOF83]. The theorem states that, when all jurors are independent and have a probability of being right on the matter at issue, which is higher than random, then majority voting is a good truth-tracking method. In other words, under certain conditions, groups make better decisions than individuals, and the probability of the group taking the right decision approaches 1 as the group size increases.
So, interestingly, Condorcet showed at the same time the possibility of majority cycles, a negative result around which much of the literature on social choice theory built up, and a positive result like the Condorcet Jury Theorem, which gives an epistemic justification to majority voting.4
Dodgson
From the overview so far, the reader may have gotten the impression that the early developments of social choice theory were exclusively due to French scholars. But this is not the case. Indeed many English mathematicians have also studied the subject: Eduard John Nanson, Francis Galton and, more importantly, the Rev. Charles Lutwidge Dodgson (better known as ‘Lewis Carroll’, author of Alice’s Adventures in Wonderland), to whom we now turn.
Black gives a careful analysis of Dodgson’s life and of the circumstances that raised the interests of a Mathematics lecturer at Christ Church college in Oxford for the theory of elections. In particular, Black discovered three of Dodgson’s previously unpublished pamphlets and, thanks to his extensive research, could conclude that Dodgson ignored the works of both Borda and Condorcet.
Dodgson referred to well-known methods of voting (like plurality and Borda’s method) and highlighted their deficiencies. For him the main interest of the theory of elections resided in the existence of majority cycles. He suggested a modification of Borda’s method to the effect of introducing a ‘no election’ alternative among the existing ones [Dod73], the idea being that in case of cycles, the outcome should be ‘no election’. He then claimed that if there is no Condorcet winner, his modified method of marks should be used [Dod74].
Later Dodgson proposed a method based on pairwise comparison that may seem to contradict the ‘no election’ principle he introduced earlier. However, as Arrow suggests [Arr63], this approach could be used when we do not wish to accept ‘no election’ as a possible outcome. The new method (now known as Dodgson rule) selects the Condorcet winner (whenever there is one) and otherwise finds the candidate that is ‘closest’ to being a Condorcet winner [Dod76]. The idea is to find the (not necessarily unique) alternative that can be made a Condorcet winner by a minimum number of preference switchings in the original voters’ preferences. A switch is a preference reversal between two adjacent positions. In order to illustrate the method, let us consider one of the examples made by Dodgson himself.
Consider the preference profile given in Figure 1.3. Each row represents a group of voters with the same preferences, given in a left to right order. The number in the first column indicates the size of each group. In this example, there are eleven voters and four alternatives (a, b, c, and d). As the reader can easily check, the majority is cyclical (adcba) and none of the alternatives is a Condorcet winner. However, if the voter holding preference dcba switches alternatives c and b (marked by an asterisk) in her preference ranking, b becomes a Condorcet winner. Alternative c also can be made a Condorcet winner by one switch, so b and c are the only Dodgson winners (a and d each need four switches to be preferred to every other alternative by some strict majority).
1.1.2 MODERN SOCIAL CHOICE THEORY
We have mentioned how Robbins’s claim [Rob38] that interpersonal utilities could not be compared undermined what constituted the predominant utilitarian approach to welfare economics until the Thirties: this amounted to say that there is social improvement when everyone’s utility goes up (or, at least, no one’s utility goes down when someone’s