# agenda_separability_in_judgment_aggregation__4702e4db.pdf

Agenda Separability in Judgment Aggregation

J erˆome Lang and Marija Slavkovik and Srdjan Vesic LAMSADE, CNRS University of Paris-Dauphine, France, lang@lamsade.dauphine.fr University of Bergen, Norway, marija.slavkovik@uib.no CRIL, CNRS Univ. Artois, France, vesic@cril.fr

One of the better studied properties for operators in judgment aggregation is independence, which essentially dictates that the collective judgment on one issue should not depend on the individual judgments given on some other issue(s) in the same agenda. Independence, although considered a desirable property, is too strong, because together with mild additional conditions it implies dictatorship. We propose here a weakening of independence, named agenda separability: a judgment aggregation rule satisfies it if, whenever the agenda is composed of several independent sub-agendas, the resulting collective judgment sets can be computed separately for each sub-agenda and then put together. We show that this property is discriminant, in the sense that among judgment aggregation rules so far studied in the literature, some satisfy it and some do not. We briefly discuss the implications of agenda separability on the computation of judgment aggregation rules.

1 Introduction

Judgment aggregation consists in finding collective judgments that are representative of a collection of individual judgments on some logically interrelated issues. Judgment aggregation problems originate in political theory and public choice, however they also occur in various areas of artificial intelligence, as a consequence of the increased distributivity of computing systems and social networks, together with the rise of artificial agency. Judgment aggregation generalises voting and preference aggregation (Dietrich and List 2007a; Lang and Slavkovik 2013), and has links with belief revision (Everaere, Konieczny, and Marquis 2015; Pigozzi 2006) as well as abstract argumentation (Caminada and Pigozzi 2011; Awas et al. 2015; Booth 2015; Booth, Awad, and Rahwan 2014). For an overview of applications of judgment aggregation in artificial intelligence see for instance the work by Grossi and Pigozzi (2014) or Endriss (2015). The main focus of research in judgment aggregation is the development and analysis of judgement aggregation operators. Numerous impossibility results see the survey by List and Puppe (2009) for an overview have dashed the hope of finding a universally applicable operator. Consequently, the suitability of an operator for a given judgment aggrega-

Copyright c 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

tion problem has to be identified with respect to the desirable properties that the aggregation process should satisfy. One of the better studied properties for operators in judgment aggregation is the independence property, which essentially dictates that the collective judgment on any one issue in the agenda should not depend on the individual judgments given on any of the other issues in the same agenda. Independence is a desirable property because, among other reasons, it is a necessary condition for strategyproofness (Dietrich and List 2007c), and it leads to rules that are both conceptually simple and easy to compute. However, independence is too strong; in particular, together with mild additional conditions, it implies dictatorship (Dietrich and List 2007a). We propose a natural weakening of independence, named agenda separability. A judgment aggregation rule satisfies it if, whenever the agenda is composed of several independent sub-agendas (with an extreme form of independence being when the sub-agendas are syntactically unrelated to each other), the resulting collective judgment sets can be computed separately for each sub-agenda and then put together. Resorting to syntactically independent sub-languages is reminiscent of Parikh s language splitting (Parikh 1999), where decomposing a logical theory into several subtheories over disjoint sub-languages simplifies many tasks in knowledge representation, such as belief change (Peppas, Chopra, and Foo 2004) or inconsistency handling (Chopra and Parikh 1999). The agenda separability property is very intuitive and motivations for it can be easily found. For instance, in computational linguistics, we may want to aggregate annotations from several agents about parts of texts (Kruger et al. 2014); then, finding collective annotations about parts of two unrelated texts can (and should) be performed independently. When a rule satisfies agenda separability, it also becomes computationally simpler when applied to decomposable agendas, because the rule can be applied independently to every subagenda of the decomposition. Agenda separability also offers a weak form of strategyproofness: no agent is able to influence the outcome on some issue from one subagenda of the partition by strategically reporting judgments about another subagenda. Of course, a weakening of independence is meaningful only if there are rules that satisfy it. Not only we show that this is the case, but we also show that agenda separability

Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16)

is discriminant, in the sense that among the known judgment aggregation rules, some satisfy it and some do not. This leads us to see agenda independence as a possible means of choosing a judgment aggregation rule against another. The paper is structured as follows. Section 2 introduces the background. Section 3 discusses the independence property. In Sections 4 and 5 we define two notions of agenda separability, and we identify some rules that satisfy them and some that do not. Section 6 contains a summary and discussion.

2 Preliminaries

Let L be a set of well-formed propositional logical formulas, including (tautology) and (contradiction). An issue is a pair of formulas ϕ, ϕ where ϕ L and ϕ is neither a tautology nor a contradiction. An agenda A is a finite set of issues and has the form A = {ϕ1, ϕ1, . . . , ϕm, ϕm}. The preagenda [A] associated with A is [A] = {ϕ1, . . . , ϕm}. A sub-agenda is a subset of issues from A. A sub-preagenda is a subset of [A]. An agenda usually comes with an integrity constraint Γ, which is a consistent formula whose role is to filter out inadmissible judgment sets. (A, Γ) is called a constrained agenda. As a classical example, given a set of candidates C = {x1, . . . , xm}, the preference agenda over C (Dietrich and List 2007a) is AC = {xi Pxj|1 i < j m}, and the associated integrity constraint is ΓC =

i,j,k (xi Pxj xj Pxk xi Pxk). When Γ is not specified, by default it is equal to . A judgment on ϕ [A] is one of ϕ or ϕ. A judgment set J is a subset of A. J is complete iff for each ϕ [A], either ϕ J or ϕ J. A judgment set J (and in general, a set of propositional formulas) is Γ-consistent if and only if J {Γ} . Let JA,Γ be the set of all complete and consistent judgment sets. To lighten the notations, we will generally say that a judgment set is consistent instead of Γconsistent, and note JA instead of JA,Γ. A profile P = J1, . . . , Jn J n A is a collection of complete and consistent individual judgment sets. We further define N(P, ϕ) = |{i | ϕ Ji}| to be the number of all agents in P whose judgment set includes ϕ. The order P is the weak order over A defined by ϕ P φ if and only if N(P, ϕ) N(P, φ). The restriction of P = J1, . . . , Jn over a sub-agenda A1 of A is defined as P A1 = J1 A1, . . . , Jn A1 . Every consistent subset of the agenda S A can be extended in order to obtain a complete judgment set (there might be several such extensions). For a set S of subsets of agenda , we define ext(S) = {J JA | there exists J S such that J J}. A judgment aggregation rule, for n agents, is a function R that maps any constrained agenda (A, Γ) and any profile P J n A,Γ to a non-empty set of complete consistent judgment sets over A.1 If R always outputs a singleton then it

1The reason why the (constrained) agenda is an argument of rules is that the notions we study need a rule to be applied to a variable agenda. We omit writing A, Γ as an argument of R when defining R to improve the readability of the text.

is called a resolute rule. The majoritarian judgment set associated with profile P contains all elements of the agenda that are supported by a majority of judgment sets in P: m(P) = {ϕ A | N(P, ϕ) > n

2 }. A profile P is majorityconsistent iff m(P) is consistent. Let S L. We define Atoms(S) as the set of all propositional variables appearing in S. For example, Atoms({p, q r, s p}) = {p, q, r, s}. Given a set of formulas S and a formula Γ, S S is Γ-consistent if S {Γ} is consistent, S is a maximal Γconsistent subset of S, if S is Γ-consistent and there is no S S , S S that is Γ-consistent. . We use max(S, ) to denote the maximal consistent subsets of S. The set S S is a maxcard Γ-consistent subset of S if S is Γ-consistent and there exists no Γ-consistent set S S such that |S | < |S |. We use max(S, |.|) to denote the maxcard consistent subsets of S. We now give the definitions of seven judgment aggregation rules. They come from various places in the literature, where they sometimes appear with different names (Lang et al. 2011; Lang and Slavkovik 2013; Nehring and Pivato 2013; Nehring, Pivato, and Puppe 2014; Miller and Osherson 2009; Everaere, Konieczny, and Marquis 2014). Throughout the subsection, P = J1, . . . , Jn is a profile. For two consistent and complete judgment sets J, J we denote their Hamming distance as d H(J, J ) = |J \ J |.

MC, MCC. The maximum Condorcet rule (MC) and the maxcard Condorcet rule (MCC) rules are defined as follows. For every agenda A, for every profile P J n A, MC(P) = {ext(S) | S max(m(P), )} and MCC(P) = {ext(S) | S max(m(P), |.|)}.

RA. For A = {ψ1, . . . , ψ2m} and a permutation σ of {1, . . . , 2m}, let >σ be the linear order on A defined by ψσ(1) >σ ... >σ ψσ(2m). We say that >σ is compatible with P if ψσ(1) P ... P ψσ(2m). The ranked agenda rule RA is defined as J RA(P) if and only if there exists a permutation σ such that >σ is compatible with P and such that J = Jσ is obtained by the following procedure:

S := ; for j = 1, . . . , 2m do if S {ψσ(j)} is consistent, let S := S {ψσ(j)}; Jσ := S.

Rd H,MAX(P) = argmin J JA

n max i=1 d H(Ji, J).

RS. A scoring function (Dietrich 2014) is defined as s : JA A R+. Given a scoring function s, the judgment aggregation rule Rs is defined as RS(P) = argmax J JA

ϕ J s(Ji, ϕ). If we choose the

reversal scoring function srev(Ji, ϕ) as the minimal number of judgment reversals needed in Ji in order to reject ϕ then we get the reversal scoring rule Rrev (Dietrich 2014). If we choose the scoring function s defined by smed(Ji, ϕ) = 1 if ϕ Ji and 0 if ϕ / Ji then Rs is exactly the median rule, i.e. Rs MED.

argmax J JA

ϕ J N(P, ϕ) = argmin J JA

Ji P d H(Ji, J).

FULLH. Given profiles P = J1, . . . , Jn and Q =

J 1, . . . , J n in J n A, let DH(P, Q) = n

i=1 d H(Ji, J i).

FULLH(P) = {ext(m(Q)) | Q argmin Q J n A DH(P, Q )}.

The rules defined here are irresolute, but similarly as in voting theory, can be made resolute by composing them with a tie-breaking mechanism. A simple way of defining a tiebreaking mechanism θ is via a priority relation >θ over consistent and complete judgment sets. Given an irresolute rule R and a tie-breaking mechanism θ, the resolute rule Rθ is the rule that, given P, returns the maximal (with respect to >θ) element of R(P).

3 Relaxing Independence

A judgment aggregation rule F satisfies independence of irrelevant alternatives (IIA) if for every two profiles P, P J n A, and every ϕ A, if P {ϕ, ϕ} = P {ϕ, ϕ}, then ϕ F(P) iff ϕ F(P ). Independence is a very strong property: together with three seemingly innocuous properties, namely universal domain (F is defined for every profile), unanimity principle, and collective rationality (F outputs complete and consistent judgment sets), it implies dictatorship (Dietrich and List 2007a). Now, while it is natural to expect that the individual judgments on logically related issues will influence the choice of collective judgments for those issues, it is also natural to expect that individual judgments over logically unrelated issues will have no impact on them. To illustrate this point, we give an example from a collective decision making problem that occurs in crowdcomputing. There are a lot of tasks that are rather simple for a human to do, but fairly complicated for a computer, such as labelling images, choosing the best out of several images, identifying music segments etc. These types of tasks are called human intelligence tasks (HITs). Considering the task of cataloguing pictures by location, that is outsourced as HITs to an unspecified, but finite, group of people. The people undertaking these tasks should label each photo in a series and also indicate reasons for their labelling. For example: the photo is of Paris (p) if the Eiffel tower can be seen on it (e) or the Triumphal arc can be seen on it (t); the photo is of Rome (r) if the Colosseum can be seen on it (c) or the Spanish Steps can be seen on it (s). The commissioner of the HITs will aggregate the individual labelings and assign the labels that are collectively supported. The problem of finding which labelings are collectively supported can be solved as a judgment aggregation problem; see the work by Endriss and Fern andez (2013) for a similar view of crowdsourcing as a judgment aggregation problem. Assume, for simplicity, that we have three labellers (or agents) and two pictures. Furthermore, the commissioner is only interested in whether the first photo is of Paris and whether

the second one is of Rome. The problem for the first photo is represented with the agenda [A1] = {p, e, t, e t p}, while the problem for the second photo is represented with the agenda [A2] = {r, c, s, c s r}. Observe that Atoms(A1) Atoms(A2) = . The agents get the pictures at the same time. Clearly, whether the first picture is of Paris or not has nothing to do with whether the second picture is of Rome or not, consequently we would expect that the collective judgments regarding issues in A1 depend only on the judgments given for these issues, but not on the individual judgments given for issues in A2. In the next section we relax independence along this principle, defining a new property called agenda separability.

4 Agenda Separability

Following the idea that only judgments on logically related issues should influence the collective judgment on each issue, we define agenda separability as the property requiring that when two agendas can be split into sub-agendas that are independent from each other, the output judgment sets can be obtained by first applying the rule on each sub-agenda separately and then taking the pairwise unions of judgment sets from the two resulting sets. A partition {A1, A2} of A is an independent partition of A if for every J1 JA1 and J2 JA2, J1 J2 is Γconsistent.2

Definition 1 (Agenda separability) We say that rule R satisfies agenda separability (AS) if for every agenda A, every independent partition {A1, A2} of A, and all profiles P J n A, we have

R(P) = {J1 J2 | J1 R(P A1) and J2 R(P A2)}.

If R is a resolute rule, then the last line of the definition simplifies into R(P) = R(P A1) R(P A2). Also, by associativity of , this notion generalises to agendas that can be partitioned into a collection {A1, . . . , Ak} such that for every J1 JA1, . . . , Jk JAk, J1 . . . Jk is consistent. In that case,

i=1 Ji J1 R(P A1), . . . , Jk R(P Ak)

IIA is defined for resolute rules only. We show that agenda separability restricted to resolute rules is a weakening of IIA.

Proposition 1 Any resolute judgment aggregation rule that satisfies IIA is agenda separable.

2A stronger notion of independence, which makes sense only when Γ = , is syntactical agenda independence: a partition {A1, A2} of A is syntactically independent if Atoms(A1) Atoms(A2) = . Clearly, syntactical agenda independence implies agenda independence, because Atoms(A1) Atoms(A2) = implies that A1 and A2 are independent. Note that the implication is strict: for example, let A = {x, x, x y, (x y)} = A1 A2, Γ = , A1 = {x, x} and A2 = {x y, (x y)}. {A1, A2} is an independent partition of A although Atoms(A1) Atoms(A2) = .

Proof. If a resolute rule R satisfies IIA, we can write R(P) = m i=1 Fi(P {ϕi, ϕi}) where [A] = {ϕ1, . . . ϕm} and F1, . . . , Fm are resolute rules. Let {A1, A2} be an independent partition of A. Without loss of generality, assume [A1] = {ϕ1, . . . , ϕk} and [A2] = {ϕk+1, . . . , ϕm}. We have R(P) = k i=1 Fi(P {ϕi, ϕi}) m i=k+1 Fi(P {ϕi, ϕi}) = R(P A1) R(P A2).

We shall see that the reverse implication does not hold.

Definition 2 The scoring function s is separable if for every A and every independent partition {A1, A2} of A, for i {1, 2}, and every J JA and ϕ Ai, we have s(J, ϕ) = s(J Ai, ϕ).

We omit the easy proofs of the next two results.

Proposition 2 If s is a separable scoring function, then RS is agenda separable.

Corollary 1 MED and Rrev are agenda separable.

Proposition 3 MC, MCC, RA, and FULLH are agenda separable. Rd H,MAX is not agenda separable.

Proof. For MC and RA, this will be a consequence of a stronger result proven in Section 5, therefore we give a proof only for MCC and FULLH. Let {A1, A2} be an independent partition of A. MCC. Denote B1 = m(P1), B2 = m(P2) and B = m(P). Let ΠP1,P2 = {J1 J2 | J1 MCC(P1) and J2 MCC(P2)}. We first show that MCC(P) ΠP1,P2. Let J

MCC(P); thus J ext(max(B, |.|)). Let J1 = J A1 and J2 = J A2. J1 and J2 are consistent, because J is consistent. Assume J1 / ext(max(B1, |.|)). Since J1 is consistent, there exists J1 ext(max(B1, |.|)) such that |J1 | > |J1 |. Let J = J1 J2 . Because {A1, A2} is an independent partition of A, the consistency of J1 and of J2 implies the consistency of J . But then |J | > |J |, which contradicts J ext(max(B, |.|)). Therefore, J1 ext(max(B1, |.|)). Similarly, J2 ext(max(B2, |.|)). Thus, J ΠP1,P2. Now we show that ΠP1,P2 MCC(P). Let J1

MCC(P1) and J2 MCC(P2), that is, J1 ext(max(B1, |.|)) and J2 ext(max(B2, |.|)). Let us show that J = J1 J2 ext(max(B, |.|)). Because {A1, A2} is an independent partition of A, J is consistent. Suppose that there exists J ext(max(B, |.|)) such that |J | > |J|. Let J1 = J B1 and J2 = J B2. Both J1 and J2 are consistent, and |J | > |J| implies that |J1 | > |J1 | or |J2 | > |J2 |, which contradicts J1 / ext(max(B1, |.|)) and J2 / ext(max(B2, |.|)). Thus, it must be that J ext(max(B, |.|)) and, consequently, J MCC(P). FULLH. Let X J n A be the set of all profiles Q such that ext(m(Q)) JA, CMC(P) = argmin Q XDH(P, Q), and UA12 = {J1 J2 | J1 FULLH(P A1) and FULLH(P A2)}. We first show that FULLH(P) UA12. Let J FULLH(P). Let J1 = J A1 and J2 = J A2. Since J FULLH(P) then there exists Q CMC(P) such that J ext(m(Q)). Let us show that Q A1 CMC(P A1). Suppose that Q A1 / CMC(P A1). Then, there

Agents p q p q t J1 + + + + J2 + - - + J3 - + - - P1 P2

Figure 1: Counter example to Rd H,MAX being agenda separable.

exists a majority-consistent Q 1 J n A1, Q 1 = I 1, . . . , I n such that DH(Q 1, P A1) < DH(Q A1, P A1). Let Q = I1, . . . , In . Let Q A1 = I1 1, . . . , I1 n and Q A2 = I2 1, . . . , I2 n . Define Q = I 1 I2 1, . . . , I n I2 n . Because {A1, A2} is an independent partition of A, Q is a majority-consistent profile. Note also that DH(Q , P) < DH(Q, P). Contradiction. Thus, Q A1 CMC(P A1), and for the same reasons, Q A2 CMC(P A2). Therefore, J1

FULLH(P A1), J2 FULLH(P A2), and FULLH UA12. We now show that UA12 FULLH. Let J1 FULLH(P A1) and J2 FULLH(P A2). Thus, there exist profiles Q1 CMC(P A1) and Q2 CMC(P A2) such that J1 ext(m(Q1)) and J2 ext(m(Q2)). Let Q1 = Q1 1, . . . , Q1 n , Q2 = Q2 1, . . . , Q2 n , and Q = Q1 1 Q2 1, . . . , Q1 n Q2 n . Because {A1, A2} is an independent partition of A, Q is majority-consistent. Let us show that Q CMC(P). Assume that Q / CMC(P). Then there exists Q CMC(P) s.t. DH(Q , P) < DH(Q, P). Observe that DH(Q A1, P) + DH(Q A2, P) < DH(Q A1, P) + DH(Q A2, P). This means that DH(Q A1, P) < DH(Q A1, P) or DH(Q A2, P) < DH(Q A2, P). Recall that Q A1 = Q1 and Q A2 = Q2. Thus, DH(Q A1, P) < DH(Q1, P) or DH(Q A2, P) < DH(Q2, P), which, together with the fact that Q A1 and Q A2 are majority-consistent, contradicts Q1 CMC(P A1) and Q2 CMC(P A2). Thus, Q CMC(P). Note that J1 J2 m(Q). This implies that J1 J2 FULLH(P). Rd H,MAX. We provide a counter example.Let A = A1 A2 with [A1] = {p, q, p q} and [A2] = {t}. Consider the profile P from Figure 1 with P1 = P A1 and P2 = P A2. We obtain Rd H,MAX(P) = {{ p, q, (p q), t}}. However Rd H,MAX(P2) = {{t}, { t}} and Rd H,MAX(P1) = {{ p, q, (p q)}, {p, q, (p q)}, {p, q, (p q)}}.

The fact that a rule satisfies agenda separability does not imply that a resolute rule obtained by composing it with a tie-breaking mechanism satisfies agenda separability as well. For instance, if tie-breaking favours { a} over {a} when A = {a}, { b} over {b} when A = {b}, and {a, b} over all other judgment sets when A = {a, b}, and if P contains one judgment set {a, b} and one judgment set { a, b}, then for any one of our rules, and with A1 = {a, a} and A2 = {b, b}, we have R(P A1) = { a}, R(P A2) = { b}, and R(P) = {a, b}. However, if the tiebreaking priority relation >θ satisfies the following decom-

posability property, then agenda separability of an irresolute rule implies agenda separability of its composition with θ. A tie-breaking priority relation >θ is agenda separable if for every agenda A, for every independent partition {A1, A2} of A, and every J1 , J1 JA1, and J2 , J2 JA2, J1 >θ J1 and J2 >θ J2 imply J1 J2 >θ J1 J2 .

Observation 1 If >θ is an agenda separable tie-breaking priority relation and R is agenda separable, then Rθ is agenda separable.

Let >θ be an agenda separable tie-breaking priority relation, then RAθ is agenda separable. However, since it satisfies universal domain, unanimity principle (Lang et al. 2011), and collective rationality, then it does not satisfy IIA. Hence, the implication stated in Proposition 1 is strict. Lastly, we would like to state two observations about the properties of rules that are agenda separable.

Observation 2 Let K be a constant and say that agenda A is K-decomposable if A can be partitioned into p syntactically unrelated agendas A1, . . . , Ap such that for all i |Atoms(Ai)| K. If a rule satisfies agenda separability, then the collective judgment sets can be computed in time O(2Kn) whenever the agenda is K-decomposable.

In other terms, computing these rules is parameterized tractable when he parameter is the degree K of decomposability, which is a complexity gap, since winner determination for these rules is Θ2 p-hard or even Π2 p-hard (Lang and Slavkovik 2014; Endriss and de Haan 2015). Moreover, agenda separability allows for a weak form of strategyproofness. Indeed, if A can be partitioned into p syntactically unrelated agendas A1, . . . , Ap, then no agent is able to influence the outcome on some issue in Ai by reporting strategic judgments about issues of Aj for j = i.

5 Overlapping Agenda Separability In this section, we consider a stricter property than agenda separability. We first need the notion of independent overlapping decomposition.

Definition 3 (Independent overlapping decomposition) Let A be an agenda and let A = A1 A2 (but not necessarily A1 A2 = ). We say that {A1, A2} is an independent overlapping decomposition (IOD) of A if and only if for every J1 JA1, for every J2 JA2

if J1 A2 = J2 A1 then J1 J2 JA.

Example 1 Let [A] = {p, p t, p q}, [A1] = {p, p t} and [A2] = { p t, p q}. Note that {A1, A2} is an independent overlapping decomposition of A.

Observation 3 Every independent partition is an independent overlapping decomposition.

Example 1 shows that the contrary of the previous observation does not hold. Indeed, as soon as the intersection of the two sub-agendas is non-empty, they do not form an independent partition. There is a clear connection between independent overlapping decompositions and conditional independence in

propositional logic (Darwiche 1997; Lang, Liberatore, and Marquis 2002); we do not give technical details here, but we mention that this connection gives us several characterizations as well as complexity results for finding independent overlapping decompositions. We can now introduce the definition of overlapping agenda separability.

Definition 4 (Overlapping agenda separability) We say that rule R satisfies overlapping agenda separability (OAS) if for every agenda A and every independent overlapping decomposition {A1, A2} of A, for every profile P over A it holds that: if for every J1 R(P A1), for every J2 R(P A2), we have J1 A2 = J2 A1 then R(P) = {J1 J2 | J1 R(P A1) and J2 R(P A2)}.

Observation 4 Overlapping agenda separability implies agenda separability.

Proof. Let {A1, A2} be an independent partition of A. From Observation 3 {A1, A2} is an IOD. Since A1 A2 = , condition J1 A2 = J2 A1 is satisfied for every J1, J2. Thus, R(P) = {J1 J2 | J1 R(P A1) and J2 R(P A2)}.

Proposition 4 MC and RA satisfy OAS.

Proof. MC. Suppose that for every J1 MC(P1), for every J2 MC(P2), J1 A2 = J2 A1. Let ΠP1,P2 = {J1 J2 | J1 MC(P1) and J2 MC(P2)}. We first show that MC(P) ΠP1,P2. Let J MC(P). Denote J1 = J A1 and J2 = J A2. We claim that J1 MC(P1) and J2 MC(P2). Note that J1 and J2 are consistent. By means of contradiction, and without loss of generality, assume J1 / MC(P1). Thus, there exists J1 JA1 such that J1 m(P) J1 m(P). Denote J = J1 J2. Observe that J is consistent. Furthermore, J m(P) J m(P), thus J / MC(P), contradiction. We now show that ΠP1,P2 MC(P). Let J1 MC(P1) and J2 MC(P2). Denote J = J1 J2. Since {A1, A2} is an IOD, J is consistent. Suppose J / MC(P). Thus, there exists J JA such that J m(P) J m(P). Let ϕ (J m(P)) \ (J m(P)). Without loss of generality, assume ϕ A1. Denote J1 = J A1. Note that J1 is consistent and J1 m(P) J1 m(P), contradiction. RA. We give only a proof sketch. Suppose that for every J1 RA(P1), for every J2 RA(P2), J1 A2 = J2 A1. Let ΠP1,P2 = {J1 J2 | J1 RA(P1) and J2 RA(P2)}. Let J1 RA(P1), J2 RA(P2). Denote J = J1 J2. We claim that J RA(P). Because J1 RA(P1), there is an order >σ1 on A1, refining P1 such that J1 = Jσ1. Similarly, there is an order >σ2 on A2, refining P2, such that J2 = Jσ2. We first claim that without loss of generality, we can assume that >σ1 and >σ2 coincide on A1 A2. For this we construct σ on A2, refining P2, such that >σ coincides with >σ1 on A1 A2 and Jσ = Jσ2 = J2. Now, let >σ be an order on A refining P and extending both >σ1 and >σ2. Let A = {α1, . . . , α2m}. Without loss of generality, suppose α1 >σ . . . >σ α2m. Let Si A be

p p q p r q r s s q s r J1 + + + + + + + + J2 - + + - - - + + J3 + - - - - + - -

Figure 2: The counter example used to show that several rules do not satisfy OAS.

the set obtained at the step i of construction of J = Jσ. We show by induction on i that

(Hi) j {1, . . . , i} we have αj Si iff αj J1 J2.

From (H2m), we obtain J = J1 J2. We now show that RA(P) ΠP1,P2. Suppose J RA(P). Let >σ be an order on A such that J = Jσ. Without loss of generality, suppose α1 >σ . . . >σ α2m. Denote by >σ1 (resp. >σ2) the restriction of >σ on A1 (resp. A2). Let J1 = Jσ1 and J2 = Jσ2. Observe that J1 A2 = J2 A1. Since {A1, A2} is an IOD, J1 J2 is consistent. Let Si A be the set obtained at the step i of construction of J = Jσ. We show by induction on i that

(Hi) j {1, . . . , i} we have αj Si iff αj J1 J2.

By putting i = 2m, we obtain J = J1 J2.

Proposition 5 MCC, MED, FULLH, and Rrev do not satisfy OAS.

Proof. MCC, MED and FULLH. We now provide a counterexample to show that MCC and MED do not satisfy OAS. Let [A1] = {p, p q, p r, q, r}, [A2] = {q, r, s, s q, s r}, and A = A1 A2. Observe that {A1, A2} is an IOD of A. Consider the profile from Figure 2. We obtain MCC(P1) = MED(P1) = FULLH(P1) = { { p, p q, p r, q, r, } } , and MCC(P2) = MED(P2) = FULLH(P2) = { { s, s q, s r, q, r, } } . However, MCC(P) = MED(P) = FULLH(P) = {{ p, p q, p r, q, r, s, s q, s r}, {p, p q, p r, q, r, s, s q, s r}}. Rrev. The proof is omitted due to space limitations.

The preference agenda (Dietrich and List 2007b) associated with a set of alternatives C = {x1, . . . , xq} is AC = {xi Pxj | 1 i < j q}. When j > i, xi Pxj is not a proposition of AC, but we write xj Pxi as a shorthand for (xj Pxi). Conversely, given a judgment set J on AC, the binary relation J over C is defined by: for all xi, xj C, xi J xj if xi Pxj J and xj J xi if xi Pxj J.

Observation 5 For any m 3, there exists no (non-trivial) independent overlapping decomposition of the preference agenda over the set of alternatives C = {x1, . . . , xm}.

Proof. We first establish the following lemma: if {A1, A2} is an independent overlapping decomposition, then for all xi, xj, xk, xi Pxj and xi Pxk are both in A1 or both in A2. Assume that it is not the case: without loss of generality,

xi Pxj A1 and xi Pxk A2. Also without loss of generality, assume xj Pxk A1. Let J1 and J2 be two consistent judgment sets over A1 and A2 such that J1 contains {xi Pxj, xj Pxk}, J2 contains xk Pxi, and J1 and J2 are completed in an arbitrary way such that J1 A2 = J2 A1; J1 J2 is an inconsistent judgment set over A1 A2, which contradicts the assumption that {A1, A2} is an independent overlapping decomposition. Assume without loss of generality that x1Px2 A1. Let x , x {x1, . . . , xk}. If x = x1 or x = x1 then the above lemma implies that x Px A1. If neither x = x1 nor x = x1, then the above lemma implies that x1Px A1, and applying the lemma again leads to x Px A1. This being true for all x , x , we have A1 = A, and {A1, A2} is a trivial decomposition.

6 Discussion We proposed a new property for judgment aggregation, namely agenda separability. It is a relaxation of the classical independence property, and unlike it, it is satisfied by several non-degenerate judgment aggregation rules. We have defined a stronger version of agenda separability, namely overlapping agenda separability, which is even more discriminant, since we have identified only two of the previously studied judgment aggregation rules that satisfy it, namely MC and RA. Note that RA satisfied furthermore unanimity principle (Lang et al. 2011). Also, two rules were left out of this paper due to space limitations: the judgment aggregation version of the Young rule, which does not satisfy agenda separability, and the geodesic distance-base rule of Duddy and Piggins (2012), which satisfies agenda separability but not overlapping agenda separability. A possible reason why agenda separability has not been studied sooner is that it is not applicable to common agendas such as the preference agenda, simply because they are not decomposable (cf. Observation 5). A similar observation would hold for other agendas of interest, such as those used for the aggregation of equivalence relations or for committee elections. However, agenda separability does apply to variants of these problems. Suppose for instance that we have to elect a committee made of K men and K women; then agenda separability applies and says that the election of the K men and the K women do not interfere. This notion of agenda separability should not be confused with a notion of separability, also known as consistency or reinforcement, considered in voting theory (Young 1975) and generalized to judgment aggregation (Lang et al. 2011): these notions say that if a profile P can be decomposed into two subprofiles P1 and P2 for which the output is the same, then this should also be the output for P. An ambitious issue for further work would be characterizing the set of rules that satisfy agenda separability, or one of its variants.

Acknowledgements. We would like to thank the anonymous reviewers for helping us to improve this work. J erˆome Lang is supported by the ANR project Co Co RICo-Co Dec.

References Awas, E.; Booth, R.; Tohm e, F.; and Rahwan, I. 2015. Judgement aggregation in multi-agent argumentation. Journal of Logic and Computation In Press. Booth, R.; Awad, E.; and Rahwan, I. 2014. Interval methods for judgment aggregation in argumentation. In Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, 594 597. Booth, R. 2015. Judgment aggregation in abstract dialectical frameworks. In Eiter, T.; Strass, H.; Truszczynski, M.; and Woltran, S., eds., Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation, volume 9060 of Lecture Notes in Computer Science. Springer International Publishing. 296 308. Caminada, M., and Pigozzi, G. 2011. On judgment aggregation in abstract argumentation. Autonomous Agents and Multi-Agent Systems 22(1):64 102. Chopra, S., and Parikh, R. 1999. An inconsistency tolerant model for belief representation and belief revision. In Proceedings of the 16th International Joint Conference on Artificial Intelligence, 192 197. Darwiche, A. 1997. A logical notion of conditional independence: Properties and applications. Artificial Intelligence 97(1 - 2):45 82. Dietrich, F., and List, C. 2007a. Arrow s theorem in judgment aggregation. Social Choice and Welfare 29(1):19 33. Dietrich, F., and List, C. 2007b. Judgment aggregation by quota rules: Majority voting generalized. Journal of Theoretical Politics 4(19):391 424. Dietrich, F., and List, C. 2007c. Strategy-Proof Judgment Aggregation. Economics and Philosophy 23(03):269 300. Dietrich, F. 2014. Scoring rules for judgment aggregation. Social Choice and Welfare 42(4):873 911. Duddy, C., and Piggins, A. 2012. A measure of distance between judgment sets. Social Choice and Welfare 39(4):855 867. Endriss, U., and de Haan, R. 2015. Complexity of the winner determination problem in judgment aggregation: Kemeny, Slater, Tideman, Young. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 117 125. Endriss, U., and Fern andez, R. 2013. Collective annotation of linguistic resources: Basic principles and a formal model. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, 539 549. Endriss, U. 2015. Judgment aggregation. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice. Cambridge University Press. chapter 17. In press. Everaere, P.; Konieczny, S.; and Marquis, P. 2014. Counting votes for aggregating judgments. In International conference on Autonomous Agents and Multi-Agent Systems, 1177 1184. Everaere, P.; Konieczny, S.; and Marquis, P. 2015. Belief merging versus judgment aggregation. In Proceedings of the

2015 International Conference on Autonomous Agents and Multiagent Systems, 999 1007. Grossi, D., and Pigozzi, G. 2014. Judgment Aggregation: A Primer. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers. Kruger, J.; Endriss, U.; Fern andez, R.; and Qing, C. 2014. Axiomatic analysis of aggregation methods for collective annotation. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, 1185 1192. Lang, J., and Slavkovik, M. 2013. Judgment aggregation rules and voting rules. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory, volume 8176 of Lecture Notes in Artificial Intelligence, 230 244. Springer-Verlag. Lang, J., and Slavkovik, M. 2014. How hard is it to compute majority-preserving judgment aggregation rules? In Proceedings of the 21st European Conference on Artificial Intelligence, 501 506. Lang, J.; Pigozzi, G.; Slavkovik, M.; and van der Torre, L. 2011. Judgment aggregation rules based on minimization. In Theoretical Aspects of Rationality and Knowledge, 238 246. Lang, J.; Liberatore, P.; and Marquis, P. 2002. Conditional independence in propositional logic. Artificial Intelligence 141(1-2):79 121. List, C., and Puppe, C. 2009. Judgment aggregation: A survey. In Anand, P.; Puppe, C.; and Pattanaik, P., eds., Oxford Handbook of Rational and Social Choice. Oxford. Miller, M., and Osherson, D. 2009. Methods for distancebased judgment aggregation. Social Choice and Welfare 32(4):575 601. Nehring, K., and Pivato, M. 2013. Majority rule in the absence of a majority. Mpra paper, University Library of Munich, Germany. Nehring, K.; Pivato, M.; and Puppe, C. 2014. The Condorcet set: Majority voting over interconnected propositions. Journal of Economic Theory 151:268 303. Parikh, R. 1999. Belief revision and language splitting. In Proceedings of Logic, Language and Computation. CSLI, 266 278. Peppas, P.; Chopra, S.; and Foo, N. 2004. Distance semantics for relevance-sensitive belief revision. In Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference, 319 328. Pigozzi, G. 2006. Belief merging and the discursive dilemma: an argument-based account to paradoxes of judgment aggregation. Synthese 152(2):285 298. Young, H. P. 1975. Social choice scoring functions. SIAM Journal on Applied Mathematics 28(4):824 838.