Nicolas Schwind
email: nicolas-schwind@aist.go.jp

Pierre Marquis
email: marquis@cril.fr

On Consensus in Belief Merging

We define a c onsensus p ostulate i n t he p ropositional 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 c onsensus 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., [START_REF] Lin | Integration of weighted knowledge bases[END_REF][START_REF] Revesz | On the semantics of arbitration[END_REF][START_REF] Liberatore | Arbitration (or how to merge knowledge bases)[END_REF]Konieczny and Pino Pérez 2002a;[START_REF] Konieczny | Logic based merging[END_REF]. The second step calls for revision policies, as considered in [START_REF] Schwind | Belief revision games[END_REF]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 h er p rior b eliefs ϕ 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 c onsensus 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 µ.

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érez 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érez 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.

Among them is the basic merging operator ∆ b (Konieczny and Pérez 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 [START_REF] Liberatore | Arbitration (or how to merge knowledge bases)[END_REF]. 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 L P 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. 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 µ, M C(K, µ) denotes the set of maximal subsets of bases from K which are jointly consistent with µ, that is,

M C(K, µ) = {K ⊆ K | K ∧ µ |= ⊥, ∀K ⊆ K, K K ⇒ K ∧ µ |= ⊥}. Lastly, M C(K, µ) denotes the set K ∈M C(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érez 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 K 1 ≡ K 2 and µ 1 ≡ µ 2 , then ∆ µ1 (K 1 ) ≡ ∆ µ2 (K 2 ); (IC4) If ϕ 1 |= µ, ϕ 2 |= µ and ∆ µ ({ϕ 1 , ϕ 2 }) ∧ ϕ 1 is con- sistent, then ∆ µ ({ϕ 1 , ϕ 2 }) ∧ ϕ 2 is consistent; (IC5) ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) |= ∆ µ (K 1 K 2 ); (IC6) If ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) is consistent, then ∆ µ (K 1 K 2 ) |= ∆ µ (K 1 ) ∧ ∆ µ (K 2 ); (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

K 1 = {ϕ 1,1 , . . . , ϕ 1,n } and K 2 = {ϕ 2,1 , . . . , ϕ 2,n }, K 1 ≡ K 2 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érez 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érez 2002a;[START_REF] Everaere | Disjunctive merging: Quota and gmin merging operators[END_REF]): (Maj), (Arb) and (Disj), that respectively characterize the class of majority, arbitration (Konieczny and Pino Pérez 2002a) and disjunctive [START_REF] Everaere | Disjunctive merging: Quota and gmin merging operators[END_REF] operators:

(Maj) ∃n ≥ 1 ∆ µ (K 1 K 2 . . . K 2 n ) |= ∆ µ (K 2 ). (Arb) If ∆ µ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 [START_REF] Konieczny | DA 2 merging operators[END_REF]. 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 in- terpretations induced by K defined by ω ≤ d,f K ω if and only if d f (ω, K) ≤ d f (ω , K), where d f (ω, 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 [START_REF] Konieczny | DA 2 merging operators[END_REF])) but taking advantage of usual aggregation functions as Σ, GMax and GMin [START_REF] Everaere | Disjunctive merging: Quota and gmin merging operators[END_REF]) lead to IC merging operators.

Example 1 (continued) Let L P 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érez 1999) defined by:

∆ d µ (K) = K ∧ µ if consistent, µ otherwise;
and of the basic merging operator ∆ b (Konieczny and Pérez 1999) defined by:

∆ b µ (K) =      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." Therefore, as we are interested in consensus operators satisfying (IC2), (IC6) must be set aside.

ω ϕ 1 ϕ 2 ϕ 3 Σ GMax GMin P ar ∇ d D ,f ϕ 1 ϕ 2 ϕ 3 Σ GMax GMin P ar ∇ d H ,GMin ∇ d H ,Σ/GMax 000 d = d D 0 1 1 d = d H 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
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 ∈ M C(K, µ) and (ii) ∀ϕ j ∈ K, ϕ j / ∈ M C(K, µ) ⇒ ϕ j ∧ µ |= ϕ i ∧ µ.
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 ) de- note 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 , µ). We now prove (ii). We already got that ∆ µ (K) |= ϕ i ∧ µ. Let ϕ j / ∈ M C(K, µ). By using the contrapositive of (i) on ϕ j , we get ϕ j ∧ µ |= ∆ µ (K). Hence, ϕ j ∧ µ |= ϕ i ∧ µ. This concludes the proof.

ϕ i ∈ K, ϕ i ∧ µ |= ∆ µ (K). We prove (i) ϕ i ∈ M C(K, µ). Assume towards a contradiction that ϕ i / ∈ M C(K, µ). Since ϕ i ∧ µ |= ⊥, M C(K, µ) = ∅. So let S ⊆ M C(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 ∈ M C(K
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 M C(K, µ); and (ii) each one these bases (in conjunction with µ) necessarily entails each base that belongs to all maximal consistent subsets from M C(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 ∈M C(K,µ) K ∧ µ |= ∆ µ (K).
Proposition 9 states that in presence of (IC0) and (IC8), the disjunction of all maximal consistent subsets of M C(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érez 2002b):

(IC6') If ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) is consistent, then ∆ µ (K 1 K 2 ) |= ∆ µ (K 1 ) ∨ ∆ µ (K 2 ).
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érez 2002b). Among them are the Max operators (Konieczny and Pino Pérez 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 [START_REF] Konieczny | Sur la logique du changement : révision et fusion de bases de connaissance[END_REF]) 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 [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF], and revision operators of interest yet not satisfying (R6) have been proposed in the literature (Katsuno and Mendelzon 1991; [START_REF] Benferhat | Revision of partially ordered information: Axiomatization, semantics and iteration[END_REF] 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.

Related Work

Notions of consensus have been considered in several AI settings, e.g., in multi-agent systems [START_REF] Ephrati | Deriving consensus in multiagent systems[END_REF], where a consensus is derived from voting agents and results in maximizing some social utility, or within the Dempster-Shafer theory [START_REF] Jøsang | The consensus operator for combining beliefs[END_REF]; however, none of these works is about belief merging. The other way around, [START_REF] Creignou | Belief merging within fragments of propositional logic[END_REF]) 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, [START_REF] Creignou | Belief merging within fragments of propositional logic[END_REF]) is not about consensus. (Konieczny et al. 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 et al. 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. [START_REF] Benferhat | Sum-based weighted belief base merging: From commensurable to incommensurable framework[END_REF] 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. [START_REF] Benferhat | Sum-based weighted belief base merging: From commensurable to incommensurable framework[END_REF] 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 considered in [START_REF] Benferhat | Sum-based weighted belief base merging: From commensurable to incommensurable framework[END_REF] and concepts used in our own work look quite similar. To be more precise, [START_REF] Benferhat | Sum-based weighted belief base merging: From commensurable to incommensurable framework[END_REF]) 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 [START_REF] Benferhat | Sum-based weighted belief base merging: From commensurable to incommensurable framework[END_REF]) on many aspects, and do not follow from them. 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 et al. 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 (Proposition 2) is not of the same nature as the "impossibility" result provided in [START_REF] Benferhat | Sum-based weighted belief base merging: From commensurable to incommensurable framework[END_REF]) (Proposition 12) which concerns ∆ Σ . [START_REF] Gauwin | Conciliation through iterated belief merging[END_REF]) 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 [START_REF] Gauwin | Conciliation through iterated belief merging[END_REF]) 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). [START_REF] Everaere | A diff-based merging operator[END_REF]) present a postulate:

(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 [START_REF] Grégoire | On consensus extraction[END_REF], in which it is required that C ⊆ n i=1 ϕ i ∪{µ} and {µ} ⊆ C. An important difference concerns the syntax-sensitivity dimension. In [START_REF] Grégoire | On consensus extraction[END_REF], 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 [START_REF] Grégoire | On consensus extraction[END_REF]: 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 [START_REF] Grégoire | On consensus extraction[END_REF] is the empty set, while in our approach {b} is an acceptable consensus. Lastly, while the main contribution of [START_REF] Grégoire | On consensus extraction[END_REF]) 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.

  [ϕ] denotes the set of models of the formula ϕ, i.e., [ϕ] = {ω ∈ W | ω |= ϕ}. |= denotes logical entailment and ≡ logical equivalence, i.e., ϕ |= ψ iff [ϕ] ⊆ [ψ] and ϕ ≡ ψ iff [ϕ] = [ψ].

Table 1 :

 1 The BM operators ∆ d,Σ , ∆ d,GMax , ∆ d,GMin , ∆ d,P ar and ∇ d,f for d ∈ {d D , d H } and f ∈ {Σ, GMax, GMin}. 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[START_REF] Konieczny | On the difference between merging knowledge bases and combining them[END_REF] and the quota operators[START_REF] Everaere | Disjunctive merging: Quota and gmin merging operators[END_REF]; and this is also why weaker postulates (like (IC6b) introduced in (Everaere et al. 2014) 2 ) have been previously considered.

Details of the computations are reported in Table1.

(IC6b) requires that if ∆µ(ϕ1) ∧ . . . ∧ ∆µ(ϕn) is consistent, then ∆µ(ϕ1, . . . , ϕn) |= ∆µ(ϕ1) ∧ . . . ∧ ∆µ(ϕn).

Acknowledgments

This work was supported by JSPS KAKENHI Grant Number JP17K12746.

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

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

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

This is actually always the case for any distance d and any aggregation function f satisfying the (strict monotonicity) property [START_REF] Everaere | Compositional belief merging[END_REF], (which is offered by standard aggregation functions as GMax, GMin and Σ):

Proposition 12 Let d be any distance and f be an aggregation function satisfying (strict monotonicity). For every profile K and formula µ, we have

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 M C(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

Proposition 13 states that ∆ d D ,P ar µ (K) is equivalent to the disjunction of the maximal consistent subsets of M C(K, µ). It is worth noting that ∆ d D ,P ar corresponds to the combination function Comb 1 introduced in [START_REF] Baral | Combining knowledge bases consisting of first-order theories[END_REF] and studied in [START_REF] Konieczny | On the difference between merging knowledge bases and combining them[END_REF]. 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

then ∇ satisfies (IC4) and (CO).

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 .

3 If 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

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 [START_REF] Liberatore | Arbitration (or how to merge knowledge bases)[END_REF]. Let us recall that the arbitration operator induced by a belief revision operator • is defined by [START_REF] Liberatore | Arbitration (or how to merge knowledge bases)[END_REF], and that, for a given BM operator ∆, the induced belief revision operator • ∆ is defined by ϕ 1 • ∆ ϕ 2 = ∆ ϕ2 ({ϕ 1 }) (Konieczny and Pino Pérez 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érez 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

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: 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).