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 [8, 21], and has links with belief revision [16, 30] as well as abstract argumentation [4, 1, 3, 2]. For an overview of applications of judgment aggregation in artificial intelligence see for instance the work by Grossi and Pigozzi [17] or Endriss [12].

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 [23] for an overview – have dashed the hope of finding a universally applicable operator. Consequently, the suitability of an operator for a given judgment aggregation 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 [10], 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 [8].

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 [28], where decomposing a logical theory into several subtheories over disjoint sub-languages simplifies many tasks in knowledge representation, such as belief change [29] or inconsistency handling [5].

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 [18]; 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 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.

Let L be a set of well-formed propositional logical formulas, including (tautology) and (contradiction). An issue is a pair of formulas where and is neither a tautology nor a contradiction. An agenda A is a finite set of issues and has the form . The preagenda [A] associated with A is [. 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 , the preference agenda over C [8] is , and the associated integrity constraint is Γ(). When Γ is not specified, by default it is equal to .

A judgment on ] is one of or . A judgment set J is a subset of A. J is complete iff for each ], either or . A judgment set J (and in general, a set of propositional formulas) is Γ-consistent if and only if . Let 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 instead of .

A is a collection of complete and consistent individual judgment sets. We further define to be the number of all agents in P whose judgment set includes . The order is the weak order over A defined by if and only if ).

The restriction of over a sub-agenda of A is defined as .

Every consistent subset of the agenda 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 there exists such that .

A judgment aggregation rule, for n agents, is a function R that maps any constrained agenda (A, Γ) and any profile to a non-empty set of complete consistent judgment sets over If R always outputs a singleton then it 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 A profile P is majority-consistent iff m(P) is consistent.

Let . We define Atoms(S) as the set of all propositional variables appearing in S. For example, .

Given a set of formulas S and a formula Γ, is Γ-consistent if is consistent, is a maximal Γ-consistent subset of S, if is Γ-consistent and there is no that is Γ-consistent. . We use ) to denote the maximal consistent subsets of S. The set is a maxcard Γ-consistent subset of S if is Γ-consistent and there exists no Γ-consistent set such that . 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 [20, 21, 26, 27, 24, 15].

Throughout the subsection, is a profile. For two consistent and complete judgment sets we denote their Hamming distance as .

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 and .

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

[7] is defined as . Given a scoring function s,

we choose the reversal scoring function ) as the minimal number of judgment reversals needed in in order to reject then we get the [7]. If we choose the scoring function s defined by and 0 if then is exactly the median rule, i.e. .

Given profiles and in , let

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 tie-breaking 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 is the rule that, given P, returns the maximal (with respect to ) element of R(P).

A judgment aggregation rule F satisfies independence of irrelevant alternatives (IIA) if for every two profiles , and every , if , then ) iff ). 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 [8].

In [25] a relaxation of IIA is proposed, called Independence of Irrelevant Propositional Alternatives (IIPA). IIPA is the requirement that for every , and every that is either an atom or a negation of an atom, if , then ) iff ). However [25] also shows that IIPA, modulo some conditions on the agenda, is not consistent with the unanimity preservation requirement.

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 [14] 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 [, while the problem for the second photo is represented with the agenda [. Observe that . 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 depend only on the judgments given for these issues, but not on the individual judgments given for issues in .

In the next section we relax independence along this principle, defining a new property called 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 of A is an independent partition of A if for every and is Γ-consistent.

Definition 1 (Agenda separability) We say that rule R satisfies agenda separability (as) if for every agenda A, every independent partition of A, and all profiles , we have

If R is a resolute rule, then the last line of the definition simplifies into

Also, by associativity of , this notion generalises to agendas that can be partitioned into a collection such that for every is consistent. In that case,

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.

Proof. If a resolute rule R satisfies IIA, we can write ) where [and are resolute rules. Let be an independent partition of A. Without loss of generality, assume [and [. We have

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 of A, for , and every and , we have ).

We omit the easy proofs of the next two results.

Proposition 3 mc, mcc, ra, and are agenda separable. is not agenda separable.

We first show that . Let ). Let and . Since ) then there exists ) such that )). Let us show that ). Suppose that ). Then, there exists a majority-consistent such that ). Let . Let and . Define . Because is an independent partition of A, is a majority-consistent profile. Note also that ). Contradiction. Thus, ), and for the same reasons, ). Therefore, ), and .

We now show that . Let ) and ). Thus, there exist profiles ) and ) such that )) and )). Let , and Because is an independent partition of A, Q is majority-consistent.

Let us show that ). Assume that ). Then there exists ) s.t. ). Observe that ) + ) + This means that ) or ). Recall that and . Thus, ) or ), which, together with the fact that and are majority-consistent, contradicts ) and ). Thus, ). Note that ). This implies that ).

We provide a counter example.Let with [and [. Consider the profile P from Figure 1 with and . We obtain . However and

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

Figure 1: Counter example to being agenda separable.

well. For instance, if tie-breaking favours over {a} when 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 , then for any one of our rules, and with and , we have , and R(P) = {a, b}. However, if the tie-breaking priority relation satisfies the following decomposability 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 of A, and every , and and imply .

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

Let be an agenda separable tie-breaking priority relation, then is agenda separable. However, since it satisfies universal domain, unanimity principle [20], 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 such that for all i . If a rule satisfies agenda separability, then the collective judgment sets can be computed in time ) 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 Θ-hard or even Π-hard [22, 13].

Moreover, agenda separability allows for a weak form of strategyproofness. Indeed, if A can be partitioned into p syntactically unrelated agendas , then no agent is able to influence the outcome on some issue in by reporting strategic judgments about issues of for .

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 (but not necessarily ). We say that is an independent overlapping decomposition (IOD) of A if and only if for every , for every

Example 1 Let [, [and [. Note that 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 [6, 19]; 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 of A, for every profile P over A it holds that: if for every for every we have then ) and

Proof. Let be an independent partition of A. From Observation 3 is an IOD. Since , condition is satisfied for every . Thus, ) and

. We claim that ) and ). Note that and are

consistent. By means of contradiction, and without loss of generality, assume ). Thus, there exists such that Denote . Observe that is consistent. Furthermore, ), thus ),

contradiction. We now show that Π). Let ) and ). Denote

. Since is an IOD, J is consistent. Suppose ). Thus, there

exists such that Let )). Without loss of generality, assume . Denote . Note that is consistent and

ra. We give only a proof sketch. Suppose that for every for every Let

Π) and . Let ). Denote

. We claim that ). Because ), there is an order on , refining such that . Similarly, there is an order on , refining , such that . We first claim that without loss of generality, we can assume that and coincide on . For this we construct on , refining , such that coincides with on and .

Now, let be an order on A refining and extending both and . Let . Without loss of generality, suppose . Let be the set obtained at the step i of construction of . We show by induction on i that

From (), we obtain .

We now show that . Suppose ). Let be an order on A such that . Without loss of generality, suppose . Denote by (resp. ) the restriction of on (resp. ). Let and . Observe that . Since is an IOD, is consistent.

Let be the set obtained at the step i of construction of . We show by induction on i that

By putting i = 2m, we obtain

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

We obtain mcc(P(P(Pp, p q, p r, , and mcc(P(P(Ps, s q, s r, . However, mcc(P) = med(P(Pp, p q, p r, s, s q, s , {p, p q, p r, q, r, s, s q, s .

The proof is omitted due to space limitations.

The preference agenda [9] associated with a set of alternatives is . When is not a proposition of , but we write as a shorthand for ). Conversely, given a judgment set J on , the binary relation over C is defined by: for all if and if .

Observation 5 For any 3, there exists no (non-trivial) independent overlapping decomposition of the preference agenda over the set of alternatives .

Proof. We first establish the following lemma: if is an independent overlapping decomposition, then for all and are both in or both in . Assume that it is not the case: without loss of generality, and . Also without loss of generality, assume . Let and be two consistent judgment sets over and such that contains contains , and and are completed in an arbitrary way such that is an inconsistent judgment set over , which contradicts the assumption that is an independent overlapping decomposition.

Assume without loss of generality that . Let . If or then the above lemma implies that . If neither nor , then the above lemma implies that , and applying the lemma again leads to . This being true for all , we have , and is a trivial decomposition.

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 [20]. 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 [11], 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 [31] and generalized to judgment aggregation [20]: these notions say that if a profile P can be decomposed into two subprofiles and 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 CoCoRICo-CoDec.

[1] E. Awas, R. Booth, F. Tohm´e, and I. Rahwan. Judgement aggregation in multi-agent argumentation. Journal of Logic and Computation, page In Press, 2015.

[2] R. Booth, E. Awad, and I. Rahwan. Interval methods for judgment aggregation in argumentation. In Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, pages 594–597, 2014.

[3] Richard Booth. Judgment aggregation in abstract dialectical frameworks. In T. Eiter, H. Strass, M. Truszczynski, and S. Woltran, editors, Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation, volume 9060 of Lecture Notes in Computer Science, pages 296–308. Springer International Publishing, 2015.

[4] M. Caminada and G. Pigozzi. On judgment aggregation in abstract argumentation. Autonomous Agents and Multi-Agent Systems, 22(1):64–102, 2011.

[5] S. Chopra and R. Parikh. An inconsistency tolerant model for belief representation and belief revision. In Proceedings of the 16th International Joint Conference on Artificial Intelligence, pages 192–197, 1999.

[6] A. Darwiche. A logical notion of conditional independence: Properties and applications. Artificial Intelligence, 97(1 - 2):45 – 82, 1997.

[7] F. Dietrich. Scoring rules for judgment aggregation. Social Choice and Welfare, 42(4):873–911, 2014.

[8] F. Dietrich and C. List. Arrow’s theorem in judgment aggregation. Social Choice and Welfare, 29(1):19–33, July 2007.

[9] F. Dietrich and C. List. Judgment aggregation by quota rules: Majority voting gener- alized. Journal of Theoretical Politics, 4(19):391 – 424, 2007.

[10] F. Dietrich and C. List. Strategy-Proof Judgment Aggregation. Economics and Philosophy, 23(03):269–300, November 2007.

[11] C. Duddy and A. Piggins. A measure of distance between judgment sets. Social Choice and Welfare, 39(4):855–867, 2012.

[12] U. Endriss. Judgment aggregation. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 17. Cambridge University Press, 2015. In press.

[13] U. Endriss and R. de Haan. Complexity of the winner determination problem in judg- ment aggregation: Kemeny, Slater, Tideman, Young. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 117–125, 2015.

[14] U. Endriss and R. Fern´andez. Collective annotation of linguistic resources: Basic prin- ciples and a formal model. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 539–549, 2013.

[15] P. Everaere, S. Konieczny, and P. Marquis. Counting votes for aggregating judgments. In International conference on Autonomous Agents and Multi-Agent Systems, pages 1177–1184, 2014.

[16] P. Everaere, S. Konieczny, and P. Marquis. Belief merging versus judgment aggrega- tion. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 999–1007, 2015.

[17] D. Grossi and G. Pigozzi. Judgment Aggregation: A Primer. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2014.

[18] J. Kruger, U. Endriss, R. Fern´andez, and C. Qing. Axiomatic analysis of aggregation methods for collective annotation. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, pages 1185–1192, 2014.

[19] J. Lang, P. Liberatore, and P. Marquis. Conditional independence in propositional logic. Artificial Intelligence, 141(1-2):79–121, 2002.

[20] J. Lang, G. Pigozzi, M. Slavkovik, and L. van der Torre. Judgment aggregation rules based on minimization. In Theoretical Aspects of Rationality and Knowledge, pages 238–246, 2011.

[21] J. Lang and M. Slavkovik. 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, pages 230–244. Springer-Verlag, 2013.

[22] J. Lang and M. Slavkovik. How hard is it to compute majority-preserving judgment aggregation rules? In Proceedings of the 21st European Conference on Artificial Intelligence, pages 501–506, 2014.

[23] C. List and C. Puppe. Judgment aggregation: A survey. In P. Anand, C. Puppe, and P. Pattanaik, editors, Oxford Handbook of Rational and Social Choice. Oxford, 2009.

[24] M.K. Miller and D. Osherson. Methods for distance-based judgment aggregation. Social Choice and Welfare, 32(4):575–601, 2009.

[25] P. Mongin. Factoring out the impossibility of logical aggregation. Journal of Economic Theory, 141(1):100 – 113, 2008.

[26] K. Nehring and M. Pivato. Majority rule in the absence of a majority. Mpra paper, University Library of Munich, Germany, 2013.

[27] K. Nehring, M. Pivato, and C. Puppe. The Condorcet set: Majority voting over interconnected propositions. Journal of Economic Theory, 151:268–303, 2014.

[28] R. Parikh. Belief revision and language splitting. In Proceedings of Logic, Language and Computation. CSLI, pages 266–278, 1999.

[29] P. Peppas, S. Chopra, and N.Y. Foo. Distance semantics for relevance-sensitive belief revision. In Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference, pages 319–328, 2004.

[30] G. Pigozzi. Belief merging and the discursive dilemma: an argument-based account to paradoxes of judgment aggregation. Synthese, 152(2):285–298, 2006.

[31] H. P. Young. Social choice scoring functions. SIAM Journal on Applied Mathematics, 28(4):824–838, 1975.