Belief Merging Operators as Maximum Likelihood Estimators

1 Introduction

The aggregation of pieces of information, encoding preferences, beliefs or judgments, that are owned by a number of agents, is a key challenge in many settings, among social choice, vote, merging, or judgment aggregation. Whatever the setting, the design of aggregation operators is typically guided either by axiomatic concerns, or by epistemic concerns. In the former case, expected properties (postulates) are exhibited, and operators satisfying them are pointed out or impossibility theorems are proved. In the latter case, it is assumed that the preferences, beliefs or judgments that are reported by the agents are a noisy perception of "correct" preferences, beliefs or judgments. Such an epistemic approach have received great attention when dealing with preferences [Young, 2003; Conitzer and Sandholm, 2005; Xia et al., 2010; Conitzer, 2014; Elkind and Slinko, 2016; Pivato, 2012], and can be traced back at least to Condorcet, who justified the use of majoritarian vote in this way (his famous jury theorem [Condorcet, 1785]). Contrastingly, the epistemic interpretation of belief merging operators gave rise to few research work (we know a single paper about it, it is discussed in the related work section).

Propositional belief merging operators aim to associate a belief base with a set of (usually conflicting) belief bases representing the individual beliefs of the agents. So far, belief merging operators have been evaluated with respect to several criteria, such as rationality properties leading to the so-called IC merging operators [Konieczny and Pino Pérez, 2002a; Konieczny and Pino Pérez, 2011], properties inspired by vote [Haret et al., 2016], computational complexity [Konieczny et al., 2004], strategy-proofness [Everaere et al., 2007], etc. In this work, we want to evaluate belief merging operators as maximum likelihood estimators (MLE). One assumes that there exists a true state of the world ω⋆ (represented by a specific propositional interpretation) and that each agent participating in the merging process receives a noisy signal of it (a formula Ki). The objective is then to aggregate the agents' belief bases to make the best possible guess about ω⋆ . The key issue we want to address is to determine the extent to which belief merging operators are suited to this objective, i.e., to figure out how the corresponding merged bases and ω⋆ are connected.

In the following, we provide a number of results in this direction. First, we present some logical connections between rationality postulates for merging (IC postulates) and simple conditions (especially about independence) over the noise model P under consideration. We also rationalize a large family of distance-based IC merging operators ∆ by showing that for each operator ∆ of the family, there exists a noise model P such that ∆ is a MLE for P. Then we focus on two specific noise models. For the first one, the world swap noise, we show that a standard distance-based merging operator based on the drastic distance is a MLE. And for the second one, the atom swap noise, we show that the distancebased merging operator based on the sum and the Hamming distance is a MLE. Finally, we report some empirical results showing that those two distance-based merging operators are efficient noise cancellers in practice, meaning that the number of agents needed for identifying the true state of the world with high probability remains small enough.

The rest of the paper is organized as follows. In the next section, some formal preliminaries on belief merging are provided. In Section 3, noise models and maximum likelihood estimators are defined in the belief merging setting. In Section 4, conditions under which merging operators are / are not maximum likelihood estimators are pointed out. In Section 5 the focus is laid on the world swap noise, and in Section 6 on the atom swap noise. Section 7 gives some empirical results. Section 8 discusses some related work. Finally, Section 9 concludes the paper. For space reasons only the proofs of some of the main results are provided. A full-proof version of the paper is available on http://www.cril.fr/∼konieczny/ijcai20proofs.pdf.

2 Formal Preliminaries

We consider a propositional language L defined from a finite set P of m propositional variables and the usual connectives. An interpretation (or state of the world) ω is a total function from P to {0, 1}. Ω is the set of all interpretations. An interpretation ω is a model of a formula φ ∈ L if and only if it makes it true in the usual truth-functional way. Otherwise, ω is a counter-model of φ. [φ] denotes the set of models of formula φ, i.e., [φ] = {ω ∈ Ω | ω |= φ}.

A belief base K is a finite set of propositional formulae, interpreted conjunctively (i.e., viewed as the conjunction of its elements). A profile E (of belief bases) is associated with a group of n agents that are involved in the merging process; formally, E is given by a vector of bases E = 〈K1, . . . , Kn〉. ∧ E denotes the conjunction of all elements of E, and ⊔ denotes concatenation. Two profiles E = 〈K1, . . . ,Kn〉 and E′ = 〈K′1 , . . . ,K′n 〉 are said to be equivalent, noted E ≡ E′ , iff there exist a permutation σ such that ∀Ki, we have [Ki] = [K′σ(i) ]. An integrity constraint µ is a formula restricting the possible results of the merging process. A merging operator △ is a mapping which associates with a profile E and an integrity constraint µ a (merged) base △µ(E).

We expect belief merging operators to satisfy the following rationality postulates (the IC postulates):

Definition 1 A merging operator △ is an IC merging operator iff it satisfies the following properties:

• (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
• (IC5) △µ(E1) ∧△µ(E2) |=△µ(E1 ⊔E2)
• (IC6) If △µ(E1) ∧△µ(E2) is consistent, then △µ(E1 ⊔ E2) |= △µ(E1) ∧ △µ(E2)
• (IC7) △µ1 (E) ∧ µ2 |=△µ1∧µ2 (E)
• (IC8) If △µ1 (E) ∧ µ2 is consistent, then △µ1∧µ2 (E) |=△µ1 (E) ∧ µ2

See [Konieczny and Pino Pérez, 2002a] for explanations and justifications of these properties.

Let us give some examples of IC merging operators from the family of distance-based merging operators [Konieczny et al., 2004]. We first need a notion of (pseudo-)distance:

Definition 2 A (pseudo-)distance between interpretations is a mapping d : Ω × Ω → IR+ such that for any ω1, ω2 ∈ Ω:

• d(ω1, ω2) = d(ω2, ω1)
• d(ω1, ω2) = 0 iff ω1 = ω2

Every distance between interpretations can be easily lifted to a "distance" between worlds and formulae, by stating that d(ω, K) = minω′∈[K]d(ω, ω′ ).

Usual distances considered in merging [Konieczny and Pino Pérez, 2002a] are the Hamming distance dH and the drastic distance dD. dH(ω1, ω2) is the number of propositional letters on which the two interpretations differ. dD is such that dD(ω1, ω2) = 0 iff ω1 = ω2, and = 1 otherwise.

One then needs a notion of aggregation function:

Definition 3 An aggregation function is a mapping 1 f from (IR+)p to IR+, which satisfies:

• if xi ≥ x′i , then f(x1, . . . , xi, . . . , xp) ≥ f(x1, . . . , x′i , . . . , xp)
• if ∀i ∈ {1, . . . , p} xi = 0 then f(x1, . . . , xp) = 0
• f(x) = x
• If σ is a permutation over {1, . . . , p}, then f(x1, . . . , xp) = f(xσ(1), . . . , xσ(p))

Many aggregation functions have been pointed out so far, and considered in the belief merging literature. They include sum (Σ), leximin (alias Gmin), leximax (alias Gmax), and Σk (the sum of the kth powers - where k is a fixed integer). Formal definitions can be found, e.g., in [Konieczny and Pino Pérez, 2002a; Everaere et al., 2010b].

Definition 4 Let d and f be respectively a pseudodistance between interpretations and an aggregation function. The distance-based merging operator △d,f is defined by [△d,f µ (E)] =min([µ],≤E), where the total pre-order ≤E on Ω is defined in the following way (with E = 〈K1, . . . , Kn〉):

• ω ≤E ω′ iff d(ω,E) ≤ d(ω′ ,E),
• d(ω,E) = f(d(ω,K1), . . . , d(ω,Kn)).

For many standard aggregation functions, whatever the chosen pseudo-distance d between interpretations, the corresponding distance-based operator △d,f is an IC merging operator [Konieczny and Pino Pérez, 2002a; Everaere et al., 2010b]:

Proposition 1 Let d be any pseudo-distance between interpretations and let f be an aggregation function among Σ, leximin, leximax , or Σk . △d,f is an IC merging operator.

More generally, properties on the aggregation function ensuring that the corresponding distance-based operator is an IC merging operator can be found in [Konieczny et al., 2004].

3 Noise andMaximumLikelihood Estimators

In this work, we assume the existence of a true state of the world, that is represented by an interpretation ω⋆ ∈ Ω. Whenever some integrity constraints µ are available, we assume that ω⋆ is a model of µ, meaning that the integrity constraints are always supposed to hold in the true state of the world. Stated otherwise, integrity constraints are pieces of knowledge, i.e., of true beliefs.

1 Strictly speaking, it is a family of mappings, where a mapping is defined for each positive integer p.

Let I be a set of n agents. We suppose that each agent has a noisy perception of the true state of the world ω⋆ : for every i ∈ I, the base Ki representing the beliefs of agent i corresponds to the perception of ω⋆ by i. The given (observed) profile E = 〈K1, . . . ,Kn〉 thus reflects the noisy perception of the true state of the world by the group of agents.

Because of the noise, there is no guarantee that [Ki] = {ω⋆ } for at least one agent i, or even that there exists any logical connection between E and ω⋆ (for instance, it can be the case that ω⋆ is inconsistent with each Ki in E). However, depending on ω⋆ , the observation of a profile E is more or less plausible given the noise. Formally, a noise model makes precise the connection between ω⋆ and the profiles using probabilities.

Given the worlds ω ∈ Ω and the agents i ∈ I, one considers 2m × n Boolean random variables of the form (ω, i). Each random variable (ω, i) is thus associated with two possible outcomes, the one noted (ω, i), where the random variable (ω, i) takes the truth value true, and the one noted (ω, i), where the random variable (ω, i) takes the truth value false. The fact that (ω, i) takes the truth value true (resp. false) means that the world ω is not discarded (resp. discarded) by the observation achieved by agent i, i.e., ω is a model of Ki (resp. not a model of Ki). O denotes the Cartesian product of the set of outcomes for all the Boolean random variables (ω, i). Every element of O represents (from a semantical point of view) a profile E since it indicates for every world ω ∈ Ω and every agent i ∈ I whether or not ω is a model of Ki. Similarly, every projection of an element of O over the outcomes associated with all the random variables of the form (ω, i) for a fixed i ∈ I represents (again, up to logical equivalence) a belief base Ki. Given those notations, a noise model can be formally defined as follows:

Definition 5 A noise model P is a mapping associating with every consistent formula µ ∈ L and every interpretation ω ∈ [µ] a joint probability distribution, noted Pµ,ω, of the 2m ×n Boolean random variables (ω, i), i.e., Pµ,ω is a probability distribution over O, s.t. the following conditions are satisfied:

• ∀ω′ ∈ Ω, if ω′ ̸|= µ, then ∀i ∈ I, Pµ,ω((ω′ , i)) = 0,
• If µ′ ≡ µ, then Pµ,ω = Pµ′ ,ω.

Since each Pµ,ω is a joint probability distribution, every (non-empty) subset of the 2m × n Boolean random variables of the form (ω, i) corresponds to a marginal probability distribution.

The first condition in Definition 5 states that any interpretation ω′ that violates the given integrity constraint µ will never be reported by any agent as a model of her belief base (stated otherwise, every agent involved in the merging process is supposed to be aware of µ). Thus, the (marginal) probability of such an (impossible) event (ω′ , i) for the random variable (ω′ , i) is 0. The second condition in the definition expresses a form of syntax-independence for the integrity constraint.

A profile E is said to be generated by the noise model P if E is a random variate (outcome) from P. In this work, we observe a single profile E generated by P, and we want to determine whether a merging operator allows to identify the worlds that best explain E, i.e., to find (if it exists) a merging operator that is a maximum likelihood operator for P:

Definition 6 Let P be a noise model. A merging operator ∆P is a maximum likelihood estimator (MLE) for P iff for any consistent formula µ ∈ L and for any profile E generated by P , we have 2 [∆Pµ (E)] = argmaxωPµ,ω(E).

4 IC Postulates, ICOperators andMLEs

We first show that if a merging operator ∆ is a MLE for some noise P (whatever this noise), then ∆must comply with some IC postulates.

Proposition 2 Let P be any noise model. If ∆ is a MLE for P, then ∆ satisfies (IC0), (IC1), (IC3), (IC7) and (IC8).

In general, we can expect noise models to satisfy some additional constraints, like the following independence condition, which is very natural (and is quite standard for voting methods):

Definition 7 A noise model P satisfies the independence condition iff for any for any consistent formula µ ∈ L, any ω ∈ [µ], for each i ∈ I, the set of 2m random variables {(ω, i) | ω ∈ Ω} considered in Pµ,ω is independent from all the remaining random variables.

When P satisfies the independence condition, whatever the true state of the world, the beliefs of any agent are independent from the beliefs of the other agents.

The independence condition rules out some merging operators as MLEs:

Proposition 3 Let P be any noise model satisfying the independence condition. If ∆ is a MLE for P, then ∆ satisfies (IC5) and (IC6).

To sum up, a merging operator that is a MLE for a noise model satisfying the independence condition must satisfy almost all IC postulates. The exceptions are (IC2) (that requires the merged base to be the conjunction of all the bases with the integrity constraints whenever this conjunction is consistent), and (IC4) (that requires an equal treatment of the two bases in any profile containing two bases).

In the literature (see for example [Conitzer and Sandholm, 2005]), another assumption about noise is often considered, namely the uniformity condition:

Definition 8 A noise model P satisfies the uniformity condition iff for any for any consistent formula µ ∈ L, any ω ∈ [µ], ω′ ∈ Ω, any i, j ∈ I, we have Pµ,ω((ω′ , i)) = Pµ,ω((ω′ , j)).

Intuitively, the uniformity condition states that the noise model is the same one for all the agents.

Interestingly, many merging operators (especially IC ones) can be interpreted as MLEs for a noise model satisfying the independence condition and the uniformity condition:

Proposition 4 Let d be any pseudo-distance on interpretations. Let k be any natural number. There exists a noise model P satisfying the independence condition and the uniformity condition such that the merging operators ∆d,Σk and ∆d,leximax are MLEs for P.

2 argmax ω Pµ,ω(E) = {ω ∈ Ω|∀ω′ ∈ Ω, Pµ,ω(E) ≥ Pµ,ω′ (E)}.

Proof: Let ω⋆ |= µ be the true state of the world and E = 〈K1, . . . ,Kn〉 a given profile. Let us define the noise P such that the probability that any world ω is a model of the base associated with any agent j, namely Pµ,ω⋆((ω, j)), is equal to α× 1 2(d(ω,Kj)+1)k , where α is a positive real number that does not depend on j (the uniformity assumption ensures that it exists) and k is a fixed integer.

Due to the independence condition on P , the probability of ω to be a model of every base of E is thus equal to

Then the problem of determining the maximum likelihood estimates of ω⋆ consists in exhibiting the interpretations ω |= µ such that αn 2Σnj=1 ((d(ω,Kj)+1)k) is maximal. Obviously, αn 2Σnj=1 ((d(ω,Kj)+1)k) is maximal if and only if Σnj=1 ((d(ω,Kj) + 1)k ) is minimal, and Σnj=1 ((d(ω,Kj) + 1)k ) is minimal if and only if the weighted sum of Hamming distances of ω to every base from the profile E = 〈K1, . . . ,Kn〉 is minimal. This shows that every ∆d,Σk is a MLE for P .

Finally, it is well-known [Konieczny and Pino Pérez, 2002b] that for a sufficiently large k whatever the pseudo-distance d over interpretations and the profile E = 〈K1, . . . ,Kn〉, two worlds ω and ω′ are such that ∑ni=1 d(ω,Ki)k ≤ ∑ni=1 d(ω′ ,Ki)k if and only if the leximax aggregation of the values d(ω,K1), . . . , d(ω,Kn) is less than or equal to the leximax aggregation of the values d(ω′ ,K1), . . . , d(ω′ ,Kn) w.r.t. the lexicographic ordering. Hence an interpretation ω minimizing the leximax aggregation of the values d(ω,K1), . . . , d(ω,Kn) w.r.t. the lexicographic ordering maximizes the probability Πnj=1 α 2(d(ω,Kj)+1)k when k is sufficiently large. Accordingly, the merging operator ∆d,leximax is also a MLE for P. ✷

Proposition 4 shows that many distance-based merging operators ∆ (namely those for which the aggregation function is one of the Σk or leximax) are rationalizable in the sense that there exists a noise model P such that ∆ is a MLE for P .

The fact that a merging operator can be rationalized as a MLE (i.e., showing that there exists a noise model P such that the operator is a MLE for P ) is a valuable property of the operator when one is interested in making the best possible guess about ω⋆ . Indeed, as already discussed in [Everaere et al., 2010a], merging a profile of belief bases is a useful operation when one wants to synthesize the information given in the profile, i.e., to characterize a belief base which best represents the beliefs of the input profile (the synthesis view of belief merging), or when one wants to best approximate the true state of the world from the information give in the profile (the epistemic view of belief merging). In the second case, rationalizable merging operators must clearly be preferred to non-rationalizable ones. The rationalization property can thus be viewed as an interesting criterion for helping to choose a merging operator that is suited to the epistemic purpose.

In some situations, more information about the noise model P are available, and an interesting issue is then to determine whether a merging operator that is a MLE for the specific noise model P exists. This is a research question that is somewhat converse to the one discussed in the previous paragraphs: instead of starting with a merging operator ∆ and looking for the existence of a noise model P such that ∆ is a MLE for P , one starts with a noise model P and looks for a merging operator ∆ that is a MLE for P .We address this issue in the rest of the paper. To be more precise, two sensible noise models are considered and merging operators that are suited to them are identified.

5 TheWorld Swap Noise

A plausible noise model is obtained by assuming that some interpretations ω of Ω are misperceived (and thus misclassified) by the agents: for an agent i, when ω = ω⋆ (resp. ω ̸= ω⋆ ), it is considered as a counter-model (resp. a model) of Ki. This noise model is parameterized by a (world) swap probability p, which represents the chances of an interpretation to be considered as a model of the beliefs of an agent while it is not the true state of the world. We make the (reasonable) assumption that this probability of error is less than 12 , otherwise the noise would be too important. More formally, the world swap noise model P wsn is a mapping associating with every consistent formula µ ∈ L, every interpretation ω ∈ [µ], the joint probability distribution, noted P wsn µ,ω , of the 2m ×n Boolean random variables (ω′ , i) defined as the product of the distributions of the random variables (ω′ , i) when ω′ varies in Ω and i varies in I:

Definition 9 Let p ∈ [0, 1 2 ), the (world) swap probability is:

Stated otherwise, one considers here that every Boolean random variable (ω, i) is associated with a Bernoulli distribution, so that the joint distribution P wsn µ,ω for the 2m ×n random variables is a binomial distribution with parameters n and p.

We can easily check that the world swap noise model P wsn satisfies the independence and uniformity conditions. It turns out that this noise is linked to a pseudo-distance between formulae. The distance of two formulae is defined here as the number of interpretations one have to add or to retrieve to one of the two formulae to make it equivalent to the other formula. We call it the swap distance dswap between formulae.

Example 1 Consider the formulae φ = a ∧ b, φ′ = a ∨ b, φ′′ = ¬a where P = {a, b}. We have: dswap(φ, φ′ ) = 2, dswap(φ, φ′′ ) = 3, and dswap(φ′ , φ′′ ) = 3. According to dswap, a ∧ b is thus closer to a ∨ b than to ¬a.

Proposition 5 dswap is a pseudo-distance between formulae.

3⊕ is the exclusive disjunction connective.

When the world swap noise model P wsn is considered, for any model ω of the integrity constraint µ and any base K of E, the largest dswap(K, ω), the less P wsn µ,ω (K). As a consequence:

Proposition 6 Let ω be any model of the integrity constraint µ, φ be any formula having ω as its single model, and let Ki, Kj be two belief bases of E. If dswap(Ki, φ) ≥ dswap(Kj, φ), then P wsn µ,ω (Ki) ≤ P wsn µ,ω (Kj).

On this ground, we can show that the drastic merging operator ∆dD,Σ is a MLE for this noise:

Proposition 7 ∆dD,Σ is a MLE for P wsn .

6 The Atom Swap Noise

Another interesting noise is the atom swap noise P v , obtained by considering that the observed values of variables from P may differ from their values in ω⋆ . In such a case, the probability that an interpretation belongs to a base decreases with the Hamming distance between this interpretation and ω⋆ . Such a noise model is suited for instance to scenarios where the observed values of the variables come from noisy sensors.

P v is parameterized by a probability p < 1, that indicates the probability that the truth value of any observed variable v ∈ P differs from the actual one (i.e., its value in ω⋆ ). Formally the atom noise model P v is a mapping associating with every consistent formula µ ∈ L, every interpretation ω ∈ [µ], a joint probability distribution, noted P v µ,ω , of the 2m × n Boolean random variables (ω′ , i) defined as the product of the distributions of the random variables (ω′ , i) when ω′ varies in Ω and i varies in I:

Definition 11 Let p ∈ (0, 1). The (atom) swap probability is

So, with this noise model, the true state of the world ω⋆ appears in any belief base with a probability p, and any other world has a smaller probability, which exact value depends on its distance to ω⋆ .

Clearly enough, P v satisfies the independence condition (by definition) and the uniformity condition (since P v µ,ω ((ω′ , i)) does not depend on i).

Let us illustrate the behavior of this noise model on an example, with three variables (m = 3) and a profile for n = 5 agents.

Example 2 Suppose that the true state of the world ω⋆ is ω⋆ = 001, with a swap noise P v such that p = 30%. For 5 agents, a possible outcome given that noise is the profile E = 〈K1,K2,K3,K4,K5〉 with [K1] = {011}, [K2] = {110, 001, 111, 101}, [K3] = {000, 001, 111}, [K4] = {000, 110, 001}, [K5] = {001, 111}. In this case, the resulting merged base with ∆dH,Σ from this profile is [∆dH,Σ(E)] = {001}.

Proposition 8 ∆dH,Σ is a MLE for P v .

Proof: Let w be any interpretation. Let dH,Σ(w,E) denote dH(w,K1) + . . . + dH(w,Kn), where dH(w,Ki) =

minω∈Ki dH(w, ω). Let ωw i be a model of Ki such that dH (w, ωw i ) = dH (w,Ki).

Now, by definition of the atom swap noise, the probability that ωw i is a model of Ki given the interpretation w is P v µ,w ((ωw i , i)) = pdH(w,ωw i )+1 . In addition P ((ωw 1 , 1) ∩ . . . ∩ (ωw n , n)) = pdH(w,ωw 1 )+1 × . . . × pdH(w,ωwn )+1 since the atom swap noise satisfies independence. Furthermore pdH(w,ωw 1 )+1 × . . . × pdH(w,ωwn )+1 = pn × pdH(w,ωw 1 )+...+dH(w,ωwn ) = pn × pdH,Σ(w,E) .

We want to prove that ∆dH,Σ is a MLE for P v , which means that [∆dH,Σ µ (E)] = argmaxωPµ,ω(E). This is a direct consequence of the following equivalences:

7 Experimental Results

In this section we study how the merging operators identified as maximum likelihood estimators for the world swap noise and for the atom swap noise are efficient noise cancellers in practice. This requires to evaluate the number of agents needed for getting a merged base equals to the true state of the world with high probability. To this end, we perform some experiments. We report hereafter the obtained results for the world swap noise and the atom swap noise.

In our experiments, the true state of the world ω⋆ has been generated by considering every variable v from P in an iterative way, assigning v to 1 with probability 1 2 . We did not assume any integrity constraint to be fulfilled (i.e., µ is supposed to be a valid formula). Then, for several values of the parameter p, the noise model P wsn (resp. P v ) has been applied to ω⋆ in order to generate 1000 profiles E consisting of n bases for increasing values of n.

Each resulting profile has then been merged using ∆dD,Σ for the world swap noise and using ∆dH,Σ for the atom swap noise. A success has been obtained whenever [∆dD,Σ(E)] = {ω⋆ } for the world swap noise and [∆dH,Σ(E)] = {ω⋆ } for the atom swap noise. For each value of n, the success rate was defined as the percentage of profiles for which a success has been obtained.

Figure 1 shows some of the results obtained for the world swap noise and the atom swap noise, for several values of p when m = 10. Though considering 10 propositional variables may look not that high, one must keep in mind that 2m possible worlds exist since no integrity constraint is considered, so that the task is to identify a single world in a set of 1024 worlds. To interpret the results correctly, one must remind that the noise increases with p when the world swap noise is considered, while it decreases with p when the atom swap noise is considered.

Our experimental results confirm the ability of the merging operators ∆dD,Σ and ∆dH,Σ to "cancel" their respective noises. It is interesting to note that when the noise level is low (p = 30% for the world swap noise and p = 60% for the atom swap noise), as few as 30 bases are enough for being nearly sure (> 90%) to identify the true world. One can observe that for the world swap noise, the number of agents to be considered for getting with high probability a merged base having the true state of the world as its sole model remains quite small, even when the noise level is high. The empirical results also show that the noise cancellation task requires less effort (i.e., less agents) when dealing with the atom swap noise than when dealing with the world swap noise.

Finally, let us note that similar results have been obtained for the other values of m considered in our experiments (we let m vary from 2 to 15; the shapes of the resulting curves are close to those of the curves given in Figure 1, the number of agents required for getting a success increasing with m).

8 RelatedWork

This work is related to the rationalization of voting rules as maximum likelihood estimators, as discussed in [Conitzer and Sandholm, 2005; Young, 1995; Xia et al., 2010; Conitzer, 2014; Pivato, 2012]. Such an interpretation of voting rules requires to suppose that some candidates are better than others, in an absolute/objective sense, and that the agent's preferences are noisy estimates of the "absolute" agents' ranking. The objective of voting is then to determine this best ranking from the agents' votes.

This work has also connections with the truth tracking problem [Bovens and Rabinowicz, 2006; Pigozzi and Hartmann, 2007], that has been studied for belief merging in [Everaere et al., 2010a]. This problem consists in determining, when the agents are reliable enough, whether the true state of the world ω⋆ can be identified in the limit (i.e., when the number of agents participating in the merging process tends to infinity) as the unique model of the corresponding merged base. In [Everaere et al., 2010a], an extension of Condorcet's jury theorem to belief merging has been pointed out, giving a positive answer to the issue under some standard assumptions about the independence and the reliability of the agents.

The maximum likelihood estimator question differs from the truth tracking one in several aspects. In the truth tracking case, ω⋆ is known and every agent is more or less reliable. In the maximum likelihood case, ω⋆ is not known, agents have a noisy perception of it, and the corresponding noise model is more or less known. Furthermore, the observed profile is fixed (so the number of agents does not tend to infinity). So, while the truth tracking problem and the MLE one are related to the issue of providing an epistemic justification for belief merging operators, they offer complementary views.

9 Conclusion

In this work we carried out an evaluation of belief merging operators as maximum likelihood estimators. We have shown close connections between noise models and postulates for IC merging. Especially, we have proved that a merging operator that is a MLE for an independent and uniform noise model has to satisfy most IC merging postulates.We have also shown that all distance-base merging operators based on the Σk aggregation functions are MLEs for some noise. We have studied two specific, yet sensible noise models: the world swap noise and the atom swap noise. We have shown that some well-studied distance-based merging operators are MLEs for those noise models. Finally, we have reported results from experiments showing that finding the true state of the world is feasible in practice for each of the two specific noises. Based on those results, our work provides a new justification for IC merging operators, of epistemic nature.

This work calls for several perspectives for further research. One of them consists in identifying some additional pairs (P, ∆) where ∆ is a MLE for the noise model P . In application scenarios where merging beliefs is required, whenever the noise model can be guessed, a catalog of such pairs would be a useful methodological tool for deciding which belief merging operator to choose.

Acknowledgements

This work has benefited from the support of the AI Chair BE4musIA of the French National Research Agency (ANR).