Quota and Gmin Merging Operators

1 Introduction

Merging operators aim at de�ning the beliefs (resp. goals) of a group of agents from their individual beliefs (resp. goals). The merging problem in the propositional setting has been addressed in many works, both from the arti�cial intelligence community and the database community [Cholvy, 1993; Revesz, 1997; Liberatore and Schaerf, 1998; Lin and Mendelzon, 1999; Baral et al., 1991; 1992; Konieczny and Pino P·erez, 2002a]. It is also close to important issues considered in Social Choice Theory [Arrow, 1963; Moulin, 1988; Arrow et al., 2002].

Each operator is more or less suited to the many merging scenarios which can be considered. Subsequently, when facing an application for which merging is required, a �rst dif�- culty is the choice of a speci�c merging operator. Among the criteria which can be used to make a clever choice, are the following ones:

Rationality: A main requirement for adhering to a merging method is that it offers the expected properties of what intuitively �merging� means. This calls for sets of rationality postulates and this has been addressed in several papers [Revesz, 1997; Liberatore and Schaerf, 1998; Konieczny and Pino P·erez, 2002a]. In the following, we focus on the rationality postulates given in [Konieczny and Pino P·erez, 2002a], because they extend other proposals. The more (w.r.t. set inclusion) postulates satis�ed the more rational the operator.

Computational Complexity: When one looks for a merging operator for an autonomous multi-agent system, a natural requirement is computational ef�ciency. In the worst case, merging is not a computationally easy task, and query answering typically lies at the �rst or even the second level of the polynomial hierarchy. Computationally easier operators can be obviously preferred to more complex ones.

Strategy-proofness: It is usually expected for merging that agents report truthfully their beliefs/goals. For many applications, this assumption can easily be made, in particular when the agents have limited reasoning abilities. However, when rational agents with full inference power are considered, such an assumption must be questioned: agents can be tempted to misreport their beliefs/goals in order to achieve a better merging result from their point of view. Strategy-proof operators must be preferred in such a case.

Discriminating Power: Because information is typically hard to be acquired, another important criterion to compare merging operators is cautiousness: merging operators which preserve only few information from the individual bases cannot be considered as valuable ones. Thus, it is natural to prefer operators leading to consistent merged bases that are as strong as possible from an inferential point of view.

As to rationality, one can look at [Revesz, 1997; Liberatore and Schaerf, 1998; Lin and Mendelzon, 1999; Konieczny, 2000; Konieczny and Pino P·erez, 2002a; Konieczny et al., 2002]. As to computational complexity, see [Konieczny et al., 2002], and for a study of strategy-proofness of many merging operators, a recent reference is [Everaere et al., 2004] (see also [Meyer et al., 2001] for a related study concerning OCF merging operators). In light of those results, it appears that no merging operator is a better performer than any other operator with respect to the four criteria. To be more precise modelbased operators 1 are often computationally easier (inference is typically Θp2 -complete or ∆p2 -complete) than formulabased ones (inference can be Πp2 -complete) [Konieczny et al., 2002]. Model-based operators also typically satisfy more rationality postulates (see [Konieczny and Pino P·erez, 2002a; Konieczny, 2000]). The third criterion is much more dif�- cult to satisfy for both families of operators, even in very restricted cases. Actually, most of the merging operators identi�ed so far in the literature are not strategy-proof. Since the four evaluation criteria appear hard to be satis�ed altogether, one cannot do better than searching for good trade-offs.

1 A distinction between model-based operators, which select some interpretations that are the �closest� to the bases, and formula-

We consider in this paper two families of propositional merging operators. The �rst one consists of quota merging operators. They rely on a simple idea: any possible world is viewed as a model of the result of the merging when it satis�es �suf�ciently many� bases from the given pro�le. �Suf�- ciently many� can mean either �at least k� (any integer, absolute quota), or �at least k%� (a relative quota), or �nally �as many as possible�, and each interpretation gives rise to a speci�c merging operator. We show that those operators exhibit good logical properties, have low computational complexity and are strategy-proof. Since this is achieved at the price of a potential lack of discriminating power, we introduce a second family of merging operators: Gmin operators. Each Gmin operator is parameterized by a pseudo-distance and each of them is intended to re�ne the quota operators (i.e., to preserve more information). Such operators are both more rational and more discriminating than quota merging operators. Unfortunately, this improvement has to be paid by a higher computational complexity, and more strategic vulnerabilities, but we think they offer an interesting compromise nevertheless.

Note that aggregation functions close to the ones on which quota and Gmin operators are based are used to deal with relational structures that are more complex than bipartitions of worlds (which are the structures under consideration in standard propositional logic). For instance, they have been considered in the possibilistic logic setting and for constraint satisfaction problems (see e.g. [Dubois et al., 1999; 1998; Fargier, 1994]). However, as far as we know, no systematic study of quota and Gmin operators has been conducted so far in the standard propositional setting. Especially, they have never been evaluated with respect to the four criteria we consider. This is where the main contribution of the paper lies.

The rest of the paper is as follows. The next section gives some notations and de�nitions. In Section 3, quota operators are de�ned and their properties are studied. In Section 4, we de�ne △kmax , which is the operator obtained when optimizing the value of the quota under the constraint that it does not lead to an inconsistent merged base. In Section 5, △GMIN operators are de�ned and their properties are studied. Finally, we conclude this paper in Section 6.

2 Formal Preliminaries

We consider a propositional language L de�ned from a �nite set of propositional variables P and the usual connectives.

An interpretation (or world) is a total function from P to {0, 1}, denoted by a bit vector whenever a strict total order on P is speci�ed. The set of all interpretations is noted W. An

based ones, which pick some formulas in the union of the bases is often made [Konieczny et al., 2002].

interpretation ω is a model of a formula φ ∈ L if and only if it makes it true in the usual truth functional way. [φ] denotes the set of models of formula φ, i.e., [φ] = {ω ∈ W | ω |= φ}.

A base K denotes the set of beliefs/goals of an agent, it is a �nite and consistent set of propositional formulas, interpreted conjunctively. Unless stated otherwise, we identify K with the conjunction of its elements.

A pro�le E denotes the group of agents that is involved in the merging process. It is a multi-set (bag) of belief/goal bases E = {K1, . . . ,Kn} (hence two agents are allowed to exhibit identical bases). We denote by ∧ E the conjunction of bases of E, i.e., ∧ E = K1∧. . .∧Kn, and ∨ E is the disjunction of the bases of E, i.e., ∨ E = K1 ∨ . . . ∨ Kn. A pro�le E is said to be consistent if and only if ∧ E is consistent. The multi-set union is noted ⊔, multi-set containment relation is noted ⊑. The cardinal of a �nite set (or a �nite multi-set) A is noted #(A). We say that two pro�les are equivalent, noted E1 ≡ E2, if there exists a bijection f fromE1 to E2 such that for every φ ∈ E1, φ and f(φ) are logically equivalent.

The result of the merging of the bases of a pro�le E, under the integrity constraints µ, is the merged base denoted △µ(E). The integrity constraints consist of a consistent formula the merged base has to satisfy (it may represent some physical laws, some norms, etc.).

3 Quota Operators

Let us �rst de�ne the quota operators.

De�nition 1 Let k be an integer, E = {K1, . . . ,Kn} be a pro�le, and µ be a formula. The k-quota merging operator, denoted △k , is de�ned in a model-theoretic way as:

Essentially, this de�nition states that the models of the result of the k-quota merging of pro�le E under constraints µ are the models of µ which satisfy at least k bases of E. When there is no con�ict for the merging, i.e., ∧ E ∧ µ is consistent, the result of the merging is simply the conjunction of the bases.

Example 1 Let us consider the following example, with a pro�le E = {K1,K2,K3,K4}, such that [K1] = {100, 001, 101}, [K2] = {001, 101}, [K3] = {100, 000}, [K4] = {111}, and the integrity constraints [µ] = W \ {010, 011}. With quota operators we get as a result [△1µ(E)] = {000, 001, 100, 101, 111}, [△2µ(E)] = {001, 100, 101} and [△3µ (E)] = ∅.

Here is an equivalent syntactical characterization of [△kµ(E)] that is obtained from preferred consistent subsets of E. 2 Let us �rst de�ne the following notation:

Then the following proposition gives a characterization of quota operators :

2 To be more precise, �subsets� stands here for multi-set containment.

Proposition 1 Let k be an integer, E = {K1, . . . ,Kn} be a pro�le, and µ be a formula.

Interestingly, the size of the formula equivalent to [△kµ (E)] given by Proposition 1 is polynomial in |E| + |µ|. Hence, merged bases can be easily compiled as propositional formulas.

3.1 Logical Properties

Since we aim at investigating the logical properties of our family of merging operators, a set of properties must �rst be considered as a base line. The following set of postulates was pointed out in [Konieczny and Pino P·erez, 1999; 2002a]:

De�nition 2 (ICmerging operators) △ is an IC merging operator if and only if it satis�es the following postulates:

• (IC0) △µ(E) |= µ
• (IC1) If µ is consistent, then △µ(E) is consistent
• (IC2) If ∧ E is consistent with µ, then △µ(E) ≡ ∧ E ∧ µ (IC3) If E1 ≡ E2 and µ1 ≡ µ2, then △µ1 (E1) ≡△µ2 (E2)
• (IC4) If K1 |= µ and K2 |= µ, then △µ({K1,K2}) ∧ K1 is consistent if and only if △µ({K1,K2}) ∧K2 is consistent

• (IC6) If △µ(E1) ∧△µ(E2) is consistent, then △µ(E1 ⊔ E2) |= △µ(E1) ∧ △µ(E2)

An IC merging operator is said to be an IC majority operator if it satis�es (Maj)

Quota merging operators exhibit good logical properties.

Proposition 2 △k operators satisfy properties (IC0), (IC2), (IC3), (IC4), (IC5), (IC7) and (IC8). They do not satisfy (IC1), (IC6) and (Maj) in general.

Only two properties of IC merging operators are not satis�ed: (IC1) 3 since the result of the quota merging can be inconsistent (see Example 1), and (IC6).

Beside those general properties, some speci�c additional properties, are satis�ed by quota operators.

3 It is possible to make (IC1) satis�ed by requiring that, when no interpretation reaches the quota (i.e., satis�es at least k bases), the merged base is equivalent to the integrity constraints formula. But this de�nition leads to operators which do not satisfy (IC5). This last property is very important from an aggregation point of view. It corresponds to a Pareto condition, that is considered as a minimal rationality requirement for aggregation in Social Choice Theory [Arrow, 1963; Moulin, 1988; Arrow et al., 2002]. This is why we do not consider such an additional family of operators any longer in the following.

Interestingly, the disjunction property (Disj) is not shared by every IC majority merging operator [Konieczny and Pino P·erez, 2002a], since most of them allow for �generating� some new beliefs/goals from the ones in the bases of the pro�le (some interpretations that do not satisfy any of the bases can be chosen as models of the merged base). When this behaviour is unexpected, formula-based merging operators � which satisfy (Disj) � can be used, but such operators do not satisfy many rationality postulates [Konieczny, 2000] (especially (IC3) is not satis�ed) and are often hard from a computational point of view. Quota operators (as well as the other operators studied in this paper) which also ensure (Disj) offer interesting alternatives to formula-based operators in this respect.

Two other interesting postulates can be de�ned for characterizing more precisely quota operators; the �rst one is a weakening of (Maj), which is not satis�ed by every IC merging operator:

The second one shows the prominence of the largest maximal consistent subsets of the pro�le; let us de�ne Maxconsµ(E) as {M | M ⊑ E, ∧ M ∧ µ is consistent,

Proposition 3 △k operators satisfy properties (Disj), (Card) and (Wmaj).

Note that it is not the case that every IC majority merging operator satis�es (Card) (see Section 5).

3.2 Computational Complexity

Let △ be a merging operator. We consider the following decision problem MERGE(△):

• Input : a triple 〈E, µ, α〉 where E = {K1, . . . ,Kn} is a pro�le, µ ∈ L is a formula, and α ∈ L is a formula.
• Question : Does △µ(E) |= α hold?

For quota merging operators, we can prove that:

Proposition 4 MERGE(△k ) is BH(2)-complete.

This BH(2)-completeness result is obtained even in the restricted case the query is a propositional symbol and there is no integrity constraints (µ = ⊤). Note that this complexity class is located at a low level of the boolean hierarchy. And that, obviously, the complexity of MERGE(△k ) decreases to coNP whenever k is not lower than the number of bases of E (or under the restriction ∧ E ∧ µ is inconsistent). 3.3 Strategy-Proofness

Let us now investigate how robust quota operators are with respect to manipulation. Intuitively, a merging operator is strategy-proof if and only if, given the beliefs/goals of the other agents, reporting untruthful beliefs/goals does not enable an agent to improve her satisfaction. A formal counterpart of it is given in [Everaere et al., 2004]:

De�nition 3 Let i be a satisfaction index, i.e., a total function from L×L to IR. A merging operator ∆ is strategy-proof for i if and only if there is no integrity constraint µ, no pro�le E = {K1, . . . , Kn}, no base K and no base K ′ such that i(K, ∆µ(E ⊔ {K′})) > i(K, ∆µ(E ⊔ {K})).

Clearly, there are numerous different ways to de�ne the satisfaction of an agent given a merged base. While many ad hoc de�nitions can be considered, the following three indexes from [Everaere et al., 2004] are meaningful when no additional information are available:

De�nition 4

For the weak drastic index (idw ), the agent is considered satis�ed as soon as its beliefs/goals are consistent with the merged base. For the strong drastic index (ids ), in order to be satis�ed, the agent must impose her beliefs/goals to the whole group. The last index (�probabilistic index� ip) is not a boolean one, leading to a more gradual notion of satisfaction. The more compatible the merged base with the agent's base the more satis�ed the agent. The compatibility degree of K with K∆ is the (normalized) number of models of K that are models of K∆ as well.

Proposition 5 Quota merging operators are strategy-proof for ip, idw and ids .

This is quite noticeable since strategy-proof merging operators are not numerous [Everaere et al., 2004]. Strategyproofness is hard to achieve, as illustrated in Social Choice Theory, for aggregation of preference relations, by the Gibbard-Satterthwaite impossibility theorem [Gibbard, 1973; Satterthwaite, 1975; Moulin, 1988].

3.4 Absolute and Relative Quotas

In the de�nition of quota merging operators, an absolute threshold, i.e., a �xed integer not depending on the number of bases in the pro�le, has been used. On the other hand, it can prove also sensible to express quota in a relative manner, and to de�ne the models of the merged base as the interpretations satisfying at least half (or the two third, or the wanted ratio) of the initial bases. This technique is close to a wellknown voting method used in Social Choice Theory, namely voting in committees [Barber�a et al., 1991]. Let us call such operators k-ratio merging operators (with 0 ≤ k ≤ 1), and let us note them△k .

One can quickly �gure out the close connections between the two families of quota merging operators (the one based on absolute quota and the other one on relative quota, or ratio). Each ratio merging operator corresponds to a family of quota merging operators (one for each possible cardinal of the pro�le). And given a �xed cardinal, each (absolute) quota merging operator corresponds to a family of ratio merging operators.

Although the intuitive motivations of the two de�nitions of those families look different, it turns out that ratio merging operators have exactly the same properties w.r.t. computational complexity and strategy-proofness as (absolute) quota merging operators (though the proofs of some results are different). Only some logical properties are different.

Proposition 6 △k operators satisfy properties (IC0), (IC2), (IC3), (IC4), (IC5), (IC7), (IC8), (Maj), (Disj) and (Card). They do not satisfy (IC1) and (IC6) in general.

4 △kmax Operator

Now, whatever the chosen quota is absolute or not, an important point is the choice of its value. Let us �rst observe that quota merging operators lead to a sequence of merged bases that is monotonic w.r.t. logical entailment:

Proposition 7 Let E be a pro�le, µ be a formula. We have △k+1 µ (E) |=△kµ (E) for all integers k.

Among the elements of this sequence, some of them are of special interest. Thus, △0 gives the conjunction of the bases (with the constraints) when consistent and µ otherwise. It is called full meet merging operator in [Konieczny and Pino P·erez, 1999]. △1 gives the conjunction of the bases (with the constraints) when consistent and the disjunction of the bases (with the constraints) otherwise; it is closed to the basic merging operator [Konieczny and Pino P·erez, 1999], and is also de�nable as a model-based merging operator obtained using the drastic distance and max as aggregation function [Konieczny et al., 2002]. The only difference is that △1 gives an inconsistent result when the disjunction of the bases is not consistent with the constraints, whilst the basic merging operator gives µ in this case.

Each time k is increased, the result of the merging is either the same as for the previous value of k or is logically stronger. In our �nite propositional framework, the sequence (△kµ (E))(k > 0) is obviously stationary from some stage. The value for which it becomes stationary is not interesting in itself, since the corresponding merged base is either equivalent to the conjunction of the bases of the pro�le (with the constraints), or to the inconsistent base. But an interesting value of k is the one leading to the last nontrivial merged base.

De�nition 5 Let E = {K1, . . . ,Kn} be a pro�le, µ be a formula. Let kmax = max({i ≤ #(E) | △iµ (E) ̸|= ⊥}). △kmax is de�ned in a model-theoretic way as:

While very close to quota operators, the resulting operator △kmax is not a true quota operator since the value of kmax is not given a priori, but depends on E and µ.

At a �rst glance, △kmax looks similar to the formula-based operator ∆C4 which selects cardinality-maximal subbases in the union of the bases from the pro�le [Konieczny, 2000; Baral et al., 1991; 1992]; however, △kmax and ∆C4 are distinct; thus, while both operators satisfy (Disj), △kmax satis�es (IC3) and (Maj) while ∆C4 satis�es none of them. Contrastingly, △kmax belongs to two important families of modelbased merging operators, namely the △Σ family and the △GMax family when the drastic distance is used [Konieczny and Pino P·erez, 2002b]. Accordingly, △kmax has very good logical properties:

Proposition 8 △kmax satis�es (IC0 - IC8), (Maj), (Disj) and (Card).

△kmax is obtained by considering the problem of optimizing the quota (for �pure� quota operators, k is given, so it does not need to be computed). Unsurprisingly, the corresponding inference problem is computationally harder than the inference problem for quota operators (under the standard assumptions of complexity theory):

Clearly enough, if kmax is computed during an off-line preprocessing stage and becomes part of the input afterwards, the complexity falls down to coNP.

Now, as to strategy-proofness, the kmax operator exhibits all the good properties of quota operators.

Proposition 10 △kmax is strategy-proof for the three indexes ip, idw and ids .

5 △GMIN Operators

Starting from△kmax , one could wonder whether it is possible to constrain further the quota operators so as to get operators with a higher discriminating power, i.e,. allowing more inferences to be drawn. In this section we provide a full family of such operators.

In order to de�ne a △GMIN operator, the de�nition of a pseudo-distance between interpretations is �rst needed:

De�nition 6 A pseudo-distance between interpretations is a total function d from W ×W to IN such that for every ω1, ω2 ∈ W

• d(ω1, ω2) = d(ω2, ω1), and
• d(ω1, ω2) = 0 if and only if ω1 = ω2.

Any pseudo-distance between interpretations d induces a �distance� between an interpretation ω and a formula K given by d(ω, K) = minω′ |=K d(ω, ω′ ).

Examples of some such distances are the drastic distance, noted dD, that gives 0 when ω1 = ω2 and 1 otherwise, or the Dalal distance [Dalal, 1988], noted dH, that is the Hamming distance between interpretations.

Then △d,GMIN µ operators are de�ned as:

De�nition 7 Let d be a pseudo-distance, µ an integrity constraint, E = {K1, . . . , Kn} a pro�le and let ω be an interpretation. The �distance� dd,Gmin(ω, E) is de�ned as the list of numbers (d1, . . . , dn) obtained by sorting in increasing order the set {d(ω,Ki) | Ki ∈ E}. The models of △d,GMIN µ (E) are the models of µ that are minimal w.r.t. the lexicographic order induced by the natural order.

Example 1 (continued) [△dD,GMIN µ (E)] = {001, 100, 101}. [△dH ,GMIN µ (E)] = {101}. The computations are reported in Table 1. Each column Ki gives the �distance� dH(ω,Ki) between the models of the integrity constraints and Ki.

Clearly enough, △kmax is a speci�c Gmin operator:

As far as discriminating power is concerned, △GMIN operators are interesting operators, since they re�ne the operator ∆kmax (so they re�ne also every quota merging operator), as stated by the following property:

Proposition 12 For any pseudo-distance d, any integrity constraint µ and any pro�le E, we have

Furthermore, Gmin operators exhibit very good logical properties:

Proposition 13 Let d be any pseudo-distance. △d,GMIN satis�es (IC0 - IC8), (Maj) and (Disj). It does not satisfy (Card) in general.

Thus, like formula-based merging operators, △GMIN operators satisfy (Disj), but contrariwise to formula-basedmerging operators, △GMIN operators are IC merging operators.

Let us now investigate the strategy-proofness issue for the △GMIN operators. In the general case, strategy-proofness of quota merging operators is lost:

Proposition 14 Let d be a pseudo-distance. △d,GMIN is not strategy-proof for any index among the three indexes idw , ip and ids .

We can guarantee strategy-proofness, but only in some very speci�c cases:

Proposition 15

• △d,GMIN is strategy-proof for ip, idw and ids if the bases are complete (i.e. each base has a unique model),
• △d,GMIN is strategy-proof for the indexes idw and ids when #(E) = 2 and µ = ⊤.

Finally, let us turn to the computational complexity criterion.

Proposition 16 Assume that the pseudo-distance d of any pair of interpretations ω1 and ω2 can be computed in time polynomial in |ω1| + |ω2|. Then MERGE(△d,GMIN ) is in ∆p2 .

Proposition 17

• MERGE(△dD,GMIN ) is Θp2 -complete.
• MERGE(△dH,GMIN ) is ∆p2 -complete.

As expected, the complexity of inference for △d,GMIN operators is higher than the complexity of inference for quota operators (under the usual assumptions of complexity theory). However, it remains at the �rst level of the polynomial hierarchy under reasonable requirements on the pseudo-distance.

6 Conclusion

We have considered two families of merging operators, and investigated the properties of their operators with respect to four criteria: rationality, computational complexity, strategyproofness and discrimating power. We claim that those four criteria are the main dimensions along with propositional merging operators have to be evaluated.

While no merging operators optimizing every criteria exist, we claim that both quota and Gmin operators are interesting trade-offs; even if they are not fully rational and discriminating, quota operators exhibit �low complexity� and are strategy-proof; on the other hand, Gmin operators are slightly more complex and not strategy-proof in the general case, but they are fully rational and much less cautious. They also lead to merged bases implying the disjunction of the bases from the considered pro�le, thus offering an interesting alternative to formula-basedmerging operators [Baral et al., 1991; 1992; Konieczny, 2000; Konieczny et al., 2002], which are typically at least as hard from the complexity point of view and satisfy less rationality postulates.

Acknowledgements

The authors would like to thank the anonymous reviewers. This work has been supported by the IUT de Lens, the Universit·e d'Artois, the R·egion Nord/Pas-de-Calais, the IRCICA consortium, and by the European Community FEDER Program.