Judgment Aggregation. Gabriella PigozziЧитать онлайн книгу.
outline: We start by giving a brief overview of the history of social choice theory, from the contributions of Borda and Condorcet during the French Revolution (Section 1.1.1) until the general impossibility theorem by Arrow in 1951 that started modern social choice theory (Section 1.1.2). We then present the doctrinal paradox that originated the whole field of judgment aggregation (Section 1.2), and look at how judgment aggregation relates to the older theory of preference aggregation (Section 1.2.2). In the concluding section we point to literature at the interface of social choice theory, computer science and artificial intelligence, completing the sketch of the broad scientific context of the present book.
1.1 A CONCISE HISTORY OF SOCIAL CHOICE THEORY
Social choice theory studies how individual preferences and interests can be combined into a collective decision. An example of such a type of aggregation problems is a group electing one of many candidates on the basis of the preferences that the individuals in the group express over the candidates.
Collective decision-making is a constant feature of human societies. In his 1998 Nobel lecture, Amartya Sen [Sen99] recalled that already in the fourth century B.C., Aristotle in Greece and Kautilya in India explored how different individuals could take social decisions. However, the systematic and formal study of voting and committee decisions started only during the French Revolution, thanks to French mathematicians like Borda, Condorcet and Laplace.
Besides the problem of selecting the winning candidate in an election, social choice theory has its origins in the normative analysis of welfare economics [Sen86], a branch of modern economics that evaluates economic policies in terms of their effects on the social welfare of the members of the society. Welfare economics took inspiration from Jeremy Bentham’s utilitarianism rather than from Borda and Condorcet. According to Bentham’s utilitarianism fundamental axiom, “it is the greatest happiness of the greatest number that is the measure of right and wrong” [Ben76, Preface (2nd para.)]. Utilitarianisms assumed that individual preferences could be expressed by cardinal utilities and that they could then be compared across different individuals (interpersonally comparable preferences). Yet, in the 1930s both cardinality and interpersonal comparability of personal utility were questioned by Lionel Robbins [Rob38]. If utilities reflect individual mental states—Robbins argued—since it is not possible to measure mental states, then utilities cannot be compared across several individuals either. It was such “informational restriction” [Sen86] of social welfare to a n-tuple of ordinal (and interpersonally non-comparable) individual utilities that induced economists to look at methods developed in the theory of elections. As we shall see in Section 1.1.2, the informational restriction that followed Robbins’s criticisms made the problem of welfare economics look similar to the exercise of deriving a social preference ordering from individual orderings of social states, a problem addressed by Borda and Condorcet during the French Revolution.
1.1.1 THE EARLY HISTORY
On the history of the theory of elections McLean wrote:
The theory of voting is known to have been discovered three times and lost twice. The work of Condorcet, Borda, and Laplace was entirely ignored from about 1820 until 1952, with the sole exception of E. J. Nanson’s paper ‘Methods of Election’, which was read to the Royal Society 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,1 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.2 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