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

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.¹ 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 φ”), φ ∧ ψ (“φ and ψ”), φ ∨ ψ (“φ or ψ”), φ → ψ (“if φ then ψ”), and φ ↔ ψ (“φ if and only if ψ”) belong to L, and nothing else belongs to L.² We say that a formula is positive if its outermost connective is not a negation (e.g., p → q, ¬p ∨ q).³

The meaning of a formula φ ∈ At is its truth value as specified by a valuation function V : L → {0, 1} where 0 stands for “false” and 1 for “true.” Each valuation V is an extension of some valuation V : At → {0, 1} of truth values to atoms, which obeys the following constraints: . These constraints define the semantics of the logical connectives introduced above. When V(φ) = 1 (respectively, V(φ) = 0) we will often write V ⊨ φ (respectively, V ⊭ φ). If Φ is a set of formulae, we write V ⊨ Φ to express that for all φ ∈ Φ, V ⊨ φ, i.e., all formulae in φ are made true by V.

We conclude with some auxiliary terminology concerning special classes of propositional formulae. A formula φ is a tautology if, for any valuation V, V ⊨ φ; it is a contradiction if, for any valuation V, V ⊭ φ; it is contingent if it is neither a tautology nor a contradiction. A set of formulae Φ is consistent if it has a model, that is, if there exists a valuation V, such that V ⊨ φ for each φ ∈ Φ; a formula φ is a logical consequence of a set of formulae Φ (in symbols, Φ ⊨ φ) if for every valuation V such that V ⊨ Φ, it is the case that V ⊨ φ

Agendas

With the machinery of propositional logic in place, we can frame the problem of the aggregation of judgments simply as a set of individuals or agents that are called to decide upon a given set of issues:

Definition 2.1 Judgment aggregation problem. Let L be a propositional language on a given set of atoms At. A judgment aggregation problem for L is a tuple J = 〈N, A〉 where:

• N is a finite non-empty set;

• A ⊆ L such that for some finite I ⊆ L which contains only positive contingent formulae.

Set N is the set of individuals (or agents or voters). A is called the agenda and I is called the set of issues or the pre-agenda of A. An agenda based on a set of issues I will often be denoted ±I. Given an agenda A, we denote its pre-agenda by [A].⁴

Intuitively, one can view a judgment aggregation problem as what specifies the space of possible situations in which the individuals in N have to reach some collective decision about the issues in I. An agenda A = ±I represents then all possible attitudes that can be assumed toward the issues in I. In the framework we are going to work with, such attitudes are of only two types: acceptance and rejection. The agenda is therefore a set of formulae which is closed under negation, i.e., ∀φ: φ ∈ A iff ¬φ ∈ A, and where double negations are eliminated. To make an example, the doctrinal paradox agenda expresses all the acceptance/rejection attitudes that one individual can assume over the set of issues {p, q, p ∧ q}.

2.1.2 JUDGMENT SETS AND PROFILES

Given a judgment aggregation problem, individuals are asked to express their opinions on the formulae of the agenda by accepting some and rejecting others. These opinions are called judgment sets and are defined as follows:

Definition 2.2 Judgment sets and profiles. Let J = 〈N, A〉 be a judgment aggregation problem. A judgment set for J is a set of formulae J ⊆ A such that:

• J is consistent;

• J is complete, i.e., ∀φ ∈ A, either φ ∈ J or ¬φ ∈ J.

Instead of φ ∈ J we will often use the notation J ⊨ φ to indicate that φ belongs to judgment set J.⁵ The set of all judgment sets is denoted where denotes the power-set function. A judgment profile is an |N|-tuple of judgment sets. With Pi we denote the i^th entry of P, i.e., the judgment set of agent i in P. For φ ∈ A, we use Pφ to denote the set of individuals accepting φ in . Finally, we denote with P the set of all judgment profiles. Abusing notation, we will sometimes indicate that a judgment set Ji belongs to a profile P by writing Ji ∈ P.

So individuals express their opinions through sets of formulae of the agenda: the formulae contained in the set are the ones that are accepted by the individual, the ones belonging to the complement of the set are the ones that are rejected by the individual. The consistency and completeness criteria formalize a notion of ‘rationality’ for the views that might be held by individuals. Such views cannot be internally contradictory (consistency) and cannot abstain from accepting or rejecting any of the issues posed by the agenda (completeness).⁶

Remark 2.3 Deductive closure A set of formulae Φ is deductively closed (w.r.t. agenda A) if any φ ∈ A that follows logically from Φ is also contained in it: if Φ ⊨ φ, then φ ∈ Φ. Since judgment sets are sets of formulae that are consistent and complete, they are also deductively closed. However, a set of formulae that is consistent and deductively closed is not necessarily complete. When working with judgment sets the two notations φ ∈ J (membership) and J ⊨ φ (consequence) can be seen as notational variants. However, when working with sets of formulae that are not judgment sets by the letter of Definition 2.2—in our context these will typically be sets of formulae accepted by a group of individuals—we will keep the two notations distinct.

2.1.3 AGGREGATION FUNCTIONS

The judgment aggregation problem consists in the aggregation of the individuals’ judgment sets into one collective judgment set. The aggregation of individual judgments is viewed as a function:

Definition 2.4 Aggregation function. Let J = 〈N, A〉 be a judgment aggregation problem. An aggregation function for J is a function . The output set f(P), where , is sometimes denoted J. Set J is then called a collective set. A collective set J which is a judgment set is called a collective judgment set.

So, an aggregation function takes as input a profile of consistent and complete subsets of the agenda (i.e., judgment sets) and outputs a subset of the agenda. Such subset is neither necessarily consistent nor necessarily complete. In other words, the collective set is not necessarily a judgment set. In view of our discussion of the doctrinal paradox and the discursive dilemma this should not come as a surprise: the output of an aggregation function might not be ‘rational’ in the sense in which individual judgment sets are.

Remark 2.5 Universal domain and resoluteness We conclude our comment of Definition 2.4 by noticing that it builds two key properties into the notion of aggregation function. First, it assumes that the domain of the aggregation consists of all possible judgment profiles or, intuitively, that all profiles of individual opinions are admissible as input for the aggregation. This property is commonly referred to as universal domain. Second, it assumes the aggregation to be resolute, that is, to yield for each profile only one set of formulae. In this book we will work almost exclusively with functions that satisfy universal domain and resoluteness. Aggregation functions that do not satisfy universal domain will be presented later in Chapter 4. Irresolute functions yielding for each profile a non-empty set of sets of formulae will be studied later in Chapter 4 and especially in Chapter 6.

2.1.4 EXAMPLES: AGGREGATION RULES

We now give several examples of aggregation functions as rules for defining the collective set based on a judgment profile. We typically refer to concrete aggregation functions as aggregation rules. The ones that follow in this section will be discussed at several places throughout the book and are the ones most commonly considered in the literature.

Threshold-based rules

The rules below determine the collective outcome by checking, for each proposition in the agenda (they are therefore commonly referred to as propositionwise rules), whether the number of individuals accepting that formula exceeds a given threshold. If that is the case, the formula is collectively accepted. Let P ∈ P, we define the following rules.

Majority rule:

where, for x ∈ Q, ⌈x⌉ is the smallest integer greater or equal to x. I.e., φ is collectively accepted iff there is a majority of individuals accepting it. We will refer to this rule as the propositionwise majority rule or simply as the majority rule.

Unanimity rule:

I.e., φ is collectively accepted iff all individuals accept it. We will refer to this rule as the propositionwise unanimity rule or simply as the unanimity rule.

Quota rule:

where is a tuple of integer thresholds or quotas t_φ, one for each formula in the agenda. I.e., φ is collectively accepted iff there are at least t_φ individuals that accept it.

Formula 2.3 defines the class of all propositionwise threshold-based rules. Clearly, the propositionwise majority rule is a particular quota rule whose threshold has been fixed at for all formulae in the agenda.⁷ Similarly, the unanimity rule is a quota rule with threshold |N| for all formulae. Quota rules that assign the same threshold to all formulae called uniform.

It must be noted that the selection of the thresholds has an impact on the ‘rationality’ of the collective set. For instance, it is not difficult to see that the unanimity rule might return incomplete collective sets, and that a uniform quota rule imposing a common threshold lower than might return collective sets containing both a formula and its negation. In general, one can identify precise constraints on the thresholds, which can enforce a well-behaved output of the aggregation. For instance, for each pair φ and ¬φ, the inequalities

are necessary and sufficient conditions for the collective set to be complete (i.e., to contain at least one of φ or ¬φ, Formula 2.4) and, respectively, to be such that it never contains both a formula and its negation (i.e., to contain at most one of φ and ¬φ, Formula 2.5). This latter property is usually referred to as weak consistency.

The class of all quota rules has been studied extensively in [DL07b]. We will come back to the majority rule in much more detail later in Chapter 3, and to quota rules as possible escape routes to some of the impossibility results of judgment aggregation in Chapters 4 and 5.⁸

Premise- and conclusion-based rules

We have already encountered the premise- and conclusion-based rules in Section 1.2. Here we give a more precise formulation of them.

Premise-based rule:

where: Prem ⊆ A consists of the subagenda containing the issues that are considered premises in the aggregation, and their negations; Conc ⊆ A consists of the subagenda containing the issues that are considered conclusions in the aggregation, and their negations; Prem and Conc are a partition of A; and PPrem (respectively, P^Conc) denotes the profile obtained from the restrictions of the judgment sets to the formulae in Prem (respectively, Conc). I.e., φ is collectively accepted iff it is a premise and it has been voted by the majority of the individuals or it is a conclusion entailed by the premises accepted by the majority.

Conclusion-based rule:

where PConc is as for the premise-based rule. I.e., φ is collectively accepted iff it is a conclusion and it has been voted by the majority of the individuals.

Intuitively, premise- and conclusion-based rules apply propositionwise aggregation, via the majority rule, only to specific subsets of the agenda, viz., its premises or its conclusions. They have played a pivotal role in the development of the theory of judgment aggregation, and much literature has been dedicated to their analysis (see, for instance, [NP06, DM10]). We will come back to them at several places in the remaining of the book.

An example

It is now time to illustrate the workings of all the above rules side by side. We do that with yet another variant of the doctrinal paradox:

Example 2.6 Let A = ±{p, p → q, q}, and attach the following intuitive reading to the three issues [DL07a]:

Figure 2.1: An illustration of several aggregation rules from Example 2.6.

p: Current CO₂ emissions lead to global warming.

p → q: If current CO₂ emissions lead to global warming, then we should reduce CO₂ emissions.

q: We should reduce CO₂ emissions.

The profile consisting of the three judgment sets and , once aggregated via propositionwise majority (fmaj), gives rise to an inconsistent collective judgment set . Propositionwise unanimity (fu) does not accept any of the items of the agenda. If we assume that Prem = {p, p → q} and Conc = {q}, the premise-based rule (fpb) generates a collective judgment accepting all items, and the conclusion-based rule (fcb) rejects the conclusion q, and does not accept any other item of the agenda.

We give two examples of quota rules. The first is a quota rule that requires majority over the premises and their negations, but requires a unanimous vote to collectively accept the positive conclusion and one individual to reject it. That is: .⁹ This quota rule accepts both premises but rejects the conclusion. The second one requires majority on all atomic issues and unanimity on the implicative issues.¹⁰ That is: and .¹¹ This rule then accepts one premise but rejects the implicative premise and the conclusion. Figure 2.1 recapitulates the outputs just discussed.

It is no accident that all aggregation rules in the above example either fail to yield a judgment set (all except fpb and ft″, whose output is consistent and complete) or output sets that are inconsistent with one another (fpb accepts q while fcb and ft″ reject it). The reasons for such failure are deep and we will probe them in Chapter 3. The remainder of the present chapter sets the stage for those investigations.

2.2 AGENDA CONDITIONS

We introduce here three conditions on agendas, which capture the sort of logical interdependence possibly arising between their elements.

2.2.1 HOW INTERCONNECTED IS AN AGENDA?

We define and illustrate the agenda conditions known as non-simplicity, even-negatability and path-connectedness. We also introduce the auxiliary notion of conditional entailment.

Non-simplicity

The first agenda condition is almost self-explanatory, and is usually referred to as non-simplicity [NP07].

Definition 2.7 Non-simple agendas. An agenda A is non-simple (NS) iff it contains at least one set X s.t.:

• 3 ≤ |X|;

• X is minimally inconsistent, i.e.:

– X is inconsistent;

– ∀Y S.T. Y ⊂ X : Y is consistent.

An agenda is called simple if it is not non-simple.

It is easy to see that agenda ±{p, q, p ∧ q} is non-simple as the set {p, q, ¬(p ∧ q)} is clearly minimally inconsistent. Notice that if X is minimally inconsistent then, for some φ ∈ X, it is not only the case that X − {φ} is consistent, but also that X − {φ} ⊨ ¬φ. Non-simplicity is the minimal level of complexity for an agenda to run into problems when attempting aggregation.

On the other hand, we will see that if an agenda is simple then aggregations of a non-degenerate kind are possible. In fact, the propositionwise majority rule can be proven to be the unique aggregation function that satisfies some highly desirable properties.¹² By Definition 2.7, simple agendas are agendas where minimally inconsistent sets have cardinality of at most two.¹³ Examples are agendas whose issues consist of logically unrelated formulae (e.g., {p, q, r}),¹⁴ or agendas whose issues can be ordered by logical strength like ±{p, p ∧ q, p ∧ q ∧ r}.

Conditional entailment

From non-simplicity we move now to the related notion of conditional entailment [DL13a]. This will be needed later to define the condition of path-connectedness.

Definition 2.8 Conditional entailment. Let φ, ψ ∈ A. We say that φ conditionally entails ψ (notation: φ ⊨_c ψ) if for some (possibly empty) X ⊆ A, which is consistent with φ and with ¬ψ, {φ} ∪ X ⊨ ψ.

Conditional entailment expresses that the acceptance of ψ follows from the acceptance of φ either directly—by logical consequence—or indirectly once a set of formulae X is also accepted, which is compatible with both the acceptance of φ and the rejection of ψ. Intuitively, the fact that φ conditionally implies ψ captures a specific dependency within the structure of the agenda whereby if, on the one hand, it is possible to accept both φ and the formulae in X or both X and ¬ψ, on the other hand, accepting φ and X would compel one to also accept ψ.

A few observations are in order. If φ ⊨ ψ (i.e., ψ is a logical consequence of φ) then φ ⊨_c ψ since ψ follows from {φ} ∪ Ø. If an agenda contains φ ≠ ψ such that φ ⊨_c ψ, then the agenda must have been generated by a set of issues containing at least two formulae. We conclude with the following observation relating conditional entailment to the property of non-simplicity:

Fact 2.9 Conditional entailment and NS Let A be an agenda and φ, ψ ∈ A. If (i) φ ⊨_c ψ and (ii) φ ⊭ ψ, then A satisfies NS.

Proof. By (i), (ii) and Definition 2.8 it follows that there exists X ≠ Ø such that {φ} ∪ X ⊨ ψ and hence such that X ∪ {φ, ¬ψ} is inconsistent. By the compactness¹⁵ of propositional logic there exists a smallest non-empty X′ such that X′ ∪ {φ, ¬ψ} is inconsistent. Set X′ ∪ {φ, ¬ψ} is therefore minimally inconsistent and has cardinality bigger or equal to 3. Hence A satisfies NS.

□

Even negations

The second agenda condition is known as even negatability or even number negations property, and is slightly more involved:

Definition 2.10 Evenly negatable agendas. An agenda A satisfies the even negations condition (EN) iff:

• A contains a minimally inconsistent set X ⊆ A and a set Y = {φ, ψ} ⊆ X, such that X − Y ∪ {¬φ, ¬ψ} is consistent.¹⁶