Читать книгу Judgment Aggregation - Gabriella Pigozzi - Страница 11

CHAPTER 1

Logic Meets Social Choice Theory

Judgment aggregation is a recent theory that combines aggregation problems previously studied by social choice theory with logic. Social choice theory is a vast subject, including not only the study of preference aggregation and voting theory but also topics like social welfare and justice. Given the tight links between judgment aggregation and preference aggregation, in this first chapter we give a concise survey on some historical aspects of preference aggregation and then introduce and motivate the more recent field of judgment aggregation. The chapter builds on [Sen99, Sen86, Bla58] for the historical overview on social choice theory, and on [KS93, Kor92] for the informal introduction to judgment aggregation.

Chapter 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,¹ 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, 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.⁴

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 utility goes up) [Sen95].

It thus appeared that social welfare must be based on just the n-tuple of ordinal interpersonally non-comparable, individual utilities. […] This “informational crisis” is important to bear in mind in understanding the form that the origin of modern social choice theory took. In fact, with the binary relation of preference replacing the utility function as the primitive of consumer theory, it made sense to characterise the exercise as one of deriving a social preference ordering R from the n-tuple of individual orderings {Ri} of social states. [Sen86, p. 1074]

Figure 1.3: An example of Dodgson’s rule.

The need for functions of social welfare defined over all the alternative social states was made explicit by Abram Bergson [Ber38, Ber66] and Paul Samuelson [Sam47]. Economists turned to the mathematical approach to elections explored by Condorcet, Borda, and Dodsgon only when—following the informational restriction decreed by Robbins—they searched for methods to aggregate binary relations of preference into a social preference ordering. Thus, social choice theory stemmed from two distinct problems—how to select the winning candidate in an election, and how to define social welfare—and the relations between these problems became clear only in the 1950s.

Young economist and future Nobel prize winner, Kenneth Arrow defined a social welfare function as a function that maps any n-tuple of individual preference orders to a collective preference order. His axiomatic method outlined the requirements that any desirable social welfare function should satisfy.⁵ In 1950 he proved what still is the major result of social choice, the “General Possibility Theorem,” now better known as Arrow’s impossibly result⁶ [Arr50, Arr63]. The theorem shows that there exists no social welfare function that satisfies only just a small number of desirable conditions.

Let us informally present these conditions: the first is that a social welfare function must have a universal domain, that is, it has to accept as input any combination of individual preference orders. Another commonly accepted requirement is the Pareto condition, which states that, whenever all members of a society rank alternative x above alternative y, then the society must also prefer x to y. The independence of irrelevant alternatives condition states that the social preference over any two alternatives x and y must depend only on the individual preferences over those alternatives x and y (and not on other—irrelevant—alternatives).⁷ Finally, non-dictatorship requires that there exists no individual in the society such that, for any domain of the social welfare function, the collective preference is the same as that individual’s preference (i.e., the dictator). Arrow’s celebrated result shows that no social welfare function can jointly satisfy these conditions.⁸

1.2 A NEW TYPE OF AGGREGATION

1.2.1 FROM THE DOCTRINAL PARADOX TO THE DISCURSIVE DILEMMA

We have seen that, thanks to the Condorcet Jury Theorem, majority rule enjoys an attractive property: some conditions being satisfied, groups make better decisions than individuals. Yet, unfortunately, the Condorcet paradox also showed that this same rule is unable to ensure consistent social positions under all situations.

Classical social choice theoretic models focus on the aggregation of individual preferences into collective outcomes. Such models focus primarily on collective choices between alternative outcomes such as candidates, policies or actions. However, they do not capture decision problems in which a group has to form collectively endorsed beliefs or judgments on logically interconnected propositions. Such decision problems arise, for example, in expert panels, assemblies and decision-making bodies as well as artificial agents and distributed processes, seeking to aggregate diverse individual beliefs, judgments or viewpoints into a coherent collective opinion. Judgment aggregation fills this gap by extending earlier approaches developed by social choice theory for the aggregation of preferences.⁹

Doctrinal paradox

Judgment aggregation has its roots in jurisprudence. The paradox of a group of rational individuals collapsing into collective inconsistency made its first appearance in the legal literature, where constitutional courts are expected to provide reasons for their decisions. The discovery of the paradox was attributed to Kornhauser and Sager’s 1986 paper [KS86]. However, Elster recently pointed out that structurally similar problems have been first indicated by Poisson in 1837 [Els13]. What is now known as the doctrinal paradox [KS93, Kor92, Cha98] was rediscovered in 1921 by the Italian legal theorist Vacca [Vac21] (see [Spe09]), who consequently raised severe criticisms to the possibility of deriving collective judgments from individual opinions. The logical problem of aggregation was also noticed by Guilbaud [Gui52, Mon05], who gave a logical interpretation to preference aggregation.

Figure 1.4: An illustration of the doctrinal paradox.

In order to illustrate the doctrinal paradox, we recall the familiar example in the literature by Kornhauser and Sager [KS93]. A three-member court has to reach a verdict in a breach of contract case between a plaintiff and a defendant. According to the contract law, the defendant is liable (the conclusion, here denoted by proposition r) if and only if there was a valid contract and the defendant was in breach of it (the two premises, here denoted by propositions p and q respectively). Suppose that the three judges cast their votes as in Figure 1.4.

The court can rule on the case either directly, by taking the majority vote on the conclusion r regardless of how the judges voted on the premises (conclusion-based procedure) or indirectly, by taking the judges’ recommendations on the premises and inferring the court’s decision on r via the rule (p ∧ q) ↔ r that formalizes the contract law (premise-based procedure).¹⁰ The problem is that the court’s decision depends on the procedure adopted. In this specific example, under the conclusion-based procedure, the defendant will be declared not liable, whereas under the premise-based procedure, the defendant would be sentenced liable. As Kornhauser and Sager stated:

We have no clear understanding of how a court should proceed in cases where the doctrinal paradox arises. Worse, we have no systematic account of the collective nature of appellate adjudication to turn to in the effort to generate such an understanding. [KS93, p. 12]

Legal theorists have discussed both methods and have taken different positions about them, either by arguing for the superiority of one of the approaches or by questioning both and recommending a third way (see Nash [Nas03] for an overview of the proposed solutions). In particular, Kornhauser and Sager argue against the use of a uniform voting protocol and favor instead a context-sensitive approach, where courts choose the method on a case-by-case basis, by voting on the method to be applied.

Discursive dilemma

Judgment aggregation has provided a systematic account of situations like the one arising in Figure 1.4. The first step was made by the political philosopher Pettit [Pet01], who recognized that the paradox illustrates a more general problem than just an impasse in a court decision. Pettit introduced the term discursive dilemma to indicate any group decision in which the aggregation on the individual judgments depends on the chosen aggregation method, like the premise-based and the conclusion-based procedures.

Figure 1.5: The discursive dilemma.

Then, List and Pettit [LP04] reconstructed Kornhauser and Sager’s example as shown in Figure 1.5. The difference with Figure 1.4 is that here the legal doctrine has been added to the set of issues on which the judges have to vote. Now the discursive dilemma is characterized by the fact that the group reaches an inconsistent decision, like {p, q, (p ∧ q) ↔ r, ¬r}. The court would accept the legal doctrine, give a positive judgment on both premises p and q but, at the same time, reach a negative opinion on the conclusion r. Clearly, such a position is untenable, as it would amount to release the defendant while saying, at the same time, that the two conditions for the defendant’s liability applied.

What are the consequences of the reconstruction given in Figure 1.5? Mongin and Dietrich [MD10, Mon11] have investigated such reformulation and observed that:

[T]he discursive dilemma shifts the stress away from the conflict of methods to the logical contradiction within the total set of propositions that the group accepts. […] Trivial as this shift seems, it has far-reaching consequences, because all propositions are now being treated alike; indeed, the very distinction between premisses and conclusions vanishes. This may be a questionable simplification to make in the legal context, but if one is concerned with developing a general theory, the move has clear analytical advantages. [Mon11, p. 2]

Indeed, instead of premises and conclusions, List and Pettit chose to address the problem in terms of judgment sets, i.e., the sets of propositions accepted by the individual voters. The theory of judgment aggregation becomes then a formal investigation on the conditions under which consistent individual judgment sets may collapse into an inconsistent collective judgment set.

Exactly like Arrow’s theorem showed the full import of the Condorcet paradox, so showed the result of List and Pettit how far-reaching the doctrinal paradox and the discursive dilemma are. In the next section we will look at how the Condorcet paradox relates to these two paradoxes of the aggregation of judgments.

1.2.2 PREFERENCE AGGREGATION AND JUDGMENT AGGREGATION

Let us start by introducing some formal notation. Let X be a set of alternatives, and ≻ a binary predicate for a binary relation over X, where x ≻ y means “x is strictly preferable to y.” The desired properties of preference relations viewed as strict linear orders are:

Example 1.1 Condorcet paradox as a doctrinal paradox Suppose there are three possible alternatives x, y and z to choose from, and three voters V₁, V₂ and V₃ whose preferences are the same as in Figure 1.2. The three voters’ preferences can then be represented by sets of preferential judgments as follows: V₁ = {x ≻ y, y ≻ z, x ≻ z}, V₂ = {y ≻ z, z ≻ x, y ≻ x} and V₃ = {z ≻ x, x ≻ y, z ≻ y}. According to Condorcet’s method, a majority of the voters (V₁ and V₃) prefers x to y, a majority (V₁ and V₂) prefers y to z, and another majority (V₂ and V₃) prefers z to x. This leads us to the collective outcome {x ≻ y, y ≻ z, z ≻ x}, which together with transitivity (P3) violates (P1) (Figure 1.6). Each voter’s preference is transitive, but transitivity fails to be mirrored at the collective level. This is an instance of the Condorcet paradox casted in the form of a set of judgments over preferences on alternatives.¹¹

What the Condorcet paradox and the discursive dilemma have in common is that when we combine individual choices into a collective one, we may lose some rationality constraint that was satisfied at the individual level, like transitivity (in the case of preference aggregation) or logical consistency (in the case of judgment aggregation). A natural question is then how the theory of judgment aggregation and the theory of preference aggregation relate to one another. We can address this question in two ways: we can consider what the possible interpretations are of aggregating judgments and preferences, and we can investigate the formal relations between the two theories.

On the first consideration, Kornhauser and Sager see the possibility of being right or wrong as the discriminating factor between judgments and preferences:

When an individual expresses a preference, she is advancing a limited and sovereign claim. The claim is limited in the sense that it speaks only to her own values and advantage. The claim is sovereign in the sense that she is the final and authoritative arbiter of her preferences. The limited and sovereign attributes of a preference combine to make it perfectly possible for two individuals to disagree strongly in their preferences without either of them being wrong. […] In contrast, when an individual renders a judgment, she is advancing a claim that is neither limited nor sovereign. […] Two persons may disagree in their judgments, but when they do, each acknowledges that (at least) one of them is wrong. [KS86, p. 85].¹²

Figure 1.6: The Condorcet paradox as a doctrinal paradox.

Regarding the formal relations between judgment and preference aggregation, Dietrich and List [DL07a] (extending earlier work by List and Pettit [LP04]) capitalize on the representation of the Condorcet paradox given in Figure 1.6 and show that Arrow’s theorem for strict and complete preferences can be derived from an impossibility result in judgment aggregation.¹³

Despite these natural connections, and the formal results they support, Kornhauser and Sager [Kor92] notice that the two paradoxes do not perfectly match. Indeed, as stated also by List and Pettit:

[W]hen transcribed into the framework of preferences instances of the discursive dilemma do not always constitute instances of the Condorcet paradox; and equally instances of the Condorcet paradox do not always constitute instances of the discursive dilemma. [LP04, pp. 216–217]

Given the analogy between the two paradoxes, List and Pettit’s first question was whether an analogue of Arrow’s theorem could be found for the judgment aggregation problem. Arrow showed that the Condorcet paradox hides a much deeper problem that does not affect only the majority rule. The same question could be posed in judgment aggregation: is the doctrinal paradox only the surface of a more troublesome problem arising when individuals cast judgments on a given set of propositions? As we shall see in more detail in Chapter 3, the answer to this question is positive and that can be seen as the starting point of the theory of judgment aggregation.

How likely are majority cycles?

Even from our brief survey, the reader may have guessed that large parts of the literature in social choice theory focused on the problem of majority cycles. We may wonder how likely such cycles are in reality. There are two main approaches to this question in the literature. One consists in analytically deriving the probability of a Condorcet paradox in an election, while the other looks at empirical evidence in actual elections. One assumption usually made in the first approach is the so-called impartial culture. According to the impartial culture, each preference ordering is equally possible. It should be noted that, even though it is a useful assumption for the analytic calculations, such an assumption has often been criticized as unrealistic. Niemi and Weisberg [NW68] showed that, under the impartial culture assumption and for a large number of voters, the probability of a majority cycle approaches 1 as the number of alternatives increases. However, they also found out that the probability of the paradox is quite insensitive to the number of voters but depends highly on the number of alternatives.

Yet, these results are in contrast with the findings of the approach that looks at the actual elections.¹⁴ Mackie [Mac03], for example, claims that majority cycles never actually occurred in real elections. One way to explain such discrepancy is that we do not dispose of all the information needed to verify the occurrence of a majority cycle. For example, we typically do not dispose of the voter’s preference order over all the possible candidates.

1.3 FURTHER TOPICS

The brief survey on social choice theory provided in this chapter has no pretense to be exhaustive. The aim was to give a background against which to frame the birth and development of judgment aggregation. For a broader but still concise introduction to social choice theory see [Lisce], and [Nur10, Pacds] for an introduction to voting theory. Moreover, the reader is referred to [RVW11] for a survey on preference reasoning from a perspective that brings together social choice theory and artificial intelligence. In particular, Chapter 4 of [RVW11] focuses on preference aggregation. There, several voting rules are defined, and manipulation and computational aspects are discussed. Manipulation in judgment aggregation is the object of a separate chapter in the present book (Chapter 5).

If the traditional domain of social choice theory has been economics and the political sciences, attention in aggregation problems is witnessing a steady growth within the fields of artificial intelligence and multi-agent systems. Aggregation problems often appear in the design and specification of distributed intelligent systems and the very same idea of voting has been applied to problems like recommender systems [PHG00] and rank aggregation for the Web [DKNS01]. In particular, computational social choice [CELM07, BCE13], of which judgment aggregation can be seen as a contributing field, is the discipline stemmed from the interactions between computer science and social choice theory, and which studies, among other topics, the computational complexity of the application and manipulation of aggregation rules [EGP12],¹⁵ the design of aggregation rules based on knowledge representation techniques like merging [Pig06],¹⁶ or the application of logic to reason, within a formal language, about aggregation problems [AvdHW11].

¹Duncan Black (called the founder of social choice [Tul91] for being the first to really understand the work of Condorcet and discovering Dodgson’s papers) gave in [Bla58] an excellent historical overview of the mathematical theory of voting starting from Borda, Condorcet and Laplace and including Nanson, Galton and Dodgson.

²The same method was also suggested by Laplace in 1795, in a series of lectures he gave at the École Normale Superiéure in Paris.

³Manipulation will be the topic of Chapter 5.

⁴It is worth observing, in passing, that these two landmark results can be viewed as stemming from two different ways of conceiving democracy: the first one sees democracy as based on preferences, while the second sees it as based on knowledge (epistemic conception, as called in [Coh86, CF86]).

⁵See [Sup05] for a reconstruction of the intellectual path that led Arrow to introduce the axiomatic method in economics, and in particular Alfred Tarski’s influence, of whom Arrow attended a course in the calculus of relations as an undergraduate student.

⁶In Chapter 4 we will come back to the subtle relationships between impossibility and possibility theorems.

⁷This, as we shall see, is a more controversial requirement.

⁸It is impossible to underestimate the influence that Arrow’s theorem had in the development and foundation of social choice as a formal discipline. His result generated a vast literature, including many other impossibility results, like [Bla57, Sen69, Sen70, Pat71, Gib73, Sat75], to quote only few of them. Political scientists (most notably, William Riker [Rik82]) argued that Arrow’s findings posed serious threat to the theory of democracy.

⁹On the relations between judgment aggregation and preference aggregation, see Sections 1.2.2 and 3.4.

¹⁰The premise-based procedure has been reconsidered later as one of the possible escape routes from the many impossibility results that plague the discipline (see Section 4.3.1 later in the book).

¹¹We will come back later in Chapter 2 to another (logically simpler) formalization of the Condorcet paradox as a set of judgments about preferences (Example 2.15).

¹²Different procedures for judgment aggregation have been assessed with respect to their truth-tracking capabilities, see [BR06, HPS10].

¹³We will discuss this result in Chapter 3 (Section 3.4.1).

¹⁴See also [RGMT06] for an introduction to behavioral social choice.

¹⁵We will touch upon this topic in Chapter 5 (Section 5.3.3).

¹⁶We will discuss this topic in detail in Chapter 4 (Section 4.3.3) and Chapter 6.