Belief Merging without Distance Measures

Abstract

When information comes from di erent sources inconsistent beliefs may appear. To handle inconsistency, several model-based belief merging operators have been proposed. Starting from the beliefs of a group of agents which might con ict, these operators return a unique consistent belief base which represents the beliefs of the group. The operators, parameterized by a distance between interpretations and aggregation function, usually only take into account consistent bases. Consequently some information which is not responsible for con icts may be ignored. This paper presents P S-M erge, an alternative way of merging which is based on the notion of Partial Satis ability. The proposal uses an alternative way of measuring the satisfaction of a formula since Partial Satis ability lets us have satisfaction values in the interval [0,1]. P S-M erge produces similar results to other merging approaches. Actually, in order to achieve satisfactory results for di erent scenarios from the literature we require di erent merging operators while the proposal obtains similar results for all these di erent scenarios with a unique operator, P S-M erge.

-

Belief merging is concerned with the process of combining the information contained in a set of (possibly inconsistent) belief bases obtained from different sources to produce a single consistent belief base. Belief merging is an important issue in arti cial intelligence and databases, and its applications are many and diverse [ 2 ]. For example, in multiagent systems a merging operator de nes the beliefs of a group of agents according to the beliefs of each member of the group. When agents have con icting beliefs about the \true" state of the world, belief merging can be used to determine the \true" state of the world for the group. Though we consider only belief bases, merging operators can typically be used for merging either beliefs or goals.

Several merging operators have been de ned and characterized in a logical way. Among them, model-based merging operators [ 10, 7, 15, 11 ] obtain a belief base from a set of interpretations with the help of a distance measure on interpretations and an aggregation function. Usually, model-based merging operators only take into account consistent belief bases and consequently some information which is not responsible for con icts may be ignored. Other merging operators, syntax-based ones [1], are based on the selection of some consistent subsets of the set-theoretic union of the belief bases. This allows for taking inconsistent belief bases into account, but such operators usually do not take into account the frequency of each explicit item of belief. For example, the fact that a formula is believed in a base or in n bases is not considered relevant, which is counter-intuitive.

An alternative method of merging uses the notion of Partial Satis ability to de ne P S-M erge, a model-based merging operator which depends on the syntax of the belief bases [ 3 ]. The proposal produces similar results to other merging approaches, but while other approaches require many merging operators in order to achieve satisfactory results for di erent scenarios the proposal obtains similar results for all these di erent scenarios with a unique operator. It is worth noticing that P S-M erge is not based on distance measures on interpretations, and takes into account inconsistent bases and the frequency of each explicit item of belief. We study some logical properties satis ed by P S-M erge and analyze the rational behavior of the operator.

The rest of the paper is organized as follows. After providing some technical preliminaries, Section 3 describes the notion of Partial Satis ability and the associated merging operator. Section 4 studies some properties satis ed by P S-M erge in the context of postulates proposed in [ 7, 8 ]. In Section 5 we give a comparison of P S-M erge with other approaches and Section 6 concludes with a discussion of future work. 2

Preliminaries

We consider a language L of propositional logic formed from a nite ordered set P := fp1; p2; :::; png of atoms in the usual way. And we use the standard terminology of propositional logic except for the de nitions given below. A belief base K is a nite set of propositional formulas of L representing the beliefs of an agent (we identify K with the conjunction of its elements).

A state or interpretation is a function w from P to f1; 0g, these values are identi ed with the classical truth values true and f alse respectively. The set of all possible states will be denoted as W and its elements will be denoted by vectors of the form (w(p1); :::; w(pn)). A model of a propositional formula Q is a state such that w(Q) = 1 once w is extended in the usual way over the connectives. For convenience, if Q is a propositional formula or a set of propositional formulas then P(Q) denotes the set of atoms appearing in Q. jP j denotes the cardinality of set P . A literal is an atom or its negation.

A belief pro le E denotes the beliefs of agents K1; :::; Km that are involved in the merging process. If Q1i ; :::; Qni denotes the beliefs in the base Ki, then E = ffQ11 ; :::; Qn1 g; :::; fQ1m ; :::; Qnm gg. E is a multiset (bag) of belief bases and thus two agents are allowed to exhibit identical bases.

Two belief pro les E1 and E2 are said to be equivalent, denoted by E1 E2, i there is a bijection g from E1 to E2 such that K g(K) for every base K in E1. With V E we denote the conjunction of the belief bases Ki 2 E, while t denotes the multiset union. For every belief pro le E and positive integer n, En denotes the multiset union of n times E. 3

Partial Satis ability

In order to de ne Partial Satis ability without loss of generality we consider a normalized language so that each belief base is taken as the disjunctive normal form (DNF) of the conjunction of its elements. Thus if K = fQ1; :::; Qng is a belief base we will identify this base with QK = DN F (Q1 ^ ::: ^ Qn). The DNF of a formula is obtained by replacing A $ B and A ! B by (:A _ B) ^ (:B _ A) and :A _ B respectively, applying De Morgan's laws, using the distributivity law, distributing _ over ^ and nally eliminating the literals repeated in each conjunct.

Example 1. Given the belief base K = fa ! b; :cg it is identi ed with QK = (:a ^ :c) _ (b ^ :c).

The last part of the construction of the DNF (the minimization by eliminating literals) is important since the number of literals in each conjunct a ects the satisfaction degree of the conjunct. We are not applying other logic minimization methods to reduce the size of the DNF expressions since this may a ect the intuitive meaning of the formulas. A further analysis of logic equivalence and the results obtained by the Partial Satis ability is required.

De nition 1 (Partial Satis ability). Let K be a belief base, w any state of W and jP j = n, we de ne the Partial Satis ability of K for w, denoted as wps(QK ), as follows.

If QK := C1 ^ ::: ^ Cs where Ci are literals then wps(QK ) = max

i=1 ( s

X w(Ci) ; n s jP(QK )j ) 2n If QK := D1 _ ::: _ Dr where each Di is a literal or a conjunction of literals then wps(QK ) = max fwps(D1); :::; wps(Dr)g

The intuitive interpretation of Partial Satis ability is as follows: it is natural to think that if we have the conjunction of two literals and just one is satis ed then we are satisfying 50% of the conjunction. If we generalize this idea we can measure the satisfaction of a conjunction of one or more literals as the sum of the evaluation of them under the interpretation divided by the number of conjuncts. However, the agent's beliefs may consider only some atoms of the language, in that case the agent is not a ected by the decision taken over the atoms not appearing in its beliefs. Hence it is indi erent to the evaluation of these atoms, so we interpret this indi erence as a partial satisfaction of 50% for each atom not appearing in its beliefs.

On the other hand the agent is interested in satisfying the literals that appear in its beliefs and we interpret this fact by assigning a satisfaction of 100% to each literal veri ed by the state and 0% to those that are falsi ed. As we can see the former intuitive idea is re ected in De nition 1 since the literals that appear in the agent beliefs have their classical value and atoms not appearing have a value of just 12 .

Finally, if we have a disjunction of conjunctions the intuitive interpretation of the valuation is to obtain the maximum value of the considered conjunctions.

Example 2. The Partial Satis ability of the belief base of Example 1 given P = fa; b; cg and w = (1; 1; 1) is wps(QK ) = max nmaxf w(:a)+2w(:c) ; 16 g; maxf w(b)+2w(:c) ; 16 go = 12 .

Instead of using distance measures as [ 7, 11, 8, 12 ] we have proposed the notion of Partial Satis ability in order to de ne a new merging operator. The elected states of the merge are those whose values maximize the sum of the Partial Satis ability of the bases.

De nition 2. Let E be a belief pro le obtained from the belief bases K1; :::; Km, then the Partial Satis ability Merge of E denoted by P S-M erge(E) is a mapping from the belief pro les to belief bases such that the set of models of the resulting base is: ( w 2 W Example 3. We now give a concrete merging example taken from [ 14 ]. The author proposes the following scenario: a teacher asks three students which among three languages, SQL, Datalog and O2, they would like to learn. Let s, d and o be the propositional letters used to denote the desire to learn SQL, Datalog and O2, respectively, then P = fs; d; og. The rst student only wants to learn SQL or O2, the second wants to learn only one of Datalog or O2, and the third wants to learn all three languages. So we have E = fK1; K2; K3g with K1 = f(s _ o) ^ :dg, K2 = f(:s ^ d ^ :o) _ (:s ^ :d ^ o)g, and K3 = fs ^ d ^ og.

In [ 12 ] using the Hamming distance applied to the anonymous aggregation function and in [ 7 ] using the operator , both approaches obtain the states (0; 0; 1) and (1; 0; 1) as models of the merging.

We have QK1 = (s ^ :d) _ (o ^ :d), QK2 = (:s ^ d ^ :o) _ (:s ^ :d ^ o), and QK3 = s ^ d ^ o. As we can see in the fth column of Table 1 the models of P S-M erge(E)1 are the states (0; 0; 1) and (1; 0; 1).

w (1; 1; 1) (1; 1; 0) (1; 0; 1) (1; 0; 0) (0; 1; 1) (0; 1; 0) (0; 0; 1) (0; 0; 0)

In [ 8 ] two classes of merging operators are de ned: majority and arbitration merging. The former strives to satisfy a maximum of agents' beliefs and the latter tries to satisfy each agent beliefs to the best possible degree. The former notion is treated in the context of P S-M erge, and it can be re ned tending to arbitration if we calculate the minimum value among the Partial Satis ability of the bases. Then with this indicator, we have a form to choose the state that is impartial and tries to satisfy all agents as far as possible. If we again consider Example 3 in Table 1 there are two di erent states that maximize the sum of the Partial Satisfaction of the pro le, (1; 0; 1) and (0; 0; 1). If we try to minimize the individual dissatisfaction these two states do not provide the same results. Using the min function (see 6th column of Table 1) over the partial satisfaction of the bases we get the states that minimize the individual dissatisfaction and between the states (1; 0; 1) and (0; 0; 1) obtained by the proposal we might prefer the state (1; 0; 1) over (0; 0; 1) as the GMax operator (an arbitration operator) does in [ 7 ].

It is possible to extend this notion of P S-M erge in the case where a set of integrity constraints must be obeyed. If is a formula representing the set of integrity constraints, then the states that falsify the integrity constraint cannot be considered in the P S-M erge. If W( ) denotes the set of states that validate the integrity constraints, it is enough to restrict the de nition of the Partial Satis ability Merge to W( ).

1If is a merging operator, we are going to abuse the notation by referring to the models of the merging operator mod( (E)) and their respective belief base (E) simply as (E). De nition 3. Let E be a belief pro le obtained from the belief bases K1; :::; Km, then P S-M erge (E), the Partial Satis ability Merge of E given the set of integrity constraints , is a mapping from the belief pro les to belief bases such that the set of models of the resulting base is: ( w 2 W( ) Example 4. The following example of information merging under constraints is given in [ 8 ]. At a meeting of four co-owners of a block of ats, the chairman proposes the construction of a swimming-pool, a tennis-court and a private-car-park in the coming year. But if two of these three items are built, the rent will increase signi cantly. We will denote by s, t and p the construction of the swimming-pool, the tennis-court and the private car-park respectively and i will denote the increase of the rent. Two coowners want to build the three items, and do not care about the rent increase (K1 = K2 = s ^ t ^ p), the third thinks that building any item will cause at some time an increase of the rent and wants to pay the lowest rent so he is opposed to any construction (so K3 = :s ^ :t ^ :p ^ :i) and nally the last one thinks that the at really needs a tennis-court and a private car-park but does not want a rent increase (i.e. K4 = t ^ p ^ :i).

The chairman outlines that building two or more items will increase the rent signi cantly. This fact cannot be ignored and the states in which this fact is falsi ed must be ignored. These kinds of facts are known as integrity constraints. In the example the integrity constraints are represented by the single formula ((s ^ t) _ (s ^ p) _ (t ^ p)) ! i. If we consider P the ordered set fs; t; p; ig then the states (1; 1; 1; 0), (1; 1; 0; 0), (1; 0; 1; 0) and (0; 1; 1; 0) cannot be considered as a possible Partial Satis ability Merge since these states falsify the integrity constraint. It is enough to calculate the Partial-Satis ability to states in W( ).

The answer to Example 4 obtained by applying P S-M erge (see Table 2) is the state (1; 1; 1; 1), i.e. the decision that satis es the majority of the group is to build the three items no matter if the rent increases. This decision is also the one obtained using the integrity constraint majority merging operator based on the function in [ 8, 9 ]. 4

Properties

Finding a set of axiomatic properties that an operator may satisfy in order to exhibit a rational behavior is a concern greatly studied. In [ 7, 15, 10, 11 ] sets of postulates have been proposed concerning belief merging operators.

In [ 7, 9 ] Konieczny and Pino-Perez proposed the basic properties (A1)(A6) for merging operators, rephrased without reference to integrity constraints.

De nition 4. Let E, E1, E2 be belief pro les, and K1 and K2 be consistent belief bases. Let be an operator which assigns to each belief pro le E a belief base (E). is a merging operator if and only if it satis es the following postulates: (A1) (E) is consistent (A2) if V E is consistent then (E) V E (A3) if E1 E2, then (E1) (E2) (A4) (fK1; K2g) ^ K1 is consistent if and only if consistent (A5) (E1) ^ (E2) j= (E1 t E2) (A6) if (E1) ^ (E2) is consistent, then (fK1; K2g) ^ K2 is (E1 t E2) j= (E1) ^ (E2)

The intuitive meaning of the postulates is as follows: (A1) ensures the extraction of a piece of information from the pro le. (A2) states that if the belief bases agree on some alternatives, then the result of the merging will be these alternatives. (A3) ensures that the operator obeys a principle of irrelevance of syntax. (A4) is the fairness postulate, such that when we merge two bases the operator should not give preference to one of them. (A5) expresses the following: if we have two groups viewed as pro les E1 and E2, and E1 compromises a set of alternatives to which A belongs, and E2 compromises another set which also contains A, then if we join the two groups A must be in the chosen alternatives. (A5) and (A6) together state that if one could nd two groups which agree on at least one alternative, then the result of the global merging will be exactly these alternatives.

We analyze the minimal set of properties P S-M erge satis es and its rational behavior concerning merging. Clearly P S-M erge satis es (A1), which simply requires of the result of merging to be consistent. P S-M erge also satis es (A2).

Proposition 1. V E 2 ? implies P S-M erge(E) V E: Proof. Let E = fQK1 ; :::; QKm g be a pro le with its belief bases expressed in DNF such that V E 2 ?. There are l > 0 states w1; :::; wl that satisfy each base thus for every state wr we can nd m disjoints d1; :::; dm belonging to each base QK1 ; :::; QKm respectively, that are satis ed by wr. Consequently the Partial Satis ability of the bases for every wr is evaluated in 1, i.e. wrps(QKj ) = 1 for 1 r l and 1 j m. So we can a rm that Pm

i=1 wrps(QKi ) = m for each model of the pro le. Notice that every disjoint can have either of two values Pis=1 w(sCi) or n jP2n(dj)j (see De nition 1). Moreover the rst value is less or equal to 1 and the second one is less or equal to 2nn = 12 . From this fact we can a rm that if a state w does not satisfy a base QK then wps(QK ) < 1 and we can conclude that Pim=1 wps(QKi ) < m for the states that do not satisfy the pro le. Hence a state w is included in the merge i w is a model of V E, i.e. we obtain only models of the conjunction of the bases as a result of P S-M erge when the pro le is consistent.

The next property (A3) is a version of Dalal's principle of the Irrelevance of Syntax [ 4 ]. In general, P S-M erge does not satisfy (A3). Consider the situation, called implicit knowledge in [ 6 ], where systems want to extract additional knowledge that is not locally held by any agent. For example, if an agent knows a and another agent knows a ! b, then combining their knowledge yields b, whereas neither one of them individually knows it. Using most of the merging operators we can nd the expected result. Now suppose that this situation is presented in the mind of an agent, i.e. both facts a and a ! b are known by an agent who does not know how to combine the facts in order to produce b and hence its beliefs in DNF are K1 = (a^:a)_(a^b). On the other hand suppose another agent who knows explicitly that a and b hold, i.e. its beliefs in DNF are K2 = a ^ b. We can see that both agents' bases are equivalent. Now using P S-M erge to combine the bases with another agent's base K3 = :b, we obtain the states (1; 0) and (0; 0) from merging K1 and K3 and only the state (1; 0) from merging K2 and K3. P S-M erge is a majority operator which tries to satisfy each base as much as possible. Hence in the rst case the maximum percentage of satisfaction for K1 is 50% if it wants to leave a percentage of satisfaction for K3 di erent from 0%, noticing that state (1; 0) satis es a and (0; 0) satis es a ! b. In the second case where K2 is satis ed 50% by (1; 0), we can see that if the agent knows explicitly the facts then P S-M erge re nes the answer. We can also see that even though (A3) is not satis ed by P S-M erge, the results show a realistic behavior. The result of combining information without making inferences beforehand might not be as detailed as when agents nd some consequences of their knowledge before the merging.

In general, P S-M erge does not satisfy (A4). Consider again K1 = (a ^ :a) _ (a ^ b) and K3 = :b. We can see that both bases are consistent by themselves, however, their conjunction is not. As we know from the example above, using P S-M erge to combine them we obtain the states (1; 0) and (0; 0) which clearly favor K3. Here it is important to notice that K1 shows an indecision :a _ b of the agent that is why the merging process prefers the satisfaction of the \con dent" source K3. However, if P S-M erge takes as parameters bases showing only explicit information, for example K2 = a ^ b and K3 = :b, the merging process does not lead to a preference for any of them. The result of the example is state (1; 0) which is not the models of either base.

If there is no \redundant" information, i.e. formulas including disjoints of the style a ^ :a, then (A3) and (A4) are satis ed. P S-M erge satis es the property (A4) under certain restrictions.

Proposition 2.

(fK1; K2g) ^ K1 2 ? i (fK1; K2g) ^ K2 2 ?: (A5) and (A6) establish connections between two results; the result obtained when merging each of two belief pro les and then taking their conjunction and the result obtained when rst combining the two belief pro les and then performing a single merge. Together the two properties require that these two results be equivalent, provided that the conjunction referenced is not inconsistent. P S-M erge satis es (A5) but it is necessary to consider that pro les come from di erent contexts and they can have di erent languages. In this case it will be necessary to extend the language of E1 to include the atoms appearing in E2 and vice versa.

Proposition 3. If P(E1) = P(E2) then P S-M erge(E1)^P S-M erge(E2) j= P S-M erge(E1 t E2) Proof. If P S-M erge(E1) ^ P S-M erge(E2) is consistent then each model w of the conjunction maximizes the Partial Satisfaction of E1 and E2 at tPhekis2aEm1 ewpt0sim(QeKbie)caanudsePwkiis2Em2owdpesl(QofKeia)ch mPekrig2iEng2.wIp0.se(.QPKik)i2fEo1rwaplls(wQ0 K2i )W. The merging of the union of the pro les is simply the sum of the Partial Satisfaction of the pro les E1 and E2. Then for all w0 2 W:

X ki2E1tE2 wp0s(QKi )

X ki2E1tE2 wps(QKi ) =

X wps(QKi ) +

X wps(QKi ) ki2E1 X wp0s(QKi ) + ki2E2

X wp0s(QKi ) = ki2E1 ki2E2 Remark 1. By de nition the P S-M erge is commutative. I.e. the result of the merging does not depend on any order of the bases of the pro le.

As stated before there are two important classes of merging operators, majority and arbitration operators. The behavior of majority operators is to say that if an opinion is the most popular, then it will be the opinion of the group. A postulate that captures this idea is the postulate (M7) of [ 7 ]. (M7) 8K9n 2 N

(E t fKgn) j= K

P S-M erge satis es the postulate (M7) as a direct consequence of the de nition of P S-M erge. Even more, the de nition of P S-M erge not only tries to satisfy the majority of the group, it also tries to satisfy to the maximum degree (see for example 10 in the following section). P S-M erge does not satisfy all the postulates (A1)-(A6), however, it behaves as a majority merging operator. As the reader can see in the next section the behavior of P S-M erge is close to and CM erge which are majority operators. 5

Comparing results

P S-M erge yields similar results compared with existing techniques such as CM erge, the 2 operator and M CS (Maximal Consistent Subsets) considered in [ 11, 7, 8 ]. Let E be in each case the belief pro le consisting of the belief bases enlisted below and let P be corresponding set of atoms ordered alphabetically.

1. K1 = K2 = fag and K3 = f:ag. CM erge(E) = fag which is equivalent to P S-M erge(E) = (E) = f(1)g. 2. K1 = fbg, K2 = fa; a ! bg and K3 = f:bg. Here CM erge(E) = fa; a ! bg which is equivalent to P S-M erge(E) = (E) = f(1; 1)g. 3. K1 = f g

b , K2 = fa; bg and K3 = f:bg. In this case CM erge(E) and the model obtained from (E) and P S-M erge(E) are as in the previous case. 4. K1 = fbg, K2 = K3 = fa ! bg and K4 = fa; :bg. CM erge(E) = fa; a ! bg and P S-M erge(E) = (E) = f(1; 1)g which are all equivalent. 5. K1 = fa; cg, K2 = fa ! b; :cg and K3 = fb ! d; cg. In this case CM erge(E) = fa; a ! b; b ! d; cg which is equivalent to P SM erge(E) = (E) = f(1; 1; 1; 1)g.

2As stated in [ 7 ], merging operator is equivalent to the merging operator proposed by Lin and Mendelzon in [ 11 ] called CM erge. 6. K1 = fa; cg, K2 = fa ! b; :cg, K3 = fb ! d; cg and K4 = f:cg.

While CM erge(E) =M CS(E) =fa; a ! b; b ! dg which is equivalent to (E) = f(1; 1; 0; 1); (1; 1; 1; 1)g, P S-M erge(E) = f(1; 1; 0; 1)g. CM erge, M CS and the operator give no information about c. Using P S-M erge, c is falsi ed and this leads us to have total satisfaction of the second and fourth bases and partial satisfaction of the rst and third bases. 7. K1 = fag, K2 = fa ! bg and K3 = fa; :bg. Now CM erge(E) = fag, (E) = f(1; 1); (1; 0)g and P S-M erge(E) = f(1; 1)g. The model (1; 0) satis es only two bases while the model (1; 1) satisfy two bases and a \half" of the third base. 8. K1 = fag, K2 = fa ! bg, K3 = fa; :bg and K4 = f:bg. In this case CM erge(E) = fa ^ :bg, which is equivalent to P S-M erge(E) = (E) = f(1; 0)g. 9. K1 = fbg, K2 = fa ! bg and K3 = fa; :bg. Now CM erge(E) = fa ^ bg and P S-M erge(E) = (E) = f(1; 1)g. 10. K1 = fbg, K2 = fa ! bg, K3 = fa; :bg and K4 = f:bg. In this case CM erge(E) = fa _ :bg, (E) = f(0; 0); (1; 0); (1; 1)g and P SM erge(E) = f(1; 1); (0; 0)g. The model (1; 0) obtained using operator satis es only two bases, while the two options of P S-M erge(E) satisfy two bases and a \half" of the third base. Then P S-M erge is a re nement of the answer given by CM erge and . 11. K1 = K2 = fa ^ b ^ cg, K3 = f:a ^ :b ^ :c ^ :dg and K4 = fb ^ c ^ :dg with the restriction that if two of a, b or c are validated it forces d to be validated as well. CM erge(E) = fa ^ b ^ c ^ dg, P S-M erge(E) = (E) = f(1; 1; 1; 1)g. 6

Conclusion

A merging operator has been proposed in [ 3 ] that is not de ned in terms of a distance measure on interpretations, but is Partial Satis ability-based. It appears to resolve con icts among the belief bases in a natural way. The idea is intended to extend the notion of satis ability to one that includes a \measure" of satisfaction. This notion of satisfaction considers that whenever an atom does not appear in a formula then it is considered that the agent has no preferences on this atom so a partial satisfaction di erent from 0 is assigned. In De nition 1 we chose 21 . This measure considers the intuitive idea that an \or" is satis ed if any of its disjoints is satis ed and in the case of an \and" we count the number of conjuncts satis ed; but if none then we count the partial satisfaction of the atoms not appearing in the conjunction. We can think that a state always satis es a formula by a percentage, which is given by the Partial Satis ability. Once a satisfaction measure of belief bases is given, it is used to de ne P S-M erge. Unlike the operators proposed in the literature, in order to know the \degree" of satisfaction by a given state, P S-M erge does not need to calculate a partial pre-order over the set of states since Partial Satis ability can be calculated for a single state. In this way the comparison between states becomes easier. This property can be used in many real-world collective decision problems, as a set of alternatives is given and the method selects a collectively preferred belief base from the set of candidates. However, it is necessary to take into account that before calculating the Partial Satis ability of a formula it is necessary to transform it into DNF.

Unlike other approaches P S-M erge can consider belief bases which are inconsistent, since the source of inconsistency can refer to speci c atoms and the operator takes into account the rest of the information.

The approach bears some resemblance to the belief merging framework proposed in [ 7, 8, 11, 12 ], particularly with the operator. As with those approaches the Sum function is used, but instead of using it to measure the distance between the states and the pro le P S-M erge uses Sum to calculate the general degree of satis ability. The result of P S-M erge are simply the states which maximize the Sum of the Partial Satis ability of the pro le and it is not necessary to de ne a partial pre-order. Because of this similarity between P S-M erge and we propose to analyze this similarity in term of the postulates satis ed by outlined in [ 7, 8 ]. In this paper we analyzed some of these postulates, and even though the P S-M erge does not satisfy all the properties cited in [ 7, 11 ] it has a rational behavior.

As in [ 8 ] in order to consider integrity constraints P S-M erge selects the states among the states which validate the integrity constraints rather than those in W. The approach behaves as a majority operator but an arbitration operator can also be de ned in terms of Partial Satis ability in a similar way.

As future work a further analysis of the P S-M erge is necessary to characterize its behaviour in terms of postulates. As well, study of the properties of the approach including integrity constraints is required. It remains for the de nition of an arbitration operator in terms of Partial Satis ability and the corresponding characterization to be considered. It is necessary to study the complexity of the whole process of the P S-M erge in order to compare it with the existing techniques. Finally, we intend to combine the proposal with a heuristic for solving problems with combinatorial explosion.

References

[1] C. Baral, S. Kraus, J. Minker, and V. Subrahmanian. Combining knowledge bases consisting of rst-order theories. Computational Intelligence,

References

[2] I. Bloch and A. Hunter . Fusion: General concepts and characteristics . International Journal of Intelligent Systems , 10 ( 16 ): 1107 { 1134 , 2001 .

[3] V. Borja Mac as and P. Pozos Parra. Model-based belief merging without distance measures . In Procceedings of the Sixth International Conference on Autonomous Agents and Multiagent Systems , pages 613 { 615 , Honolulu , Hawai'i , 2007 . ACM.

[4] M. Dalal . Investigations into a theory of knowledge base revision . In Procceedings of the 7th National Conference of the American Association for Arti cial Intelligence , pages 475 { 479 , Saint Paul , Minnesota, 1988 .

[5] P. Everaere , S. Konieczny , and P. Marquis . The strategy-proofness landscape of merging . Journal of Arti cial Intelligence Research , 28 , 2007 .

[6] J. Halpern and Y. Moses . A guide to completeness and complexity for modal logics of knowledge and belief . Arti cial Intelligence , 3 ( 54 ): 319 { 379 , 1992 .

[7] S. Konieczny and R. Pino-Perez . On the logic of merging . In A. G. Cohn, L. Schubert , and S. C. Shapiro, editors, KR'98: Principles of Knowledge Representation and Reasoning , pages 488 { 498 . Morgan Kaufmann, 1998 .

[8] S. Konieczny and R. Pino-Perez . Merging with integrity constraints . Lecture Notes in Computer Science , 1638 , 1999 .

[9] S. Konieczny and R. Pino-Perez . Merging information under constraints: a logical framework . Journal of Logic and Computation , 12 ( 5 ): 773 { 808 , 2002 .

[10] P. Liberatore and M. Schaerf . Arbitration (or how to merge knowledge bases) . IEEE Transactions on Knowledge and Data Engineering , 10 ( 1 ): 76 { 90 , 1998 .

[11] J. Lin and A. Mendelzon . Knowledge base merging by majority . In R. Pareschi and B . Fronhoefer, editors, Dynamic Worlds: From the Frame Problem to Knowledge Management . Kluwer Academic, 1999 .

[12] T. Meyer, P. Pozos, and L. Perrussel . Mediation using m-states . In Proceedings of Eighth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU) , pages 489 { 500 , 2005 .

[13] P. Pozos Parra and V. Borja Mac as. Partial satis ability-based merging . In Proceedings of the Sixth Mexican International Conference on Arti cial Intelligence , pages 225 { 235 , 2007 .

[14] P. Z. Revesz . On the semantics of theory change: Arbitration between old and new information . In Proceedings of the Twelfth ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems , pages 71 { 82 , 1993 .

[15] P. Z. Revesz . On the Semantics of Arbitration . Journal of Algebra and Computation , 7 ( 2 ): 133 { 160 , 1997 .