Judgment Aggregation. Gabriella Pigozzi
Читать онлайн книгу.
Yet, these results are in contrast with the findings of the approach that looks at the actual elections.14 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],15 the design of aggregation rules based on knowledge representation techniques like merging [Pig06],16 or the application of logic to reason, within a formal language, about aggregation problems [AvdHW11].
1Duncan 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.
2The same method was also suggested by Laplace in 1795, in a series of lectures he gave at the École Normale Superiéure in Paris.
3Manipulation will be the topic of Chapter 5.
4It 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]).
5See [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.
6In Chapter 4 we will come back to the subtle relationships between impossibility and possibility theorems.
7This, as we shall see, is a more controversial requirement.
8It 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.
9On the relations between judgment aggregation and preference aggregation, see Sections 1.2.2 and 3.4.
10The 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).
11We 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).
12Different procedures for judgment aggregation have been assessed with respect to their truth-tracking capabilities, see [BR06, HPS10].
13We will discuss this result in Chapter 3 (Section 3.4.1).
14See also [RGMT06] for an introduction to behavioral social choice.
15We will touch upon this topic in Chapter 5 (Section 5.3.3).
16We will discuss this topic in detail in Chapter 4 (Section 4.3.3) and Chapter 6.
CHAPTER 2
Basic Concepts
This chapter is devoted to an introduction of the basic framework of judgment aggregation based on propositional logic. Our presentation is based on the framework first proposed in [LP02] and later developed by Dietrich and List in a long series of works (e.g., [DL07a, DL07c] to name just a few).
Chapter outline: We start in Section 2.1 by introducing the notions of agenda, judgment set, judgment profile, and aggregation function. In the same section we will also define a number of concrete aggregation functions. Section 2.2 proceeds by defining some properties of agendas, which have to do with how ‘tightly’ the formulae in the agenda are logically related to one another. We will see later that the more interconnected an agenda is, the more difficult the aggregation problem becomes. In Section 2.3 we look into a set of natural properties that one might wish to impose on the aggregation function to guarantee its ‘good’ behavior. In the concluding section we refer the reader to alternative formal frameworks—not necessarily based on logic—that have been developed in the literature to cast the theory of judgment aggregation.
2.1 PRELIMINARIES
2.1.1 AGENDAS IN PROPOSITIONAL LOGIC
In this book we will only be concerned with the aggregation of judgments that are expressed in propositional logic, which has been the framework of choice for most of the literature.1 So we start by briefly recapitulating—for the readers unfamiliar with propositional logic—some basic notions from its syntax and semantics. For a comprehensive exposition the reader is referred to [vD80, Ch. 1].
Propositional logic
The language of propositional logic, which we denote by L, consists of all the formulae that can be defined inductively from a countable set At = {p, q, …} of atomic propositions (also called atoms) using the logical connectives ¬ (negation), ∧ (conjunction), ∨ (disjunction), → (implication), ↔ (equivalence). The inductive definition goes as follows: [Base] all elements of At are formulae in L; [Step] if φ and ψ belong to L, then also ¬φ (“not φ”), φ ∧ ψ