Impossibility in Belief Merging (Extended Abstract)

1 Introduction

The aim of belief merging [Konieczny and Pino Pérez, 2002; 2011] is to give rational processes for producing a coherent and pertinent piece of information when many sources, which may be mutually in conflict, are present. This kind of process appears naturally in many important domains, for instance decision making, medical diagnosis, policy planning, automatic integration of data, etc. Thus, it is important to understand well the model, its behavior and limitations in order to develop future applications and know in which domains this can be valid.

In the belief merging framework of Konieczny and Pino Pérez the agents' basic piece of information is encoded in propositional logic and the group information is a bag. However, more complex representations are necessary in many situations. This has been revealed by Darwiche and Pearl [1997] in the case of revision operators with a good behavior with respect to iteration and by Mata Díaz and Pino Pérez [2017] through some pertinent examples. Thus, in this work we adopt this view: the basic pieces of information are some states, called epistemic states, which have attached a logical information, actually a propositional formula. Moreover the group information is vectorial (or functional, see Section 2).

� This paper is an extended abstract of an article in Artificial Intelligence [Mata Díaz and Pino Pérez, 2017].

Some similarities have been pointed out between belief merging and social choice theory [Arrow, 1963; Suzumura, 2002]. These similarities have been established in early works in belief merging [Konieczny and Pino Pérez, 1999; 2002; 2005]. As a matter of fact, the representation theorem for belief merging operators evoques the methods for defining social choice functions.

Actually, some aspects of social choice are explored in belief merging [Chopra et al., 2006; Everaere et al., 2007], mainly impossibility [Arrow, 1963; Campbell and Kelly, 2002] and strategy-proofness [Gibbard, 1973; Satterthwaite, 1975]. The operators considered by Chopra et al. [Chopra et al., 2006] satisfy a postulate which is, in fact, incompatible with the existence of a dictator; for this reason they have not an impossibility result. Moreover, they impose certain conditions to their operators which force strategy-proofness. In [Everaere et al., 2007] some results on manipulation are given with respect to manipulation over certain indexes. We continue the study of impossibility, in our present work, in the extended framework of belief merging.

We have to note three important features of the framework considered here. First, that the view of epistemic states considered here is more general than the propositional view. This abstract view of epistemic states, introduced by Benferhat et al. [2000], is indeed a formalization of the concept appeared in [Darwiche and Pearl, 1997] (see also Mata Díaz and Pino Pérez [2011]). Second, the representation of profiles will be also more general; we adopt the functional view. Third, we enrich the set of rational postulates by introducing social postulates inspired on the classical Arrow's postulates in social choice theory [Arrow, 1963]. All these postulates are formulated in a logical setting. In this framework we prove a general impossibility result.

This work is organized as follows: Section 2 is devoted to defining the concepts used throughout the paper. Section 3 is devoted to giving the syntactical postulates and their semantical counterparts and then to establish the basic representation theorems. In Section 4, we introduce the new postulates coming from social choice and state a general impossibility theorem, the main result of the paper. Finally, we make some concluding remarks in Section 5.

2 Preliminaries

A preorder over a set A is a binary relation � over A which is reflexive and transitive. We define the strict relation, � and the indi�erence relation, ', associated to a preorder � over A as follows: a � b i� a � b & b � a; and a ' b i� a � b & b � a

Given a preorder � over A and a subset C of A, we say that c in C is a maximal element of C, with respect to �, if there is no x 2 C such that x � c. The set of maximal elements of C with respect to � will be denoted by max(C; �). We will write max(�) instead of max(A; �) to denote the set of maximal elements of the whole set A with respect to �. We will denote by ��C the restriction of � to C, and P(A) will denote the set of preorders over a set A.

A total preorder is a binary relation over a set A which is total (therefore reflexive) and transitive. Thus, any total preorder over a set A is also a preorder over A.

The set of propositional formulas built over a finite set P of atomic propositions will be denoted LP. LP � will denote the set of non contradictory formulas in LP, while WP will be the set of all the interpretations. Note that WP is a finite set. If ' is a formula in LP, we denote by [[']] the set of its models, i.e. [[']] = fw 2 WP : w j= 'g. If 'i is a formula in LP, for each i in a finite set of indexes I, then we denote by VV i2I 'i the conjunction of all the formulas 'i. If I is a nonempty set of interpretations, we denote by 'I a formula such that [['I]] = I.

An epistemic space is a triple (E; B;LP) such that E is a nonempty set, LP is the set of propositional formulas over P and B is a function from E into LP, such that the image of B, modulo logical equivalence, is all the set L � P . The elements of E are called epistemic states, B is called the belief function, while B(E) is called the belief base (or the most entrenched beliefs) of E, for each E in E. Note that if I is a finite nonempty set of interpretations, then there exists an epistemic state E such that B(E) � 'I .

In order to introduce the notion of epistemic state profiles, from now on we consider a given epistemic space (E; B; LP) and a well ordered set (S; <) the elements 1 of which are called agents. A finite society of agents is a finite and nonempty set N of S. From now on, we suppose N = fi1; i2; : : : ; ing and also assume that its elements are disposed in increasing way, i.e. ik < im whenever k < m. A partition of N is a finite family fN1; N2; : : : ; Nkg of pairwise disjoint sets such that their union is N.

Given a finite society of agents N, an N-profile of epistemic states (also called N-profile or epistemic profile by abuse) is a function � : N �! E. We think of �(i) as the epistemic state of the agent i, for each agent i in N. If � is an Nprofile, for each agent i in N, Ei will denote �(i). Thus, if N = fi1; i2; : : : ; ing is a finite society of agents, it can be seen as an ordered tuple: � = (Ei1 ; Ei2 ; : : : ; Ein ). Thus, an Nprofile � collects in ordered way the information expressed by those agents in N. From now on, if N is singleton, suppose N = fig, by abuse, Ei will denote the N-profile � = (Ei). In that case we write i-profile instead of fig-profile. The set of all the epistemic profiles will be denoted P(S; E).

1 The set (S; <) can be identified with the set of natural numbers Nwith the usual order.

Let N = fi1; i2; : : : ; ing and M = f j1; j2; : : : ; jmg be two finite societies of agents, and consider the epistemic profiles � = (Ei1 ; Ei2 ; : : : ; Ein ) and � 0 = (E 0 j1 ; E 0 j2 ; : : : ; E 0 jm ). We say that � and � 0 are equivalent, denoted � � � 0 , if n = m and Eik = Ejk for k = 1; : : : ; n. Thus, for any pair of agents i, j in S, if we consider an i-profile Ei and a j-profile Ej, then Ei � Ej i� , seen as epistemic states, we have Ei = Ej. Thus, by abuse and being clear from the context, we write Ei = E j and Ei , Ej instead of Ei � Ej and Ei . Ej respectively.

When N and M are disjoint, � is an N-profile and � 0 is an M-profile, we define a new (N[M)-profile, the joint of � and � 0 , denoted �t� 0 , in the following way: (�t� 0 � (i) is �(i) if i 2 N, otherwise it is � 0 (i). Moreover, if M � N, then ��M will denote the M-profile obtained by the restriction of � to M. Thus, if fN1; N2; : : : ; Nkg is a partition of a finite society of agents N, then we have � = ��N1 t � � � t ��Nk , for each N-profile �.

From now on, we will suppose that N is the finite society fi1; i2; : : : ; ing, while the N-profiles � and � 0 will be denoted by (Ei1 ; Ei2 ; : : : ; Ein ) and (E 0 i1 ; E 0 i2 ; : : : ; E 0 in ) respectively.

3 Epistemic States Merging Operators

From now on, we fix an epistemic space (E; B; LP) and a set of agents S. A function of the form r : P(S; E) � E �! E will be called an epistemic state combination operator, for short an ES combination operator. r(� ; E) represents the result of combining the epistemic states in � under an integrity constraint E.

Now we establish the rationality postulates of merging in the framework of epistemic states. Most of them are adapted from IC merging postulates proposed by Konieczny and Pino Pérez [1999; 2002; 2005; 2011]. The postulates in terms of epistemic states, were first proposed and widely studied by Mata Díaz and Pino Pérez [2011; 2017]. In order to introduce such postulates, we consider N and M a couple of finite societies of agents in S, an N-profile �, an M-profile � 0 , and a triple of epistemic states E, E 0 , E 00 in E; let j, k be a pair of agents in S, N1, N2 be any partition of N, E j be any j-profile, Ek be any k-profile.

(ESF2) If � � � 0 and B(E) � B(E 0 ) then B � r(� ; E) � � B � r(� 0 ; E 0 ) � .

(ESF3) If B(E) � B(E 0 )^B(E 00 ), then B � r(� ; E 0 ) � ^B(E 00 ) ' B � r(� ; E) � .

• (ESF5) If Ej , Ek, then there exits E 0 in E such that B � r(E j ; E 0 ) � . B � r(Ek; E 0 ) �

The first four postulates, (ESF1)-(ESF4), called basic merging postulates, are considered the minimal requirements of rationality that the combination operators have to satisfy. These postulates allow us to introduce an important class of ES combination operators, namely the ES basic merging operators. They are generalizations of ICO, IC3, IC7 and IC8 respectively. (ESF6), (ESF7) and (ESF8) are generalizations of IC2, IC5 and IC6 respectively. (ESF5) says that the operators have a sort of injectivity for profiles of size one. The last four postulates describe mainly the relationships between the results of merging as a whole society and the results of merging in its subsocieties.

Definition 1 An ES combination operator r is said to be an epistemic state basic merging operator (ES basic merging operator for short) if it satisfies (ESF1)-(ESF4).

An ES basic merging operator r is said to be a merging operator of epistemic states (ES merging operator for short) if it satisfies the postulates (ESF5)-(ESF8).

Now we present some semantics aspects. An assignment is a function � 7 !�� which maps epistemic states profiles into total preorders over interpretations. The intended meaning of this mappings is coding semantically, in some sense, the group preference.

Definition 2 A basic assignment is an application � 7 !�� which maps each epistemic profile � into a total preorder �� over WP, and it is such that ��=�� 0 , for any pair �, � 0 of equivalent epistemic profiles.

A basic assignment � 7 !�� is called a faithful assignment if it satisfies the following properties for any pair j, k of agents in S, any finite society of agents N, any partition of N, fN1; N2g, any N-profile �, any j-profile Ej, any k-profile Ek, and any pair of interpretations w, w 0 inWP:

• 1 If Ej , Ek, then �Ej ,�Ek
• 2 If VV i2N B(Ei) 0 ?, then [[ VV i2N B(Ei)]] = max(��)
• 3 If w ���N1 w 0 and w ���N2 w 0 then w �� w 0
• 4 If w ���N1 w 0 and w ���N2 w 0 , then w �� w 0

For any epistemic profile �, the total preorder �� can be seen as a global plausibility measure over worlds:

• � If w �� w 0 , we will say that w is at least as plausible as w 0 , for the agents group in �
• � If w �� w 0 , we will say that w is more plausible than w 0 , for the agents group in �

From Property 2 follows that the most entrenched preferences represent the entrenchment beliefs of any agent. More precisely, for any agent i in S and for each i-profile Ei, we have straightforwardly from Property 2 that the following equality holds, which is called maximality condition: [[B(Ei)]] = max(�Ei ).

Thus, any assignment which satisfies Property 2, satisfies the maximality condition, but the converse is not true (cf. Mata Díaz and Pino Pérez [2011; 2017]). However, in presence of Properties 3 and 4, we have that Property 2 is equivalent to maximality condition, as was showed by Mata Díaz and Pino Pérez [2017].

Now we present some results that help to understand the behavior of the ES merging operators. They allow us to describe such operators at the level of the entrenched beliefs. The proof of these results can be found in [Mata Díaz and Pino Pérez, 2017].

Theorem 1 (i) An ES combination operator r is an ES basic merging operator i� there exists a unique basic assignment � 7 !�� such that:

(ii) An ES combination operator r is said to be an ES merging operator i� there exists a unique faithful assignment � 7 !�� satisfying B-Rep.

4 Social Behavior of ESMerging Operators

We present some properties of the merging process which capture the following social principles appearing in the seminal work of Arrow [1963]: Domain Standard, Pareto Condition, Independence of Irrelevant Alternatives and Existence of a Dictator.

In order to give a formulation of these principles in logic terms using epistemic states, we will suppose from now on that P has at least two propositional variables. Thus, there will be available at least four interpretations inWP.

The first property, called Standard Domain, states some "richness" in the set of results of the merging process.

(ESF-SD) For any agent i in S, for every triple w, w 0 and w 00 in WP, and each pair of epistemic states Ew;w 0 and Ew 0 ;w 00 , such that [[B(Ew;w 0 )]] = fw; w 0 g and [[B(Ew 0 ;w 00 )]] = fw 0 ; w 00 g, the following conditions hold:

• (i) There exists an i-profile Ei such that B � r(Ei; Ew;w 0 ) � � 'w;w 0 and B � r(Ei; Ew 0 ;w 00 ) � � 'w 0
• (ii) There exists an i-profile Ei such that B � r(Ei; Ew;w 0 ) � � 'w and B � r(Ei; Ew 0 ;w 00 ) � � 'w 0 ;w 00
• (iii) There exists an i-profile Ei such that B � r(Ei; Ew;w 0 ) � � 'w and B � r(Ei; Ew 0 ;w 00 ) � � 'w 0

It is important to note the following:

Observation 1 For basic merging operators, the satisfaction of this postulate is equivalent to the fact that: for any agent i in S, any triple of interpretations w, w 0 and w 00 in WP, and any total preorder � over interpretations (except the flat order), there is an i-profile Ei such that �=�Ei �fw;w 0 ;w 00 g .

The previous observation and some natural combinatorial arguments tell us that if the epistemic space is reduced to the consistent formulas modulo logical equivalence and the function B is the identity then the basic fusion operators satisfying the maximality condition cannot satisfy (ESF-SD). That is precisely the next result.

Theorem 2 Consider the epistemic space (E; B;LP) where E = LP � =�, with LP a set of formulas built over two propositional variables and B(') = ' for every element 2 ' in E. Let r : P(S; E) � E �! E be an ES basic fusion operator satisfying the maximality condition. Then r does not satisfy (ESF-SD).

This theorem highlights the necessity of having complex representations of epistemic states in order to have postulates like standard domain. We have to say that the standard domain postulate is largely used in the proof of our impossibility theorem (Theorem 3).

Now we give a syntactical formulation of the Pareto condition: if all the agents reject a given information, and all the agents have some consensus, then this information will be rejected in the result of merging.

(ESF-P) For all finite society N in F � (S), any N-profile � and any couple of epistemic states E, E 0 in E, if VV i2N B � r(Ei; E) � 0 ? and, for all i in N, B � r(Ei; E) � ^ B(E 0 ) ' ?, then B � r(� ; E) � ^ B(E 0 ) ' ?.

Any ES merging operator satisfies the Pareto Condition. This is because the satisfaction of (ESF7) and (ESF8) entails that (ESF-P) holds. However, there exist some ES combination operators showing that the converse of this result is not true (cf. Mata Díaz and Pino Pérez [2017]).

We continue stating the syntactical postulate aiming to capture the principle of independence of irrelevant alternatives: the merging process depends only on how the restrictions in the individual epistemic states are related. Our postulate, called independence condition, tries to capture this.

(ESF-I) For any finite society N in F � (S), for any couple of N-profiles � and � 0 , for every epistemic state E in E we have B � r(� ; E) � � B � r(� 0 ; E) � , if for every epistemic state E 0 in E such that B(E 0 ) ' B(E) we have B � r(E j; E 0 ) � � B � r(E 0 j ; E 0 ) � , for all j in N.

Next, we state the postulate related with the fourth principle Absence of Dictator: the group belief base, obtained as the result of the merging process, does not depend on one unique agent. Actually, we establish the negative form: there is an agent that imposes his will, a dictatorial agent. This is the postulate that the good operators should avoid.

(ESF-D) For any finite society N in F � (S) there exists an agent dN in N such that, for all N-profile � and for all epistemic state E in E, B � r(� ; E) � ' B � r(EdN ; E) � .

Operators satisfying the previous postulate are called dictatorial operators. Thus, if r is a dictatorial operator, given a finite society N, an agent dN testifying that (ESF-D) holds, is called a dictator in N or simply N-dictator for r.

2 By abuse we write ' for the equivalence class of the propositional formula '.

It is worth to note that the social postulates here presented have a semantical characterization (cf. Mata Díaz and Pino Pérez [2017]). Actually, the Observation 1 can be seen as the semantical characterization of the standard domain condition.

Nowwe present a general result of Impossibility, similar to Arrow's Theorem [Arrow, 1963; Kelly, 1978; Taylor, 2005]. The proof of this result can be found in [Mata Díaz and Pino Pérez, 2017].

Theorem 3 (Main impossibility theorem) If r is an ES basic (complete) merging operator that satifies the properties (ESF-SD), (ESF-P) and (ESF-I), then r also satisfies (ESFD).

Because of the relationships between the merging postulates and the Pareto condition pointed out before, we have:

Corollary 1 Any ES basic merging operator that satisfies (ESF-SD), (ESF7), (ESF8) and (ESF-I), is a dictatorial operator.

5 Concluding Remarks

We have presented an epistemic version of postulates of merging which allow us to give a very precise representation results (Theorem 1). We have also introduced new postulates with a more social flavor. We have shown some tight relationships between the merging postulates and the social postulates; in particular, the ES fusion operators satisfy the Pareto condition.

The social postulates together with the basic fusion postulates are enough to prove a general impossibility theorem: the ES basic fusion operators satisfying the standard domain, Pareto and independence conditions are indeed dictatorial operators (Theorem 3). Moreover, the ES fusion operators satisfying the standard domain postulate and the independence condition are dictatorial operators (Corollary 1).

One very interesting feature of our approach is that it gives interesting instantiations of the impossibility theorem (Theorem 3) for di�erent representations of epistemic states. Thus, this applies to ordinal conditional functions, rational relations, and of course total preorders. However, the representation of epistemic states as formulas does not work because it is impossible to have standard domain in presence of a good representation of beliefs, namely the maximality condition. This fact highlights the necessity of using complex epistemic states.

An interesting problem, open for future work, is to find a characterization of dictatorial operators.

Acknowledgements

Thanks to the CDCHTA-ULA for its financial support to the Project C-1855-13-05-A.