# on_consensus_in_belief_merging__af06a419.pdf

On Consensus in Belief Merging

Nicolas Schwind National Institute of Advanced Industrial Science and Technology, Tokyo, Japan nicolas-schwind@aist.go.jp

Pierre Marquis CRIL-CNRS, Universit e d Artois, Institut Universitaire de France Lens, France marquis@cril.fr

We define a consensus postulate in the propositional belief merging setting. In a nutshell, this postulate imposes the merged base to be consistent with the pieces of information provided by each agent involved in the merging process. The interplay of this new postulate with the IC postulates for belief merging is studied, and an incompatibility result is proved. The maximal sets of IC postulates which are consistent with the consensus postulate are exhibited. When satisfying some of the remaining IC postulates, consensus operators are shown to suffer from a weak inferential power. We then introduce two families of consensus operators having a better inferential power by setting aside some of these postulates.

Introduction

In this paper, we are interested in defining consensus operators for aggregating pieces of propositional information. We consider a set of n communicating agents, each of them wanting to refine her own propositional beliefs ϕi by merging them with the beliefs of the other agents of the group. Reaching this goal requires first to merge all the belief bases, then to determine how to refine each ϕi with the result of the merging process. To achieve the first step, many belief merging (BM) operators can be exploited, see e.g., (Lin 1996; Revesz 1997; Liberatore and Schaerf 1998; Konieczny and Pino P erez 2002a; Konieczny and Pino P erez 2011). The second step calls for revision policies, as considered in (Schwind et al. 2015; 2016). Here the focus is laid on agents which are reluctant to change: each agent is ready to accept the merged base, provided that it allows her to refine her prior beliefs ϕi but does not question them. Thus, the revision policy which is adopted by each such agent consists in expanding her belief base ϕi by the merged base if the conjunction is consistent, and to keep ϕi unchanged otherwise. In order to avoid the latter case, we are interested in defining consensus operators, i.e., merging operators such that the merged base C that is generated satisfies the consensus condition: C is consistent with every input base ϕi that is consistent with the integrity constraint μ. In such a case, C is said to be a consensus for K under μ.

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

Since consensus operators are BM operators, it is important to situate them within the family of BM operators. This family received much attention in AI and some rationality postulates (the so-called IC postulates) associated with representation theorems have been pointed out (Konieczny and Pino P erez 2002a). As BM operators, consensus operators are thus expected to satisfy as many IC postulates as possible. Unfortunately, using fully rational merging operators does not lead to compute merged bases which are consensuses in the general case.

Example 1 Consider a set of three US citizens, Alice, Bob, Charlie traveling together to Paris, and planning a trip to Normandy. They all know that they have to take a train at station Gare St Lazare but have different beliefs about the location and availability of the station from CDG Airport. Thus, Alice (agent 1) believes that Gare St Lazare is located at the north of Paris midtown, and at the west. Bob (agent 2) has been told that Gare St Lazare is located at the south of Paris midtown, and that it is not reachable from CDG airport in less than 30mn, and Charlie (agent 3) believes that it is located at the north of Paris midtown, and is reachable from CDG airport in less than 30mn. Representing the information using three propositional symbols (a: Gare St Lazare is located at the south of Paris midtown, b: Gare St Lazare is located at the east of Paris midtown, and c: Gare St Lazare is reachable from CDG airport in less than 30mn), the belief bases of Alice, Bob, and Charlie are respectively ϕ1 = { a b}, ϕ2 = {a c}, and ϕ3 = { a c}. Here there are no integrity constraint (μ = ). Suppose one takes advantage of the distance-based merging operator Δd H,Σ to merge the belief bases of the profile K = {ϕ1, ϕ2, ϕ3} under μ. Δd H,Σ is based on the Hamming distance and uses sum as the aggregation function. It is known to satisfy all the IC postulates (Konieczny and Pino P erez 2002a), thus it appears prima facie as a good candidate for this job. However, Δd H,Σ μ ({ϕ1, ϕ2, ϕ3}) is equivalent to the base { a b},1

which is not a consensus for {ϕ1, ϕ2, ϕ3} under μ since it conflicts with Bob s beliefs. In order to satisfy the consensus condition for this example, a logically weaker merged base must be computed. Thus, merging operators having quite a low inferential power look at a first glance as suitable consensus operators.

1Details of the computations are reported in Table 1.

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

Among them is the basic merging operator Δb (Konieczny and P erez 1999): Δb μ({ϕ1, ϕ2, ϕ3}) is equivalent to the disjunction of the three bases ϕ1, ϕ2, ϕ3, hence to {( a c) (a b c)}, so that it is consistent with every of them. However, this consensus is not convenient since it does not convey any new piece of information to any of the three agents (expanding ϕ1, ϕ2, or ϕ3 with it does not change anything: there is no belief refinement at all). One consequence is that, for instance, it does not entail b which is not questioned by any of the three agents. Contrastingly, merged bases equivalent to {( a c) b} or to {( a c) (a c) b} would be much better consensuses, since the first one would lead Bob and Charlie to improve their beliefs and the second one would lead each of the three agents to improve her beliefs. This example shows that one must take care of the inferential power of the consensus operators which are used.

The very objective of this paper is to determine the extent to which the consensus condition is compatible with the IC postulates, to point out some consensus operators, and to delineate borders of the trade-off between the rationality conditions and the inferential power offered by such operators. The main contributions are as follows. First of all, a consensus postulate is formally defined. The interplay of this new postulate with the standard IC postulates for belief merging is studied. We show that the consensus postulate is incompatible with the conjunction of the IC postulates (IC2) and (IC6), while compatible with each of them taken separately. Since (IC2) is more central to BM than (IC6), the focus is laid on consensus operators satisfying (IC2). We also investigate how our consensus postulate interacts with the majority, arbitration and disjunction postulates. Then we show that the consensus operators satisfying (IC0) and (IC8) have a weak inferential power. Thus setting aside (IC8) is necessary for getting consensus operators satisfying (IC0) and (IC2), and which are not too weak from the inferential standpoint. On this ground, we introduce two families of consensus operators. The first one is composed of the distance-based operators relying on a Pareto aggregation. Such operators satisfy all IC postulates but (IC6) and (IC8). The second one gathers consensus operators induced by merging operators Δ, and can be viewed as a generalization of the family of arbitration operators from (Liberatore and Schaerf 1998). When the underlying BM operator Δ is an IC one, the corresponding consensus operator is ensured to satisfy all IC postulates but (IC5), (IC6) and (IC8). We show how the expected consensuses for Example 1 as given above can be computed using some of the introduced consensus operators, and provide comparative results on the behaviour of these operators from the inferential standpoint. For space reasons, most proofs are omitted. An extended version of the paper containing all the proofs is available from www.cril.fr/ marquis/aaai18-extended.pdf.

A Glimpse at Propositional Merging

Let LP be a propositional language built up from a finite set of propositional variables P and the usual connectives. (resp. ) is the Boolean constant always false (resp. true).

An interpretation is a mapping from P to {0, 1}, denoted by a bit vector whenever a strict total order on P is specified. The set of all interpretations is denoted W. [ϕ] denotes the set of models of the formula ϕ, i.e., [ϕ] = {ω W | ω |= ϕ}. |= denotes logical entailment and logical equivalence, i.e., ϕ |= ψ iff [ϕ] [ψ] and ϕ ψ iff [ϕ] = [ψ]. An integrity constraint μ is a propositional formula. A belief base ϕ denotes the set of beliefs of an agent, it is a finite and consistent set of propositional formulae, interpreted conjunctively, so that ϕ is identified with the conjunction of its elements. A profile K = {ϕ1, . . . , ϕn} is a finite, multi-set of belief bases. K (resp. K) denotes the conjunction (resp. the disjunction) of all bases from K. refers to the union of multi-sets. Given a profile K and a formula μ, MC(K, μ) denotes the set of maximal subsets of bases from K which are jointly consistent with μ, that is, MC(K, μ) = {K K | K μ |= , K K, K K K μ |= }. Lastly, MC(K, μ) denotes the set K MC(K,μ) K . A BM operator Δ is a mapping associating with every integrity constraint μ and every profile K = {ϕ1, . . . , ϕn} with n 1, a belief base Δμ(K) called the merged base. A set of standard properties denoted (IC0)-(IC8) (called IC postulates) expected for BM operators have been pointed out (Konieczny and Pino P erez 2002a). Operators satisfying them are called IC merging operators.

(IC0) Δμ(K) |= μ;

(IC1) If μ is consistent, then Δμ(K) is consistent;

(IC2) If K μ is consistent, then Δμ(K) K μ;

(IC3) If K1 K2 and μ1 μ2, then Δμ1(K1) Δμ2(K2);

(IC4) If ϕ1 |= μ, ϕ2 |= μ and Δμ({ϕ1, ϕ2}) ϕ1 is consistent, then Δμ({ϕ1, ϕ2}) ϕ2 is consistent;

(IC5) Δμ(K1) Δμ(K2) |= Δμ(K1 K2);

(IC6) If Δμ(K1) Δμ(K2) is consistent, then Δμ(K1 K2) |= Δμ(K1) Δμ(K2);

(IC7) Δμ1(K) μ2 |= Δμ1 μ2(K);

(IC8) If Δμ1(K) μ2 is consistent, then Δμ1 μ2(K) |= Δμ1(K) μ2.

In these postulates, when K1 = {ϕ1,1, . . . , ϕ1,n} and K2 = {ϕ2,1, . . . , ϕ2,n}, K1 K2 means that there exists a bijection π from {1, . . . , n} to {1, . . . , n} such that for each i {1, . . . , n}, we have ϕ1,i ϕ2,π(i). We refer the reader to (Konieczny and Pino P erez 2002a) for a detailed explanation about the rationale of these postulates. The following additional postulates will also be considered in this paper (Konieczny and Pino P erez 2002a; Everaere, Konieczny, and Marquis 2010): (Maj), (Arb) and (Disj), that respectively characterize the class of majority, arbitration (Konieczny and Pino P erez 2002a) and disjunctive (Everaere, Konieczny, and Marquis 2010) operators:

(Maj) n 1 Δμ(K1 K2 . . . K2 n ) |= Δμ(K2).

Δμ1({ϕ1}) Δμ2({ϕ2}) Δμ1 μ2({ϕ1, ϕ2}) (μ1 μ2) μ1 |= μ2 μ2 |= μ1 then Δμ1 μ2({ϕ1, ϕ2}) Δμ1({ϕ1}).

(Disj) If K μ is consistent, then Δμ(K) |= K.

Among IC merging operators are some distance-based operators, i.e., operators which are based on the selection of some models of the integrity constraint, the closest ones to the given profile. Those operators are characterized by a distance d between interpretations and an aggregation function f (Konieczny, Lang, and Marquis 2004). They associate with every integrity constraint μ and every profile K a belief base Δd,f μ (K) which satisfies [Δd,f μ (K))] = min([μ], d,f K ), where d,f K is the total preorder over interpretations induced by K defined by ω d,f K ω if and only if df(ω, K) df(ω , K), where df(ω, K) = fϕi K{d(ω, ϕi)} and d(ω, ϕi) = minω |=ϕi d(ω, ω ). Usual distances are d D, the drastic distance and d H, the Hamming distance. Note that some distance-based operators are not IC merging ones (some conditions must be satisfied by f, see (Konieczny, Lang, and Marquis 2004)) but taking advantage of usual aggregation functions as Σ, GMax and GMin (Everaere, Konieczny, and Marquis 2010) lead to IC merging operators.

Example 1 (continued) Let LP be built up from the set of propositional variables P = {a, b, c}, ϕ1 = { a b}, ϕ2 = {a c}, ϕ3 = { a c} and μ = . We consider Σ, GMax and GMin operators based on the drastic distance on the one hand, the Hamming distance on the other hand. Table 1 gives for each interpretation ω [μ] the distances d(ω, ϕi) for d {d D, d H} and i {1, 2, 3}, and shows for each interpretation whether it is selected in Δd,Σ μ (K), Δd,GMax μ (K) and Δd,GMin μ (K) respectively (interpretations ω are denoted as binary sequences following the ordering a < b < c).

Δd D,Σ μ (K) Δd D,GMax μ (K) Δd D,GMin μ (K) a b c ϕ1 ϕ3. Δd H,Σ μ (K) a b ϕ1;

Δd H,GMax μ (K) a b c;

Δd H,GMin μ (K) a b c ϕ1 ϕ3.

Consensus and Propositional Merging A consensus operator is a BM operator satisfying the following consensus postulate (CO):

(CO) ϕi K, if ϕi μ is consistent, then ϕi Δμ(K) is consistent.

When Δ is a merging operator satisfying (CO), the merged base Δμ(K) is said to be a consensus for K under μ. Let us investigate how the consensus postulate interacts with the IC postulates. First of all, (CO) can be viewed as a stronger version of the equity postulate (IC4):

Proposition 1 Every consensus operator satisfies (IC4).

Then a key issue is to determine whether (CO) is compatible or not with the IC postulates. It turns out that the answer to it is negative. More precisely:

Proposition 2 There is no BM operator jointly satisfying (IC2), (IC6), and (CO).

Proof: Let K = {ϕ1, ϕ2} such that [ϕ1] = {ω1} and [ϕ2] = {ω2}, and let μ such that [μ] = {ω1, ω2}. Towards a contradiction, assume there exists a BM operator Δ satisfying (IC2), (IC6), and (CO). By (IC2), Δμ({ϕ2}) ϕ2, so [Δμ({ϕ2})] = {ω2}. Furthermore, by (CO), {ω1, ω2} [Δμ({ϕ1, ϕ2})]. Hence, [Δμ({ϕ1, ϕ2}) Δμ({ϕ2})] = {ω2}, so Δμ({ϕ1, ϕ2}) Δμ({ϕ2}) |= . Then, by (IC6), Δμ({ϕ1, ϕ2, ϕ2}) |= Δμ({ϕ1, ϕ2}) Δμ({ϕ2}). Thus [Δμ({ϕ1, ϕ2, ϕ2})] = {ω2}. However, by (CO) we must also have {ω1, ω2} [Δμ({ϕ1, ϕ2, ϕ2})]. Contradiction.

The other IC postulates do not jointly conflict with (CO). Indeed, one can find a BM operator Δ satisfying (CO) and all the IC postulates but (IC2). The trivial merging operator Δt given by Δt μ(K) = {μ} does the job.

Proposition 3 Δt satisfies (CO) and all IC postulates but (IC2).

But Δt is not an interesting operator as it gives up all information from any input profile, even when all belief bases are jointly consistent with the integrity constraint. On the other hand, one can define consensus operators satisfying (IC2) and almost all other IC postulates. More precisely, there exist BM operators Δ satisfying (CO) and all the IC postulates but (IC6). This is the case of the drastic merging operator Δd (Konieczny and P erez 1999) defined by:

Δd μ(K) = K μ if consistent, μ otherwise;

and of the basic merging operator Δb (Konieczny and P erez 1999) defined by:

K μ if consistent, K μ if K μ is inconsistent and K μ is consistent, μ otherwise.

Proposition 4 Δd and Δb satisfy (CO) and all IC postulates but (IC6).

The last two propositions can be used to strengthen Proposition 2, showing that (IC2), (IC6), and (CO) is a minimal set of incompatible postulates (i.e., while there is no merging operator satisfying the three postulates, one can find merging operators satisfying any proper subset of it). Yet (IC2) is essential to belief merging. Indeed, a fundamental expectation of BM is to ensure that the beliefs of a group of agents is at least as (logically) strong as the individual beliefs, when there is no conflict between them. That way, synergetic effects are possible, i.e., some logical consequences of the beliefs of the group may not be among the consequences of any isolated agent. This is what (IC2) captures. On the other hand, (IC6) is sometimes considered as too strong.

ω ϕ1 ϕ2 ϕ3 Σ GMax GMin Par d D,f ϕ1 ϕ2 ϕ3 Σ GMax GMin Par d H,GMin d H,g

0 1 1 100 1 0 1 1 0 2 010 1 1 1 1 1 1 001 0 1 0 0 2 0 110 1 0 1 2 0 2 101 1 1 1 1 1 1 011 1 1 0 1 2 0 111 1 1 1 2 1 1

Table 1: The BM operators Δd,Σ, Δd,GMax, Δd,GMin, Δd,P ar and d,f for d {d D, d H}, f {Σ, GMax, GMin} and g {Σ, GMax}. The left part (resp. right part) depicts the case where d = d D (resp. d = d H).

Loosely speaking it is the counterpart of a very restrictive Pareto condition, considering the aggregation of sets of criteria, not only individual ones. This explains why many merging operators of interest proposed in the literature fail to satisfy (IC6), e.g., the formula-based operators (Konieczny 2000) and the quota operators (Everaere, Konieczny, and Marquis 2010); and this is also why weaker postulates (like (IC6b) introduced in (Everaere, Konieczny, and Marquis 2014)2) have been previously considered. Therefore, as we are interested in consensus operators satisfying (IC2), (IC6) must be set aside. Let us now take look at how consensus operators relate to (Maj), (Arb) and (Disj) together with the IC postulates (except (IC6)). It turns out that similarly to (IC6), (Maj) appears as antagonistic with (CO) under (IC2) (Proposition 5), and that (IC2), (Maj), and (CO) is a minimal set of incompatible postulates (Proposition 6):

Proposition 5 There is no BM operator jointly satisfying (IC2), (Maj), and (CO).

Proposition 6 Δt satisfies (Maj).

On the other hand, (Arb) and (Disj) are compatible with (CO) and all IC postulates (except (IC6)):

Proposition 7 Δd and Δb satisfy (Arb) and (Disj).

According to Proposition 4, the drastic and basic operators appear as relatively well-behaved in terms of IC properties. In addition (Proposition 7), they satisfy (Arb) and (Disj). However, whenever K μ is inconsistent nothing new can be inferred from the merged base Δd μ(K) or Δb μ(K) that cannot be inferred by at least one the bases from the profile. That is to say, for every base ϕi K, ϕi |= Δd μ(K) and ϕi |= Δb μ(K). A natural question is then whether there exist some consensus operators which satisfy all (or a subset of) IC postulates apart from (IC6) and which offer a reasonable compromise from the inferential standpoint. It turns out that the consensus operators satisfying a few IC postulates do not preserve much information from the input profile:

Proposition 8 Let Δ be a BM operator satisfying (CO), (IC0) and (IC8). For any profile K and each base ϕi K, if ϕi μ |= Δμ(K) then (i) ϕi MC(K, μ) and (ii) ϕj K, ϕj / MC(K, μ) ϕj μ |= ϕi μ.

2(IC6b) requires that if Δμ(ϕ1) . . . Δμ(ϕn) is consistent, then Δμ(ϕ1, . . . , ϕn) |= Δμ(ϕ1) . . . Δμ(ϕn).

Proof: We first prove the following lemma: Lemma 1 Let Δ be an operator satisfying (CO), (IC0) and (IC8). For each base ϕi K, if ϕi μ is consistent then ϕi μ |= Δμ(K) or Δμ(K) |= ϕi μ. Proof: Given a set of interpretations M, let φ(M) denote any formula satisfying [φ(M)] = M. Assume ϕi μ |= Δμ(K) and let us prove that Δμ(K) |= ϕi μ. Let ω |= ϕi μ Δμ(K). Assume towards a contradiction that Δμ(K) |= ϕi μ. Then let ω |= Δμ(K) (ϕi μ). By (IC0), ω |= μ so ω |= Δμ(K) ϕi. Since ω |= Δμ(K) and ω |= Δμ(K), Δμ(K) φ({ω, ω }) φ({ω }). So by (IC8), Δφ({ω,ω })(K) |= φ({ω }). On the one hand, ω |= ϕi so Δφ({ω,ω })(K) ϕi |= . On the other hand, ω |= ϕi so φ({ω, ω }) ϕi |= , and by (CO) Δφ({ω,ω })(K) ϕi |= . Contradiction.

We now prove the proposition. Let ϕi K, ϕi μ |= Δμ(K). We prove (i) ϕi MC(K, μ). Assume towards a contradiction that ϕi / MC(K, μ). Since ϕi μ |= , MC(K, μ) = . So let S MC(K, μ), ϕi / S. By Lemma 1, Δμ(K) |= ϕi μ. Yet ϕi / S, so S μ ϕi |= . So let ϕj S, Δμ(K) |= ϕj μ. We have ϕj μ |= , so by Lemma 1, ϕj μ |= Δμ(K). We got that Δμ(K) |= ϕi μ and ϕj μ |= Δμ(K), therefore ϕj μ |= ϕi μ. This contradicts that S μ ϕi |= . Therefore, ϕi MC(K, μ). We now prove (ii). We already got that Δμ(K) |= ϕi μ. Let ϕj / MC(K, μ). By using the contrapositive of (i) on ϕj, we get ϕj μ |= Δμ(K). Hence, ϕj μ |= ϕi μ. This concludes the proof.

Proposition 8 (i) tells us that using a consensus operator Δ satisfying (IC0) and (IC8), leads the merged base Δμ(K) to be entailed by each base from the profile (in conjunction with μ) which does not belong to all maximal consistent subsets from MC(K, μ); and (ii) each one these bases (in conjunction with μ) necessarily entails each base that belongs to all maximal consistent subsets from MC(K, μ). This shows that consensus operators satisfying (IC0) and (IC8) have a weak inferential power. The next proposition is a noticeable consequence of these results. We say that a profile K contains a disagreement over μ whenever {ϕi K | ϕi μ |= } is inconsistent: Proposition 9 Let Δ be a BM operator satisfying (CO),

(IC0) and (IC8). For each profile K and each formula μ, if K contains a disagreement over μ, then K MC(K,μ) K μ |= Δμ(K).

Proposition 9 states that in presence of (IC0) and (IC8), the disjunction of all maximal consistent subsets of MC(K, μ) entails the merged base when the profile K contains a disagreement over the integrity constraints μ. Yet profiles containing a disagreement over the integrity constraints are the most interesting ones in belief merging, as dealing with jointly inconsistent bases is precisely what makes the merging issue a non-trivial one. Before closing this section, we show that the indecisiveness of consensus operators gets more critical in presence of additional IC postulates. Let us consider a weakening of (IC6) introduced in (Konieczny and Pino P erez 2002b):

(IC6 ) If Δμ(K1) Δμ(K2) is consistent, then Δμ(K1 K2) |= Δμ(K1) Δμ(K2).

Clearly, a BM operator satisfying (IC6) also satisfies (IC6 ). Merging operators satisfying all IC postulates yet replacing (IC6) by (IC6 ) are called quasi-merging operators (Konieczny and Pino P erez 2002b). Among them are the Max operators (Konieczny and Pino P erez 2002b), i.e., distance-based operators using Max as an aggregation function. Interestingly, although (IC6) is not compatible with (CO) and (IC2), one can find a quasi-merging operator that is a consensus one. Indeed, the drastic merging operator Δd is a quasi-merging operator (cf. Theorem 87 in (Konieczny 1999)) and Proposition 4 shows that it satisfies (CO). However, as we argued before this operator makes poor use of information conveyed by the input profile. Actually, in presence of (IC2), (IC7) and (IC6 ) in addition to (IC0) and (IC8), the result given in Proposition 8 is strengthened: when dealing with any profile whose belief bases are jointly inconsistent with the integrity constraints, every consensus quasi-merging operator returns a merged base which is entailed by the disjunction of all non-valid bases, once conjoined with the integrity constraints:

Proposition 10 Let Δ be a merging operator satisfying (CO), (IC0), (IC2), (IC6 ), (IC7) and (IC8). If K μ is inconsistent, then for each base ϕi K such that ϕi is not valid, we have that ϕi μ |= Δμ(K).

Let us summarize: first, by Proposition 2, there is no consensus operator satisfying (IC2) and (IC6), so that (IC6) must be set aside. Second, by Proposition 8, we know that one cannot find a consensus operator with a reasonable inferential power which satisfies (IC0) and (IC8) (things getting worse in presence of (IC7), (IC2) and (IC6 ), cf. Proposition 10). Yet (IC0) captures a fundamental principle whereas (IC8) could be considered as too strong: it is the BM counterpart of the postulate (R6) in belief revision (Katsuno and Mendelzon 1991), and revision operators of interest yet not satisfying (R6) have been proposed in the literature (Katsuno and Mendelzon 1991; Benferhat, Lagrue, and Papini 2005) Therefore, in addition to (IC6), (IC8) appears as the best condition to be relaxed to get more interesting consensus operators. This is what we do in the following.

Pareto Consensus Operators

We now focus on a class of consensus operators, called Pareto operators. As distance-based operators, Pareto operators take advantage of a distance d between interpretations which defines a distance between an interpretation ω and a belief base as d(ω, ϕ) = minω |=ϕ d(ω, ω ). Every interpretation ω is then associated with a list of numbers (δ1, . . . , δn) where for each ϕi K, δi = d(ω, ϕi). Pairs of interpretations are then compared using the Pareto criterion on the list of numbers associated with them. The selected models of the merged base are the closest ones to the profile in terms of Pareto optimality:

Definition 1 (Pareto dominance) Given a profile K, a distance d between interpretations and two interpretations ω, ω , ω is said to (weakly) Pareto dominate ω w.r.t. d and K, noted ω d,P ar K ω , if for each ϕi K, d(ω, ϕi) d(ω , ϕi).

Pareto operators are then formally defined as follows:

Definition 2 (Pareto operator) Given a distance d between interpretations, the Pareto merging operator based on d, denoted by Δd,P ar, associates with every formula μ and every profile K a belief base Δd,P ar μ (K) which satisfies [Δd,P ar μ (K)] = min([μ], d,P ar K ).

Proposition 11 For any distance d between interpretations, Δd,P ar satisfies (CO), (IC0), (IC1), (IC2), (IC3), (IC4), (IC5) and (IC7). It does not satisfy (IC6), (IC8), (Arb) or (Disj) in the general case.

Example 1 (continued) We get that (see Table 1) Δd D,P ar μ (K) (a c) ( a b c) ϕ2 (ϕ1 ϕ3), and Δd H,P ar μ (K) ( a c) b. Both Δd D,P ar μ (K) and Δd H,P ar μ (K) are consensuses for K under μ. Using Δd D,P ar leads agents 1 and 3 to refine their beliefs, and using Δd H,P ar leads agents 2 and 3 to refine their beliefs.

From this example, one can observe that Δd D,P ar and Δd H,P ar are incomparable in terms of inferential power in the general case, since here Δd D,P ar μ (K) |= Δd H,P ar μ (K) and Δd H,P ar μ (K) |= Δd D,P ar μ (K). Table 1 also suggests that all three distance-based merging operators have an inferential power stronger than the Pareto operator based on the same distance, i.e., for d {d D, d H}, Δd,Σ μ (K) |= Δd,P ar μ (K) (and similarly for Δd,GMax μ (K) and Δd,GMin μ (K)). This is actually always the case for any distance d and any aggregation function f satisfying the (strict monotonicity) property (Everaere, Konieczny, and Marquis 2012), (which is offered by standard aggregation functions as GMax, GMin and Σ):

Definition 3 (strict monotonicity) An aggregation function f satisfies (strict monotonicity) if x < y f(x1, . . . , x, . . . , xn) < f(x1, . . . , y, . . . , xn).

Proposition 12 Let d be any distance and f be an aggregation function satisfying (strict monotonicity). For every profile K and formula μ, we have Δd,f μ (K) |= Δd,P ar μ (K).

Example 1 also illustrates that the merged base obtained using Pareto operators (for any of the two distances) is not entailed by the disjunction of all three input bases, as it would be required for consensus operators satisfying (IC0), (IC2) and (IC8), since none of these three bases belong to all maximal consistent subsets of MC(K, μ) (cf. point (i) of Proposition 8). This shows that while ensuring the consensus condition, Pareto operators have a reasonable inferential power compared to consensus merging operators satisfying (IC0) and (IC8). Especially, Corollary 1 below shows that the Pareto operator based on the drastic distance has an inferential power which is higher than any consensus operator satisfying (IC0) and (IC8), when dealing with profiles K containing a disagreement over μ:

Proposition 13 For any profile K and formula μ, we have that Δd D,P ar μ (K)

K MC(K,μ) K μ.

Proposition 13 states that Δd D,P ar μ (K) is equivalent to the disjunction of the maximal consistent subsets of MC(K, μ). It is worth noting that Δd D,P ar corresponds to the combination function Comb1 introduced in (Baral et al. 1992) and studied in (Konieczny 2000). A direct consequence of Proposition 13 and Proposition 9 is:

Corollary 1 Let Δ be any BM operator satisfying (CO), (IC0) and (IC8). For any profile K and formula μ, if K contains a disagreement over μ, then Δd D,P ar μ (K) |= Δμ(K).

From IC Operators to Consensus Ones We now explain how some consensus operators can be induced from merging ones. We determine the postulates satisfied by the induced operators, depending on the postulates satisfied by the merging operators they are based on.

Definition 4 ( operator) Let Δ be a BM operator. The BM operator induced by Δ is defined by μ(K) μ if K μ is inconsistent, and μ(K)

ϕi K Δϕi μ(K \ {ϕi}) in the remaining case.3

Ensuring conditions on Δ is enough to guarantee conditions on :

Proposition 14

For i {0, 1, 2, 3, 7}, if Δ satisfies (ICi), then satisfies (ICi). If Δ satisfies (IC0) and (IC1), then satisfies (IC4) and (CO). If Δ satisfies (IC0), then satisfies (Disj). If Δ satisfies (IC2), then satisfies (Arb).

However, we have also that:

Proposition 15 satisfies neither (IC5) nor (IC8) in general, even if is induced by an IC merging operator.

Let us denote d,f the distance-based operator operator induced by the distance-based merging operator Δd,f.

3If K = {ϕ1}, then we assume that μ({ϕ1}) μ if ϕ1 μ is inconsistent, and μ({ϕ1}) ϕ1 μ in the remaining case.

Example 1 (continued) Let us detail the computation of d D,Σ μ (K). We have that d D,Σ μ (K) Δd D,Σ ϕ1 μ({ϕ2, ϕ3}) Δd D,Σ ϕ2 μ({ϕ1, ϕ3}) Δd D,Σ ϕ3 μ({ϕ1, ϕ2}) (ϕ1 ϕ3) ϕ2 (ϕ1 ϕ3) ϕ2 (ϕ1 ϕ3). Then it can be checked that d D,Σ μ (K) d D,GMin μ (K) d D,GMax μ (K) d D,P ar μ (K) Δd D,P ar μ (K); d H,Σ μ (K) d H,GMax μ (K) d H,P ar μ (K) Δd H,P ar μ (K); and d H,GMin μ (K) ( a c) (a c) b. Note that when using d H,GMin μ all agents refine their beliefs and the merged base entails b which is not questioned by any agent.

Interestingly, the family of operators can be viewed as a generalization of the arbitration operators (or commutative revision operators) introduced in (Liberatore and Schaerf 1998). Let us recall that the arbitration operator induced by a belief revision operator is defined by ϕ1 ϕ2 = (ϕ1 ϕ2) (ϕ2 ϕ1) (Liberatore and Schaerf 1998), and that, for a given BM operator Δ, the induced belief revision operator Δ is defined by ϕ1 Δ ϕ2 = Δϕ2({ϕ1}) (Konieczny and Pino P erez 2002a). We have that:

Proposition 16 Let Δ be a BM operator, Δ the induced belief revision operator, and Δ the corresponding arbitration operator. We have ϕ1 Δ ϕ2 ({ϕ1, ϕ2}).

Note that the generalization of arbitration operators to profiles with more than two bases, consisting of the operators, differ from the generalization suggested in (Konieczny and Pino P erez 2002a) where the merged base for a profile K is defined as Δ K(K). Indeed, a merging operator defined by μ(K) = Δμ K(K) where Δ is an IC merging operator, does not satisfy (CO) in general, even if μ is valid. Let us finally provide some results about the inferential power of operators. First, from Example 1 one can observe (for instance) that d H,GMin μ (K) |= Δd H,P ar μ (K): the information contained in Δd H,P ar μ (K) is also contained in d H,GMin μ (K). This does not happen by accident:

Proposition 17 Let d,f be the operator induced by Δd,f, where d is any distance and f is an aggregation function satisfying (strict monotonicity). For any profile K and formula μ such that K μ is consistent, we have d,f μ (K) |= Δd,P ar μ (K).

Actually, the inferential power of distance-based operators d,f may be strictly stronger than Δd,P ar. Indeed, Example 1 shows that d H,GMin μ (K) Δd H,P ar μ (K). This may also be the case when considering the drastic distance, as shown by the following example:

Example 2 Let P = {a, b}, K = {ϕ1, ϕ2, ϕ3, ϕ4}, ϕ1 = { a}, ϕ2 = { b}, ϕ3 = ϕ4 = {a b}, and μ = . We get that Δd D,Σ μ (K) a b, whereas d D,Σ μ (K) a b. Hence, d D,Σ μ (K) Δd D,Σ μ (K).

Thus, while Pareto operators exhibit a better behaviour than operators in terms of core IC properties (Pareto operators satisfy (IC5) and operators do not), distancebased d,f operators have an inferential power stronger than Pareto ones (under conditions on f which are often met).

Related Work Notions of consensus have been considered in several AI settings, e.g., in multi-agent systems (Ephrati and Rosenschein 1996), where a consensus is derived from voting agents and results in maximizing some social utility, or within the Dempster-Shafer theory (Jøsang 2002); however, none of these works is about belief merging. The other way around, (Creignou et al. 2016) introduce refined BM operators, suited to some specific fragments of propositional logic (e.g., the Horn fragment). Among other things, the authors show that no refinement of a distance-based merging operator relying on Σ or GMax satisfies (IC6) when the Horn fragment is targeted. This is similar to what happens in our setting when (CO) must be satisfied in presence of (IC2). That said, (Creignou et al. 2016) is not about consensus. (Konieczny, Marquis, and Schwind 2011) point out independence postulates corresponding to some rationalization principles (the fact of repairing the input bases for discarding the models of them which do not satisfy the integrity constraints). Similarly to our work, the authors study how those postulates interact with the IC postulates. That said, the motivations of the two works are dissimilar. Indeed, reaching a consensus is useful when the agents involved are reluctant to change, while making a rationalization step consists in modifying the input bases. Thus, the results obtained in (Konieczny, Marquis, and Schwind 2011) are different from ours. Notably, the property of independence by rationalization by expansion or revision is compatible with the IC postulates, while consensus is not. (Benferhat, Lagrue, and Rossit 2014) analyze sum-based merging operators suited to profiles K of ranked belief bases (such bases K are multisets of pairs (ϕ, k) where k is the rank of the formula ϕ, a positive integer reflecting its plausibility). In this setting, every interpretation ω has a rank for K, equal to 0 when ω satisfies every formula in K and to the largest rank of a formula of K that ω falsifies otherwise. The rank of ω for K is the sum of its ranks for each base from K. The models of the beliefs corresponding to a profile K w.r.t. the operator ΔΣ are the interpretations having the smallest rank for K. The authors then introduce a merging operator Σ suited to the case when no commensurability assumption between the ranks considered in the bases of K can be made. A compatible scale is defined as any mapping updating the ranks of the formulae in every base ϕ of K while preserving the relative ordering of the formulae in ϕ. As to Σ, ω1 is at least as preferred as ω2 for K if the rank of ω1 is not strictly greater than the rank of ω2 for any profile obtained from K by applying a compatible scale to it. At a first glance, some concepts look quite similar to our own work. To be more precise, the authors define a consensus condition:

(CSS) ϕi K, if ϕi |= μ, then ϕi Δμ(K) is consistent,

and show that, unlike ΔΣ, Σ satisfies it. They also show that Σ can be characterized by a Pareto ordering over propositional interpretations, and does not to satisfy any of the postulates (IC6) and (IC8), just as our Pareto-based consensus operators. However, a closer inspection shows that our results differ from those reported in (Benferhat, Lagrue, and Rossit 2014) on many aspects. This can be explained

by the fact that the two merging settings under consideration ranked belief bases merging vs. flat belief bases distance-based merging are quite different. In the former setting, the same formula can be associated with two distinct ranks in two distinct bases, so that the rank of an interpretation ω for a base ϕ does not solely depend on ω and on the formulae occurring in ϕ. Contrastingly, in our setting, no ranks are considered and the distance of an interpretation ω to ϕ depends only on ω and the models of ϕ. Thus, Σ does not belong to our family of Pareto consensus operators. Furthermore, while they look similar, the (CSS) postulate is actually strictly weaker than (CO): the antecedent part of (CSS), ϕi |= μ, is strictly stronger than the antecedent part of (CO), ϕi μ is consistent. Finally, most results in (Benferhat, Lagrue, and Rossit 2014) are about the issue of determining the postulates satisfied by ΔΣ and Σ, while our main results are about the compatibility of (CO) with the IC postulates (thus, one does not focus on specific operators). In particular, our incompatibility result (cf. Proposition 2) is not of the same nature as the impossibility result provided in (Benferhat, Lagrue, and Rossit 2014) (cf. Proposition 12) which concerns ΔΣ. (Gauwin, Konieczny, and Marquis 2007) investigate how merging operators can be used to reach a consensus through a conciliation operator, i.e., a mapping from the set of belief profiles to the set of belief profiles. Conciliation operators are defined iteratively: at each step, every agent revises her belief according to the merged base, from which a new belief profile is derived. Then, this merge-then-revise process is repeated until a consensus is eventually reached. This approach is different from ours in several aspects. First, conciliation operators are induced by merging and revision operators, while our notion of consensus operator does not rely on a revision operator. Second, several iterations are typically required in a conciliation process to get a consensus while our consensus operators are required to achieve the goal in a single step. Third, in (Gauwin, Konieczny, and Marquis 2007) a consensus is reached when K μ is consistent, whereas our consensus condition only requires each base consistent with μ to be consistent with the merged base (which does not impose to reach a common agreement). (Everaere, Konieczny, and Marquis 2008) introduced:

(temperance) ϕi K, ϕi Δ (K) is consistent.

which is close to (CO). Actually, (temperance) corresponds to the specific case of (CO) when the integrity constraint μ is valid. The authors prove a result similar to Proposition 2, showing that (temperance) is incompatible with the conjunction of (IC2) and (IC6). They also introduce a merging operator Δdiff, based on a notion of closeness diff(ω, ϕ), measured as the set of all minimal subsets of variables (w.r.t. ) which have to be flipped in ω for making it a model of ϕ. The aggregation function used is set-product. Among other things, the authors show that Δdiff, satisfies (temperance). However, Δdiff, does not satisfy (CO): when ϕ1 = { a}, ϕ2 = {a b}, and μ = (a b) ( a b), we have that Δdiff, μ ({ϕ1, ϕ2}) a b; and thus ϕ1 μ is consistent, while ϕ1 Δdiff, μ ({ϕ1, ϕ2}) is inconsistent. As a consequence, Δdiff, is neither a Pareto consensus operator

nor a operator induced by an IC merging operator. Lastly, our notion of consensus C for K under μ departs from the one considered in (Gr egoire, Konieczny, and Lagniez 2016), in which it is required that C n i=1 ϕi {μ} and {μ} C. An important difference concerns the syntax-sensitivity dimension. In (Gr egoire, Konieczny, and Lagniez 2016), replacing any ϕi K by an equivalent base may easily lead to a different consensus. This is not the case in our approach as soon as the merging operator satisfies (IC3) (and this is ensured by the merging operators we focus on). Clearly enough, when μ , our notion of consensus generalizes the one considered in (Gr egoire, Konieczny, and Lagniez 2016): a consensus should be a (conjunctively interpreted) subset of the union of all bases from the profile, while in our approach it could be any propositional formula. For this reason, using our approach, more information-preserving consensuses can be established in many cases. For instance, if K = {{a b}, { a b}} (and μ ), the unique consensus according to (Gr egoire, Konieczny, and Lagniez 2016) is the empty set, while in our approach {b} is an acceptable consensus. Lastly, while the main contribution of (Gr egoire, Konieczny, and Lagniez 2016) is about computational aspects of consensus generation, our work can be viewed instead as an axiomatic study of the consensus condition in propositional merging.

Conclusion In this paper, we have stated a consensus condition in propositional BM and proved that it is incompatible with the standard IC postulates. We have then introduced two classes of consensus operators, satisfying a large subset of IC postulates and exhibiting a reasonable behaviour from the inferential standpoint. A perspective for further research consists in identifying the computational complexity of the inference problem for the Pareto and operators. The question whether a representation theorem can be found in order to characterize all operators that satisfy (CO) plus all standard postulates except (IC6) and (IC8), will also be investigated.

Acknowledgments This work was supported by JSPS KAKENHI Grant Number JP17K12746.

References Baral, C.; Kraus, S.; Minker, J.; and Subrahmanian, V. S. 1992. Combining knowledge bases consisting of first-order theories. Computational Intelligence 8(1):45 71. Benferhat, S.; Lagrue, S.; and Papini, O. 2005. Revision of partially ordered information: Axiomatization, semantics and iteration. In IJCAI 05, 376 381. Benferhat, S.; Lagrue, S.; and Rossit, J. 2014. Sum-based weighted belief base merging: From commensurable to incommensurable framework. International Journal of Approximate Reasoning 55(9):2083 2108. Creignou, N.; Papini, O.; R ummele, S.; and Woltran, S. 2016. Belief merging within fragments of propositional logic. ACM Trans. Comput. Log. 17(3):20:1 20:28.

Ephrati, E., and Rosenschein, J. S. 1996. Deriving consensus in multiagent systems. Artificial Intelligence 87(1-2):21 74. Everaere, P.; Konieczny, S.; and Marquis, P. 2008. A diffbased merging operator. In NMR 08, 19 25. Everaere, P.; Konieczny, S.; and Marquis, P. 2010. Disjunctive merging: Quota and gmin merging operators. Artificial Intelligence 174(12-13):824 849. Everaere, P.; Konieczny, S.; and Marquis, P. 2012. Compositional belief merging. In KR 12, 603 607. Everaere, P.; Konieczny, S.; and Marquis, P. 2014. On egalitarian belief merging. In KR 14, 121 130. Gauwin, O.; Konieczny, S.; and Marquis, P. 2007. Conciliation through iterated belief merging. Journal of Logic and Compution 17(5):909 937. Gr egoire, E.; Konieczny, S.; and Lagniez, J.-M. 2016. On consensus extraction. In IJCAI 16, 1095 1101. Jøsang, A. 2002. The consensus operator for combining beliefs. Artificial Intelligence 141(1/2):157 170. Katsuno, H., and Mendelzon, A. O. 1991. Propositional knowledge base revision and minimal change. Artificial Intelligence 52(3):263 294. Konieczny, S., and P erez, R. P. 1999. Merging with integrity constraints. In ECSQARU 99, 233 244. Konieczny, S., and Pino P erez, R. 2002a. Merging information under constraints: a logical framework. Journal of Logic and Computation 12(5):773 808. Konieczny, S., and Pino P erez, R. 2002b. On the frontier between arbitration and majority. In KR 02, 109 118. Konieczny, S., and Pino P erez, R. 2011. Logic based merging. Journal of Philosophical Logic 40:239 270. Konieczny, S.; Lang, J.; and Marquis, P. 2004. DA2 merging operators. Artificial Intelligence 157:49 79. Konieczny, S.; Marquis, P.; and Schwind, N. 2011. Belief base rationalization for propositional merging. In IJCAI 11, 951 956. Konieczny, S. 1999. Sur la logique du changement : r evision et fusion de bases de connaissance. Ph.D. Dissertation, Universit e de Lille 1. Konieczny, S. 2000. On the difference between merging knowledge bases and combining them. In KR 00, 135 144. Liberatore, P., and Schaerf, M. 1998. Arbitration (or how to merge knowledge bases). IEEE Transactions on Knowledge and Data Engineering 10:76 90. Lin, J. 1996. Integration of weighted knowledge bases. Artificial Intelligence 83:363 378. Revesz, P. Z. 1997. On the semantics of arbitration. International Journal of Algebra and Computation 7:133 160. Schwind, N.; Inoue, K.; Bourgne, G.; Konieczny, S.; and Marquis, P. 2015. Belief revision games. In AAAI 15, 1590 1596. Schwind, N.; Inoue, K.; Bourgne, G.; Konieczny, S.; and Marquis, P. 2016. Is promoting beliefs useful to make them accepted in networks of agents? In IJCAI 16, 1237 1243.