Patricia Everaere
email: patricia.everaere@univ-lille1.fr

Sébastien Konieczny
email: konieczny@cril.fr

Pierre Marquis
email: marquis@cril.fr

On Egalitarian Belief Merging

Belief merging aims at defining the beliefs of a group from the beliefs of each member of the group. It is related to more general notions of aggregation from economy (social choice theory). Two main subclasses of belief merging operators exist: majority operators which are related to utilitarianism, and arbitration operators which are related to egalitarianism. Though utilitarian (majority) operators have been extensively studied so far, there is much less work on egalitarian operators. In order to fill the gap, we investigate possible translations in a belief merging framework of some egalitarian properties and concepts coming from social choice theory, such as Sen-Hammond equity, Pigou-Dalton property, median, and Lorenz curves. We study how these properties interact with the standard rationality conditions considered in belief merging. Among other results, we show that the distance-based merging operators satisfying Sen-Hammond equity are mainly those for which leximax is used as the aggregation function.

Introduction

The aim of belief merging is to define a coherent belief base from a set of jointly incoherent belief bases, representing the beliefs of a group of agents. The rationality properties of belief merging operators have been studied in [Revesz, 1997;[START_REF] Lin | Knowledge base merging by majority[END_REF]Konieczny and Pino Pérez, 2002a;Konieczny, Lang, and Marquis, 2004;Everaere, Konieczny, and Marquis, 2010b]. Especially, in [Konieczny and Pino Pérez, 2002a], a number of postulates characterizing the so called IC merging operators have been identified. At the same time, many definitions of propositional belief merging operators have been pointed out. Most of these operators are distance-based ones, which means that they can be defined using a distance between interpretations and an aggregation function [Revesz, 1997;[START_REF] Lin | Knowledge base merging by majority[END_REF]Konieczny, Lang, and Marquis, 2004;Everaere, Konieczny, and Marquis, 2010a].

Two main subclasses of IC belief merging operators have been defined in [Konieczny and Pino Pérez, 2002a]: majority operators, which solve conflicts using majority, and arbitration operators, which try to find a consensual result. However, while many distance-based majority merging operators have been defined in the literature, very few arbitration operators have been identified so far. To be more precise, the only arbitration IC merging operators we are aware of are distancebased operators using leximax as aggregation function.

Majority merging operators are closely related to the utilitarian social welfare approaches, where the aim is to determine solutions with the best aggregated utility [Harsanyi, 1955;Moulin, 1988;Sen, 2005]. On the other hand, arbitration operators are related to the egalitarian social welfare approaches, where the objective is to find solutions which are as fair as possible; this usually means that they give as much as possible to the poorest agents. To this extent, poverty measures [Rawls, 1971;Gini, 1921;Sen, 1973;Dutta, 2002] are relevant to the design of egalitarian approaches.

The aim of this paper is to introduce and study new egalitarian operators, by exhibiting other fairness conditions than arbitration and by pointing out belief merging operators satisfying them. Our methodology to reach our goal consists in investigating equity conditions considered in social choice theory [START_REF] Arrow | Handbook of Social Choice and Welfare[END_REF] in order to determine if they can be reasonably imported in the belief merging setting. Thus, in the following, we translate to the belief merging framework two egalitarian conditions coming from social choice theory: Sen-Hammond equity, and Pigou-Dalton property. We show that the distance-based merging operators satisfying Sen-Hammond equity are mainly those for which leximax is used as the aggregation function. We also introduce two new families of belief merging operators, based respectively on the median and on an aggregated sum (Lorenz curves). We identify the rationality properties satisfied by these operators and study in particular their egalitarian behaviour.

The rest of the paper is organized as follows. First we give some preliminaries on propositional belief merging, focusing on IC merging operators and distance-based operators. Then we show how Sen-Hammond equity condition, and Pigou-Dalton property can be expressed in the belief merging set-ting. Since we want to define other egalitarian distance-based merging operators than those based on leximax , some IC postulates must be relaxed; we define a general family of belief merging operators, called pre-IC merging operators; they are obtained by relaxing two IC postulates. On this ground, we define the family of median distance-based merging operators. We show that the operators of this family based on the leximed k aggregation functions are pre-IC operators, and those for which k ≥ 0.5 satisfy also the arbitration postulate (Arb), but not the Pigou/Dalton property. Finally we introduce the family of cumulative sum distance-based merging operators; we identify in this family some pre-IC operators, and among them an operator satisfying the Pigou-Dalton property. Some proofs are omitted for space reasons.

On Propositional Belief Merging

We consider a propositional language L defined from a finite set of propositional variables P 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 usually denoted by a bit vector whenever a strict total order on P is specified. An interpretation ω is a model of a formula φ ∈ L if and only if it makes it true in the usual truth functional way. |= and ≡ denote logical entailment and equivalence, respectively. [φ] denotes the set of models of a formula φ, i.e., [φ]

= {ω ∈ Ω | ω |= φ}.
A base K denotes the set of beliefs of an agent, it is a finite set of propositional formulae, interpreted conjunctively (i.e., viewed as the conjunction of its elements).

A profile E denotes a group of n agents that are involved in the merging process; formally E is given by a muti-set {K 1 , . . . , K n } of bases. E denotes the conjunction of all elements of E, and denotes the multi-set union. Two multisets E = {K 1 , . . . , K n } and E = {K 1 , . . . , K n } are equivalent, noted E ≡ E , iff there exists a permutation π over {1, . . . , n} s.t. for each i ∈ 1, . . . , n, we have

K i ≡ K π(i) .
An integrity constraint µ is a formula restricting the possible results of the merging process.

A merging operator is a function which associates with a profile E and an integrity constraint µ a merged base µ (E).

The logical properties given in [Konieczny and Pino Pérez, 2002a] for characterizing IC belief merging operators are: 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 E 1 ≡ E 2 and µ 1 ≡ µ 2 , then µ1 (E 1 ) ≡ µ2 (E 2 ) (IC4) If K 1 |= µ and K 2 |= µ, then µ ({K 1 , K 2 }) ∧ K 1 is consistent if and only if µ ({K 1 , K 2 }) ∧ K 2 is consis- tent (IC5) µ (E 1 ) ∧ µ (E 2 ) |= µ (E 1 E 2 ) (IC6) If µ (E 1 ) ∧ µ (E 2 ) is consistent, then µ (E 1 E 2 ) |= µ (E 1 ) ∧ µ (E 2 ) (IC7) µ1 (E) ∧ µ 2 |= µ1∧µ2 (E) (IC8) If µ1 (E) ∧ µ 2 is consistent, then µ1∧µ2 (E) |= µ1 (E)
See [Konieczny and Pino Pérez, 2002a] for explanations on these properties. Two subclasses of IC merging operators are also defined in [Konieczny and Pino Pérez, 2002a]:

Definition 2 An IC majority operator is an IC merging operator which satisfies the following majority property:

(Maj) ∃n µ (E 1 E 2 . . . E 2 n ) |= µ (E 2 )
An IC arbitration operator is an IC merging operator which satisfies the following arbitration property:

1 (Arb) If µ1 (K 1 ) ≡ µ2 (K 2 ) µ1↔¬µ2 ({K 1 , K 2 }) ≡ (µ 1 ↔ ¬µ 2 ) µ 1 |= µ 2 µ 2 |= µ 1 then µ1∨µ2 ({K 1 , K 2 }) ≡ µ1 (K 1 )
Majority operators solve conflicts using majority. (Maj) says that if one duplicates sufficiently many times a profile E 2 , then the result of the merging of E 1 with the E 2 duplications will obey the choices of the profile E 2 . Arbitration operators try to find a consensual result. See the corresponding condition 8 in Definition 3 and Example 1 which illustrates how this property gives a preference to consensual ("median") choices of interpretations.

The representation theorems enable to interpret these logical properties as constraints on the choice of interpretations for defining the models of the resulting belief base: Definition 3 A syncretic assignment is a function mapping each profile E to a total pre-order ≤ E2 over Ω such that for any profiles E, E 1 , E 2 and for any belief bases K, K the following conditions hold:

1

. If ω |= E and ω |= E, then ω E ω 2. If ω |= E and ω |= E, then ω < E ω 3. If E 1 ≡ E 2 , then ≤ E1 =≤ E2 4. ∀ω |= K ∃ω |= K ω ≤ {K,K } ω 5. If ω ≤ E1 ω and ω ≤ E2 ω , then ω ≤ E1 E2 ω 6.
If ω < E1 ω and ω ≤ E2 ω , then ω < E1 E2 ω A majority syncretic assignment is a syncretic assignment which satisfies the following condition:

7. If ω < E2 ω , then ∃n ω < E1 E n 2 ω A fair syncretic assignment is a syncretic assignment which satisfies the following condition:

8. If ω < K1 ω , ω < K2 ω , and ω {K1,K2} ω , then ω < {K1,K2} ω Proposition 1 ( [Konieczny and Pino Pérez, 2002a]) A merging operator is an IC merging operator (resp. an IC majority, an IC arbitration operator) iff there exists a syncretic assignment (resp. a majority syncretic assignment, a fair syncretic assignment) that maps each profile E to a total pre-order

≤ E over Ω such that [ µ (E)] = min([µ], ≤ E ).
Let us now give some examples of IC merging operators using the familly of distance-based merging operators [Konieczny, Lang, and Marquis, 2004]: Definition 4 A distance3 between interpretations is a function d : Ω × Ω → IR + such that for any ω 1 , ω 2 ∈ Ω:

• d(ω 1 , ω 2 ) = d(ω 2 , ω 1 ) • d(ω 1 , ω 2 ) = 0 iff ω 1 = ω 2
Usual distances considered in merging are the Hamming distance d H : d H (ω 1 , ω 2 ) is the number of propositional letters on which the two interpretations differ (this corresponds to the 1-norm distance, also referred to as the Manhattan distance) and the drastic distance d D , defined as d D (ω 1 , ω 2 ) = 0 if ω 1 = ω 2 , and = 1 otherwise (this corresponds to the infinity-norm distance, also known as Chebyshev distance).

Definition 5 An aggregation function is a mapping4 f from R m to R, which satisfies:

• if x i ≥ x i , then (non-decreasingness) f (x 1 , ..., x i , ..., x m ) ≥ f (x 1 , ..., x i , ..., x m ) • f (x 1 , . . . , x m ) = 0 if ∀i, x i = 0 (minimality) • f (x) = x (identity) • If σ is a permutation over {1, . . . , m}, then f (x 1 , . . . , x m ) = f (x σ(1) , . . . , x σ(m) ) (symmetry)
Some additional properties can be considered for f , especially:

• if x i > x i , then (strict non-decreasingness) f (x 1 , ..., x i , ..., x m ) > f (x 1 , ..., x i , ..., x m )
Definition 6 Let d and f be respectively a distance between interpretations and an aggregation function. The distancebased 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 = {K 1 , . . . , K n }):

• ω ≤ E ω iff d(ω, E) ≤ d(ω , E) • d(ω, E) = f (d(ω, K 1 ), . . . , d(ω, K n )) • d(ω, K) = min ω |=K d(ω, ω )
For usual aggregation functions, whatever the chosen distance, the corresponding distance-based operators exhibit good logical properties:

Proposition 2 ( [Konieczny and Pino Pérez, 2002a]) For any distance d:

• if f is the sum Σ, leximin5 , or Σ n (the sum of the n th powers), then d,f is an IC majority operator.

• if f is leximax , then d,f is an IC arbitration operator.

Conditions for Egalitarian Merging

The only egalitarian property that has been proposed so far for belief merging is the arbitration property, represented by the (Arb) postulate (or the corresponding semantic condition 8 on syncretic assignments). So a key issue we would like to address is to determine whether other egalitarian properties are possible in the belief merging framework, and, if so, how they relate with arbitration.

If one looks closely at condition 8 in Definition 3, it is clear that the arbitration property only imposes some constraints on the merging of profiles consisting of two belief bases. Then the IC properties (IC5) and (IC6) ensure the propagation of the constraints on profiles of any size.

We now propose a first alternative condition, coming from social choice theory, for characterizing egalitarian behaviour in belief merging. This condition, proposed by Hammond in [Hammond, 1976] is known in the literature as the Sen-Hammond equity condition [Sen, 1997;Suzumura, 1983]. This condition in this setting is expressed in the following way:

Definition 7 (Sen97) If person i is worse off than person j both in x and in y, and if i is better off himself in x than in y, while j is better off in y than in x, and if furthermore all others are just as well off in x as in y, then x is socially at least as good as y.

It is translated in the belief merging setting as constraints on the total pre-orders associated with the input profiles. These constraints concern profiles of arbitrary size, and not only those consisting of two bases. Before doing it, we first need to define a notion of the respective "satisfaction" of two bases given an interpretation: Definition 8 Given a merging operator defining an assignment which maps every profile E to a total pre-order ≤ E over Ω, given an interpretation ω, and two bases K 1 and K 2 , we say that K 1 is better than

K 2 given ω, denoted K 1 < ω K 2 , iff ∃ω 1 |= K 1 , ∀ω 2 |= K 2 , ω 1 < ω ω 2 .
We can now give the translation of the Sen-Hammond Equity (SHe) condition:

Definition 9 (Condition (SHe)) Let E = {K 1 , . . . , K n }. ω < K1 ω ω < K2 ω ∀i = 1, 2 ω Ki ω K 1 < ω K 2 K 1 < ω K 2          =⇒ ω ≤ E ω
When distance-based merging operators are considered, this condition is equivalent to:

Definition 10 (Condition (SHE)) d(ω, K 1 ) < d(ω , K 1 ) < d(ω , K 2 ) < d(ω, K 2 ) ∀i = 1, 2 d(ω, K i ) = d(ω , K i ) =⇒ f (d(ω , K 1 ), d(ω , K 2 ), . . . , d(ω , K n )) ≤ f (d(ω, K 1 ), d(ω, K 2 ), . . . , d(ω, K n )) Proposition 3 A distance-based merging operator ∆ d,f sat- isfies (SHE) if and only if it satisfies (SHe). ω 1 ω 2 ω 3 ω 4 ≤ K1 ω 3 ω 2 ω 1 ≤ K2 ω 4 Figure 1: Egalitarian behaviour -(Arb)
Proof:

(SHE) is exactly the translation of (SHe) when the merging operator is defined from a distance and an aggregation function. Indeed, in this case,

K 1 < ω K 2 iff ∃ω 1 |= K 1 , ∀ω 2 |= K 2 , ω 1 < ω ω 2 . Then ∃ω 1 |= K 1 , ∀ω 2 |= K 2 , d(ω, ω 1 ) < d(ω, ω 2 ): ∃ω 1 |= K 1 , d(ω, ω 1 ) < min ω2|=K2 d(ω, ω 2 ) = d(ω, K 2 ). Hence we have d(ω, K 1 ) < d(ω, K 2 ). ω < K1 ω ⇔ d(ω, K 1 ) < d(ω , K 1 ) ω < K2 ω ⇔ d(ω , K 2 ) < d(ω, K 2 ) ∀i = 1, 2 ω Ki ω ⇔ ∀i = 1, 2 d(ω, K i ) = d(ω , K i ) K 1 < ω K 2 ⇔ d(ω, K 1 ) < d(ω, K 2 ) K 1 < ω K 2 ⇔ d(ω , K 1 ) < d(ω , K 2 )
Using transitivity, we get:

d(ω, K 1 ) < d(ω , K 1 ) < d(ω , K 2 ) < d(ω, K 2 ) and ∀i = 1, 2 ω Ki ω ⇔ ∀i = 1, 2 d(ω, K i ) = d(ω , K i ). Hence ω ≤ E ω ⇔ f (d(ω , K 1 ), d(ω , K 2 ), . . . , d(ω , K n )) ≤ f (d(ω, K 1 ), d(ω, K 2 ), . . . , d(ω, K n )).
2

This Sen-Hammond Equity condition expresses the following idea: compare two "situations" ω 1 and ω 2 that are equally good for all the agents except two of them. For these two agents one of them (K 1 ) is in the two situations better than the other agent (K 2 ). Then the fairer situation is the one that gives the more to the less satisfied agent (K 2 ).

This condition looks close to the arbitration condition (compare (SHe) with condition 8 of Definition 3), but the two conditions are logically independent. Let us now illustrate on a simple example how they differ: Example 1 Consider a propositional language over two variables and a distance-based merging operator d,f . Suppose that the distance d on which d,f is built is the shortest path distance on the following graph:

ω 1 1 ω 2 1 ω 3 1 ω 4 .
Figure 1 illustrates the case when the unique model of K 1 is ω 1 and the unique model of K 2 is ω 3 . It is clear here that ω 1 and ω 3 play symmetrical roles, so that they cannot be distinguished when we merge K 1 and K 2 . However, on this example, ω 2 appears as a more consensual choice than ω 1 and ω 3 for this merging. Accordingly, (Arb) imposes that ω 2 is strictly preferred to ω 1 and ω 3 in ≤ {K1,K2} .

Suppose now that we want to merge

E = {K 1 , K 2 } where [K 1 ]={ω 1 , ω 3 } and [K 2 ] ={ω 4 },
and that the choice to be made is between ω 1 and ω 2 (i.e., the integrity constraint µ satisfies [µ] = {ω 1 , ω 2 }). This is illustrated by Figure 2. (Arb) imposes no constraint on this choice. But clearly, whatever the choice between {ω 1 }, {ω 2 }, or {ω 1 , ω 2 }, the result will be closer to K 1 than to K 2 . So a simple equity argument is to

ω 1 ω 3 ω 2 ω 4 ≤ K 1 ω 4 ω 3 ω 2 ω 1 ≤ K 2 Figure 2: Egalitarian behaviour -(SHE)
commit to the choice that is the best for the farest base K 2 , so to consider that ω 2 is strictly preferred to ω 1 in ≤ E . This is what (SHe) gives.

Unfortunately, the family of distance-based IC operators satisfying condition (SHE) looks rather limited:

Proposition 4 Let d be any distance and f be any aggregation function satisfying strict non-decreasingness. The IC merging operator ∆ d,f satisfies condition (SHE) if and only if f = leximax .

Proof: We know that ∆ d,leximax is an IC operator such that leximax satisfies strict-decreasingness. It is easy to check that ∆ d,leximax satisfies (SHE), so we have mainly to prove the converse implication. Consider a distance d and an aggregation function f satisfying strict non-decreasingness, and suppose that ∆ d,f satisfies (SHE).

Let X = (x 1 , . . . , x n ) and X = (x 1 , . . . , x n ) be two vectors of distances to a profile E, ordered in the descending way (∀i,

x i = d(ω, K i ) and x i ≥ x i+1 ; x i = d(ω , K i ) and x i ≥ x i+1
). We have to show that:

X < leximax X ⇔ f (X) < f (X ) (1)
and

X leximax X 6 ⇔ f (X) = f (X ) (2)
We start with statement (1). Suppose that X < leximax X . We know that ∃l s.t. ∀i < l, x i = x i and x l < x l .

Case 1: l = n or ∀i > l, x i = x i : using strict nondecreasingness we get f (X) < f (X ).

Case 2: Suppose that ∃k > l, x k = x k and ∀i = k, l, x i = x i .

• If x k ≤ x k , then using strict-decreasingness (as

x l < x l ), we get f (X) < f (X ). • If x k > x k , then we have x l > x l ≥ x k > x k .
Consider a vector Y = (y 1 , . . . , y n ) s.t. ∀i = k, l, y i = x i and y k , y l such that x l > y l > y k > x l . As we have ∀i = k, l, y i = x i and x l > y l > y k > x k , because ∆ d,f satisfies (SHE), we can conclude that f (Y ) ≤ f (X ). Furthermore ∀i = k, l, y i = x i and y l > y k > x l ≥ x k , using strict decreasingness, we get f (Y ) > f (X). By transitivity, we obtain f (X) < f (X ).

Case 3: Let us consider now the general case. ∀i < l, x i = x i , x l < x l and l < n. We define n -l + 1 vectors Y r = (y r 1 , . . . , y r n ), for r = 0 to n -l:

y r i =      x i if i < l x l + r n-l (x l -x l ) if i = l x i if l + 1 ≤ i ≤ n -r x i if n -r + 1 ≤ i ≤ n
We have Y 0 = X and Y n-l = X , and any two consecutive vectors Y r and Y r+1 differ only on two components, namely y r l and y r+1 l on the one hand, and y r n-r and y r+1 n-r on the other hand. Furthermore,

Y r < leximax Y r+1 , because ∀i < l, y r i = y r+1 i , ∀i ≤ l, y r i ≥ y r i+1 , ∀i ≤ l, y r+1 i ≥ y r+1 i+1 and y r l < y r+1 l . Using Case 2, we can conclude that f (Y r ) < f (Y r+1 ). By transitivity we get f (Y 0 ) = f (X) < f (Y n-l ) = f (X ), and the conclusion follows. Suppose now that f (X) < f (X ). If X leximax X , then X = X and f (X) = f (X ): contradiction. If X > leximax X , then taking advantage of the first part of the proof, we get f (X) > f (X ): contradiction. So X < leximax X . Consider now statement (2). If X leximax X , then X = X and f (X) = f (X ). Suppose now f (X) = f (X ). If X > leximax X , then taking advantage of the first part of the proof, we get f (X) > f (X ): contradiction. If X < leximax X , then taking advantage of the first part of the proof, we get f (X) < f (X ): contradiction. So X = leximax X . 2
Let us stress here that the condition of strict nondecreasingness is quite natural and not very demanding. Actually all the aggregation functions giving rise to IC merging operators we are aware of (including Σ, leximax , leximin, Σ n , etc.) satisfy non-decreasingness.

Given this proposition, defining other egalitarian distancebased merging operators requires to focus on other equity principles, or to weaken some IC postulates. We explore both ways in the following.

Thus, we first focus on another egalitarian condition from the social choice literature, namely Pigou-Dalton transfer principle [Dalton, 1920]. The idea underlying it is that every transfer from the most satisfied agent to the least satisfied one decreases the inequalities:

Definition 11 Let f be an aggregation function. f satisfies the Pigou-Dalton condition if for all vectors X = (x 1 , . . . , x n ) and

X = (x 1 , . . . , x n ), if x 1 < x 1 ≤ x 2 < x 2 and x 1 -x 1 = x 2 -x 2 and ∀i = 1, 2, x i = x i then f (X) < f (X ).
This principle states that if X can be obtained from X by just making some satisfaction transfer from a well-satisfied agent to a less satisfied one, without changing the fact that the first one is still more satisfied than the second one, then X is fairer than X.

This principle can be translated as follows for distancebased merging:

Definition 12 (Condition (PD)) If ∃k and l s.t. d(ω, K k ) < d(ω , K k ) ≤ d(ω , K l ) < d(ω, K l ) and d(ω , K k ) - d(ω, K k ) = d(ω, K l ) -d(ω , K l ) and ∀i = k and i = l, d(ω, K i ) = d(ω , K i ) then ω < E ω.
Of course not all distance-based IC operators satisfy the (PD) condition. However, it is satisfied by the well-known arbitration operators based on leximax :

Proposition 5 Let d be any distance.

• ∆ d,leximax satisfies the (PD) condition.

• ∆ d,Σ and ∆ d,leximin do not satisfy the (PD) condition.

Pre-IC Operators

We now define a general family of belief merging operators, called pre-IC merging operators, obtained by relaxing the two postulates (IC5) and (IC6) into two natural conditions used in other aggregation theories contexts.

Definition 13 A merging operator is pre-IC merging operator iff it satisfies (IC0) to (IC4), (IC7) to (IC8) and the following properties:

(IC5b) µ (K 1 ) ∧ µ (K 2 ) ∧ . . . ∧ µ (K n ) |= µ ({K 1 , K 2 , . . . , K n }) (IC6b) If µ (K 1 ) ∧ µ (K 2 ) ∧ . . . ∧ µ (K n ) is consistent, then µ ({K 1 , K 2 , . . . , K n }) |= µ (K 1 ) ∧ µ (K 2 ) ∧ . . . ∧ µ (K n )
Thus, switching from IC operators to pre-IC ones simply consists in replacing the postulates (IC5) and (IC6) postulates by the weaker postulates (IC5b) and (IC6b). Indeed, it is easy to prove that (IC5b) (resp. (IC6b)) is implied by (IC5) (resp. (IC6)). As a consequence, we have: Proposition 6 Every IC merging operator is a pre-IC merging operator.

Let us now present a representation theorem suited to the pre-IC family: Definition 14 A pre-syncretic assignment is a function mapping each profile E to a total pre-order ≤ E over Ω such that for any profiles E, E 1 , E 2 and for any belief bases K, K , the following conditions hold:

1. If ω |= E and ω |= E then ω ≡ E ω 2. If ω |= E and ω |= E then ω < E ω 3. If E 1 ≡ E 2 then ≤ E1 =≤ E2 4. ∀ω |= K, ∃ω |= K ω ≤ {K,K } ω 5b. If ∀i ω ≤ Ki ω then ω ≤ {K1,...,Kn} ω 6b. If ∀i ω ≤ Ki ω and ∃k ω < K k ω then ω < {K1,...,Kn} ω
Conditions 5b and 6b are direct translations of Pareto conditions, which are usual conditions in social choice, multicriteria decision making, etc. So they should be considered as minimal aggregation conditions to be satisfied. Conditions 5 and 6 (Definition 3) are much more demanding, since they constraint all unions of two profiles.

Proposition 7 A merging operator ∆ is a pre-IC merging operator iff there exists a pre-syncretic assignment that maps each profile E to a total pre-order ≤ E over Ω such that

[∆ µ (E)] = min([µ], ≤ E ).
Proof: Only If Let ∆ be a pre-IC merging operator. We associate with it a pre-syncretic assignment as follows: for any profile

E = {K 1 , K 2 , . . . , K n }, we define ≤ E by ω ≤ E ω if and only if ω |= ∆ µ (E) where [µ] = {ω, ω }.
From [Konieczny and Pino Pérez, 2002b], we know that ≤ E is a pre-order; furthermore, as ∆ satisfies (IC0-IC4) and (IC7-IC8), conditions 1 to 4 are satisfied by the assignment. We have then only to check conditions 5' and 6'. Suppose that ∀i ∈ {1, . . . , n}, ω

≤ Ki ω . Then ∀i ∈ {1, . . . , n}, ω |= ∆ {ω,ω } (K i ). Let µ such that [µ] = {ω, ω }: ∀i ∈ {1, . . . , n}, ω |= ∆ µ (K i ), so ω |= ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∆ µ (K n ). From (IC5'), we know that ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∆ µ (K n ) |= ∆ µ ({K 1 , K 2 , . . . , K n }), so ω |= ∆ µ ({K 1 , K 2 , . . . , K n }). Therefore, ω |= ∆ µ ({K 1 , K 2 , . . . , K n }): ω ≤ E ω , hence condition 5' is satisfied. Suppose that ∃k, ω < K k ω and ∀i = k, ω ≤ Ki ω . Then ω |= ∆ µ (K k ), ω |= ∆ µ (K k ) and ∀i = k, ω |= ∆ µ (K i ). We have ω |= ∆ µ (K k ), ω |= ∆ µ (K k ) and ∀i = k, ω |= ∆ µ (K i ), so ω |= ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ) and ω |= ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ): [∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n )] = {ω}. From (IC6'), and as ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ) is consistent, we know that ∆ µ ({K 1 , K 2 , . . . , K n }) |= ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ), so {ω} = [∆ µ ({K 1 , K 2 , . . . , K n })] and ω |= ∆ µ ({K 1 , K 2 , . . . , K n }). Therefore, ω |= ∆ µ ({K 1 , K 2 , . . . , K n }) and ω |= ∆ µ ({K 1 , K 2 , . . . , K n }): ω < E ω : so condition 6' is satisfied.
If Consider a pre-syncretic assignment mapping each belief set E to a total pre-order ≤ E over interpretations. We define an operator ∆ as follows:

[∆ µ (E)] = min([µ], ≤ E ).
From [Konieczny and Pino Pérez, 2002b], we know that ∆ satisfies (IC0-IC4) and (IC7-IC8). Let us show that ∆ satisfies (IC5'-IC6'). Suppose that

∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∆ µ (K n ) is con- sistent (if not, (IC5'-IC6') is trivially satisfied). Let ω |= ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ). So ∀ω |= µ, ω ≤ Ki ω . From 5', we know that ∀ω |= µ, ω ≤ {K1,K2,...,Kn} ω : then ω |= ∆ µ ({K 1 , K 2 , . . . , K n }). We can con- clude that ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ) |= ∆ µ ({K 1 , K 2 , . . . , K n }) and (IC5') is satisfied. To show (IC6'), suppose that ∆ µ ({K 1 , K 2 , . . . , K n }) |= ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ). So ∃ω s.t. ω |= ∆ µ ({K 1 , K 2 , . . . , K n }) and ω |= ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ). As ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ) is consistent, there is an interpretation ω |= ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ). So ∀i ω ≤ Ki ω and as ω |= ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ), ∃k s.t. ω |= ∆ µ (K k ): ω < K k ω. With condition 6', we know that ω < {K1,K2,...,Kn} ω: contradiction with the fact that ω |= ∆ µ ({K 1 , K 2 , . . . , K n }). Hence, ∆ µ ({K 1 , K 2 , . . . , K n }) |= ∆ µ (K 1 ) ∧ ∆ µ (K 2 ) ∧ . . . ∧ ∆ µ (K n ): (IC6') is satisfied. 2
As one can expect, it is much easier to satisfy the pre-IC merging conditions than IC merging ones. We can for instance show that:

Proposition 8 If d is any distance and f is any aggregation function satisfying strict non-decreasingness, then the merging operator ∆ d,f is a pre-IC merging operator.

One can compare this result with a corresponding one about distance-based IC merging operators, reported in [Konieczny, Lang, and Marquis, 2004], and showing that the aggregation function f has to satisfy two additional conditions in order to guarantee that the distance-based merging operators given by d and f are IC merging operators.

Median Operators

In this section we define a new family of merging operators using generalized median aggregation functions. Interestingly, some operators of this family are pre-IC merging operators and they satisfy (Arb). The idea of using the median value is very motivated by trying to be as fair as possible. Instead of focusing on a unique aggregation function, we study a full family of k-median aggregation functions, inspired by the phantom voters voting rules of [Moulin, 1988].

Definition 15 Let k ∈]0, 1] be a real number, the k-median med k ({x 1 , . . . , x n }) of a multi-set X = {x 1 , . . . , x n } of values from a totally ordered set, is the value m k = x σ( n * k ) of X, where σ is a permutation of X where the x i are sorted in ascending order ( . denotes the ceiling function).

For k = 0.5, the usual notion of median is retrieved. In many cases these k-median functions med k are not discriminative enough, just like min and max functions. So, we can define k-leximedian operators, noted k -leximed , which are to med k what leximin (resp. leximax ) is to min (resp. max ).

Definition 16 Let L 1 and L 2 be two multi-sets consisting of n elements from a totally ordered set:

L 1 ≤ k leximed L 2 iff • med k (L 1 ) < med k (L 2 ) or • med k (L 1 ) = med k (L 2 ) and L 1 \ {med k (L 1 )} ≤ k leximed L 2 \ {med k (L 2
)} Let us define successively the k-median merging operators, and the k-leximedian ones:

Definition 17 Let E = {K 1 , ..., K n } be a profile, d a dis- tance between interpretations and k ∈]0, 1] a real num- ber. Let d d,k med (ω, E) = med k (d(ω, K 1 ), d(ω, K 2 ), . . . ,
Again, some standard operators are recovered by considering specific values of k: ∆ d,leximed k with k ∈]0, 1 n [ corresponds to the leximin operator ∆ d,leximin , and ∆ d,leximed 1 to the leximax operator ∆ d,leximax .

As expected ∆ d,leximed k operators satisfy more interesting properties than ∆ d,med k ones:

Proposition 12 For any distance d and any k ∈]0, 1], ∆ d,leximed k is a pre-IC merging operator.

We do not have better than that. In particular, these operators are not IC merging ones in the general case:

Proposition 13 ∆ d,leximed k does not satisfy any of (IC5), (IC6), (Maj) and (Arb) in general.

Concerning egalitarian properties, we reach the arbitration property, but not the other ones:

Proposition 14 If k ≥ 0.5, then ∆ d,leximed k satisfies (Arb) but does not satisfy (PD) or (SHE) in general.
It is easy to explain why the condition k ≥ 0.5 is needed. Indeed, we know that when k goes towards 0 the leximed k function goes towards leximin, and that when k goes towards 1 leximed k goes towards leximax . So it is natural to obtain an egalitarian behaviour for values between "classical" median (k=0.5) and leximax .

Considering Proposition 4, Proposition 14 shows that relaxing some IC postulates is a way for escaping from the leximax -based operators while satisfying some egalitarian condition.

Cumulative Sum Merging Operators

A very convenient representation of the inequalities of a distribution of income is the Lorenz curve [Lorenz, 1905]. The principle is to focus on the poorest (least satisfied) agents, by looking first as the utility of the poorest one, then at the sum of the utilities of the two poorest ones, etc. To be more precise, on a Lorenz curve, each element k of the x-axis corresponds to the k poorest agents and the value associated with it on the y-axis is the sum of the utilities of those agents.

This curve can be interpreted in different ways to measure how much a distribution is fair. In particular, the fairest distribution is when for any n, the n% poorest agents own n% of the income. The well-known Gini coefficient [Gini, 1921;Sen, 1973;Dutta, 2002], one of the main inequality measures, is the (double of the) area between the Lorenz curve and the fairest distribution.

In the following, we adhere to the notion of cumulative sum for defining a new family of merging operators. We translate the distance between a base and an interpretation into a satisfaction value by reversing the scale. Then we compute the cumulative satisfaction vector and take advantage of an aggregation function on it.

Let us define formally the cumulative sum merging operators:

Definition 19 Let d be a distance between interpretations, f an aggregation function, E a profile and µ an integrity constraint. Let M = max ({d(ω, ω ) | ω, ω ∈ Ω}). For an interpretation ω, we consider the vector (w σ(1) , w σ(2) , . . . , w σ(n) ) where w i = M -d(ω, K i ) is the satisfaction value of agent i for the interpretation ω, and σ is the permutation of {1, . . . , n} sorting the w i in ascending order (the less the least satisfied). Then we define the vector of cumulated satisfaction of µ, W d (ω, E) = (W 1 , W 2 , . . . , W n ), where W i = Σ i k=1 w σ(k) . Finally, the selected interpretations are the ones which maximize the cumulated satisfaction W d (ω, E):

[∆ CS(d,f ) µ (E)] = {ω |= µ | f (W d (ω, E)) is maximal }.
Let us illustrate the behavior of a cumulative sum merging operator on a simple example:

Example 3 We step back to Example 2. The computations are presented in Table 2, in which the values represent satisfaction values of the bases (the more the best), and not anymore distances (the less the best).

We get [∆ CS(d H ,Σ) (E)] = {000}. The selected interpretation is 000, because the sum of the cumulative satisfaction vector gives the maximal value of 13.

We recover some existing operators as cumulative sum ones:

Proposition 15 Let d be any distance. • ∆ CS(d,leximin) = ∆ d,leximax • ∆ CS(d,leximax ) = ∆ d,leximin
Let us finally turn to the logical properties:

Proposition 16 If d is any distance, and f is an aggregation function satisfying strict non-decreasingness, then ∆ CS(d,f ) is a pre-IC merging operator.

• ∆ CS(d,f ) does not satisfy (Arb) and (Maj) in the general case.

• ∆ CS(d,f ) does not satisfy (IC5) and (IC6) in the general case.

While (Arb) is not satisfied in general, the Pigou-Dalton condition is ensured for instance when any sum of the mpowers, m varying, is used as aggregation function:

Proposition 17 For all integer m, ∆ CS(d,Σ m ) satisfies (PD), but (SHE) is not satisfied.

) < d(ω , K k ) ≤ d(ω , K l ) < d(ω, K l ) and d(ω , K k ) -d(ω, K k ) = d(ω, K l ) -d(ω , K l ) and ∀i = k and i = l, d(ω, K i ) = d(ω , K i ). We note g the value d(ω , K k ) -d(ω, K k ), so we have d(ω , K k ) = d(ω, K k ) + g and d(ω , K l ) = d(ω, K l ) - g. g is strictly positive. We note ∀i, x i = n -d(ω, K i ), x k = n -d(ω , K k ) and
x l = n -d(ω , K l ). We suppose that the x i are ordered in the ascending way: x 1 ≤ x 2 ≤ . . . ≤ x n . Let l and k be the relative ranks of x l and x k into the x i -th. We suppose l = l and k = k. As x l > x l ≥ x k > x k , we know that if l = l, l < l and if k = k, k > k. We have then the following table, if k = k and l = l: rank : w(ω, K i ) : w(ω , K i ) :

1 x 1 x 1 . . . . . . . . . k -1 x k-1 x k-1 k x k x k+1 k + 1 x k+1 x k+2 . . . . . . . . . k -1 x k -1 x k k x k x k = x k + g k + 1 x k +1 x k +1 . . . . . . . . . l -1 x l -1 x l -1 l x l x l = x l -g l + 1 x l +1 x l l -1 x l-1 x l-2 l x l x l-1 l + 1 x l+1 x l+1 . . . . . . . . . n x n x n
From rank 1 to rank k -1, the x i -th are identical so the W m i also.

From rank k to rank k -1, we have in Σ m (W d (ω, E)):

Σ m k...(k -1) (W d (ω, E)) = (x1 + . . . + x k-1 + x k ) m + . . . +(x1 + . . . + x k-1 + x k + . . . + x k -1 ) m and in Σ m (W d (ω , E)): Σ m k...(k -1) (W d (ω , E)) = (x1 + . . . + x k-1 + x k+1 ) m + . . . +(x1 + . . . + x k-1 + x k+1 + . . . + x k ) m (3)
In equation 3, the values from x k to x k -1 are remplaced by the values from x k+1 to x k . Since the x i -th are increasing, we have Σ

m k...(k -1) (W d (ω, E)) ≤ Σ m k...(k -1) (W d (ω , E)). From rank k to rank l -1, we have in Σ m (W d (ω, E)): Σ m k ...(l -1) (W d (ω, E)) = (x1+. . .+x k-1 +x k +. . .+x k ) m +. . . +(x1 + . . . + x k-1 + x k + . . . + x l -1 ) m and in Σ m (W d (ω , E)): Σ m k ...(l -1) (W d (ω , E)) = (x1 + . . . + x k-1 + x k+1 + . . . +x k -1 + x k ) m + . . . + (x1 + . . . + x k-1 + x k+1 + . . . +x k + x k +1 + . . . + x l -1 ) m = (x1 + . . . + x k-1 + x k+1 + . . . + x k -1 + x k + g) m + . . . + (x1 + . . . + x k-1 + x k+1 + . . . + x k + g + x k +1 + . . . + x l -1 ) m (because x k = x k + g). Each term of Σ m (W d (ω , E)) is equal to one term of Σ m (W d (ω, E)) plus g. As g > 0, we have: Σ m k ...(l -1) (W d (ω, E)) < Σ m k ...(l -1) (W d (ω , E)). From rank l to rank l, we have in Σ m (W d (ω, E)): Σ m l ...l (W d (ω, E)) = (x1 + . . . + x k + x k+1 + . . . + x l -1 +x l ) m + . . . + (x1 + . . . + x l -1 + x l + . . . + x l-1 + x l ) m and in Σ m (W d (ω , E)): Σ m l ...l (W d (ω , E)) = (x1 + . . . + x k + g + x k+1 + . . . + x l -1 +x l ) m + . . . + (x1 + . . . + x k + g + x k+1 + . . . + x l + x l + . . . + x l-2 + x l-1 ) m = (x1 + . . . + x k + g + x k+1 + . . . +x l -1 + x l -g) m + . . . + (x1 + . . . + x k + g + x k+1 + . . . +x l -g + x l + . . . + x l-1 ) m because x l = x l -g, so: Σ m l ...l (W d (ω , E)) = (x1 + . . . + x k + x k+1 + . . . + x l -1 +x l ) m + . . . + (x1 + . . . + x k + x k+1 + . . . + x l + x l . . . + x l-1 ) m
In each term of Σ m l ...l (W d (ω , E)), compared with Σ m l ...l (W d (ω, E)), one element x l +i with i varying from 0 to l -l of the sum W j is remplaced by x l . Since the x i -th are increasing,

x l +i ≤ x l for 0 ≤ i ≤ l -l , so Σ m l ...l (W d (ω, E)) ≤ Σ m l ...l (W d (ω , E)). From rank l + 1 to rank n, we have in Σ m (W d (ω, E)): Σ m (l+1)...n (W d (ω, E)) = (x1 + . . . + x l -1 + x l + . . . + x l-1 +x l+1 ) m + . . . + (x1 + . . . + x l -1 + x l + . . . +x l-1 + x l + x l+1 + . . . + xn) m and in Σ m (W d (ω , E)): Σ m (l+1)...n (W d (ω , E)) = (x1 + . . . + x k + x k+1 + . . . + x l -1 + x l+1 ) m + . . . + (x1 + . . . + x k + x k+1 + . . . + x l + x l + . . . + xn) m So Σ m (l+1)...n (W d (ω , E)) = Σ m (l+1)...n (W d (ω, E)). Finally, we obtain Σ m (W d (ω, E)) < Σ m (W d (ω , E))
, for all integer m, and ω is selected : Pigou-Dalton is satisfied. For the other cases, when x l (resp. x k ) has the same rank as x l (resp. x k ), there are less cases to be studied, the table is simpler, but the result still holds.

2

Conclusion

In this paper, we have investigated alternative egalitarian conditions to the arbitration postulate. Especially, we have translated to the belief merging framework two egalitarian conditions: Sen-Hammond equity, and Pigou-Dalton property.

We have shown that the distance-based merging operators satisfying Sen-Hammond equity are mainly those for which leximax is the aggregation function. This led us to introduce a new family of belief merging operators, the pre-IC operators, which includes the family of IC merging operators as a specific case. We have pointed out a representation theorem for this family, which allows us to define easily some distance-based pre-IC operators. In order to enrich the family of egalitarian merging operators, we have considered two new families of belief merging operators, based respectively on the median and on an aggregated sum (Lorenz curves). We have shown that the operators based on the leximed k aggregation functions (with k ≥ 0.5 ) are pre-IC operators which satisfy the arbitration postulate (Arb). We have also proved that the ∆ CS(d,Σ n ) operators from the cumulative sum family are pre-IC operators satisfying (PD).

Besides theory-oriented results, this work produced two interesting families of egalitarian operators: cumulative sums ones and leximed k ones. Before this work the only known egalitarian merging operators were the leximax -based ones. Egalitarian operators are significant for all applications where consensual results are expected, i.e., all agents are supposed to be satisfied in the best way, contrariwise to utilitarian/majority operators. Whereas utilitarian operators can be used when the information sources are sensors or databases, egalitarian operators are particularly important in applications where such sources are agents which are autonomous enough to reject the result of the merging if they consider that it is too far from their position.

As already discussed in previous merging papers, usual IC merging operators can be used to merge either beliefs or goals. This distinction between belief and goals do not seem to impact any of the usual IC postulates. It is straighforward to consider egalitarian merging operators when merging goals, if one tries to achieve a "fair" result. As to the belief merging issue, when the aim is to find the correct state of the world, majority methods can appear more appealing. In [Everaere, Konieczny, and Marquis, 2010b] we discussed this truth-tracking problem for merging, and we made a distinction between two possible uses of belief merging. The one relating to truth-tracking is called the epistemic view, and in this case it is natural to consider only majority operators (this is a consequence of Condorcet Jury Theorem [Everaere, Konieczny, and Marquis, 2010b]). But there is a second possible use, called the synthesis view, where the aim is to best represents the opinion of the group (profile). This view has nothing to do with the correct state of the world, the merging process only cares about individual opinions. In this case egalitarian operators are appealing, since they provide in a sense a more robust (i.e. more consensual) view of the opinion of the group than majority operators.

  Proof: ∆ CS(d,Σ m ) satifies Pigou-Dalton property. Consider ω and ω s.t. ∃k and l s.t. d(ω, K k

Table 2 :

 2 Merging with ∆ CS(d H ,Σ)

		K1	K2	K3	Cum. Sat.	Σ
	000	3	2	2	(2, 4, 7)	13
	001	2	3	1	(1, 3, 6)	10
	010	2	1	1	(1, 2, 4)	7
	011	1	2	0	(0, 1, 3)	4
	100	3	1	3	(1, 4, 7)	12
	101	2	2	2	(2, 4, 6)	12
	110	2	0	2	(0, 2, 4)	6
	111	1	1	1	(1, 2, 3)	6

When E = {K} we note µ(K ) instead of µ({K }).

For every pre-order ≤, < denotes its strict part and the corresponding indifference relation. Furthermore, we will use ≤K as a short for ≤ {K} , and ≤ω as a short for any ≤ {Kω } where ω is the unique model of Kω.

Formally, we work with pseudo-distances since triangular inequality is not required, but for the sake of simplicity we will abuse words in this way.

 4 Strictly speaking, it is a family of mappings, one for each

m.5 The leximin (resp. leximax) aggregation function selects the interpretations that are minimal for the lexicographic order, once the distances are sorted into the increasing (resp. decreasing) order.

If X leximax X , then ∀i, xi = x i , so X=X'.

K1 K2

K3

distance vector med 0.5 000 0 1 1 (0, 1, 1)

Here is an example illustrating the behaviour of k-median operators:

Example 2 We consider a profile E of three bases such that

There is no integrity constraint (µ = ), we use the Hamming distance d H and the value k = 0.5 for the "standard" median. The computations are presented in Table 1.

We get [∆ d H ,med 0.5 (E)] = {100}. The only selected interpretation is 100, because the best vector is (0, 0, 2), with a median value of 0. Some specific values of k lead to well-known merging operators: given a profile E of n bases, ∆ med , with ∈]0, 1 n ] corresponds to the min operator, and ∆ med α , with α ∈ ] n-1 n , 1] to the max operator.

Let us now make precise the rationality postulates satisfied by these operators: Proposition 9 For any real number k ∈ ]0, 1] and any distance d, ∆ d,med k satisfies (IC0), (IC1), (IC3), (IC4), (IC7), (IC8) and (IC5b). ( IC2), (IC5), (IC6), (IC6b), (Maj) and (Arb) are not satisfied in general.

Proof: For space reasons, we provide only the less obvious proofs.

As a consequence ω 2 is selected. (IC5) and (IC6) Suppose k = 0.5, and ω 1 s.t. d d,0.5 m (ω 1 , E 1 ) = med 0.5 (0, 0) = 0, d d,0.5 m (ω 1 , E 2 ) = med 0.5 (3, 4, 4) = 4 and accordingly d d,0.5 m (ω 1 , E 1 E 2 ) = med 0.5 (0, 0, 3, 4, 4) = 3. Suppose ω 2 s.t.

(and then ∆ d,med 0.5 µ (E 1 ) and ∆ d,med 0.5 µ (E 2 ) are jointly consistent), whereas [∆ d,med 0.5 µ (E 1 E 2 )] = {ω 2 }. This example shows that neither (IC5) nor (IC6) is satisfied.

(Arb) Suppose 0 < k < 0.5 (so that ∆ d,med k is equivalent to ∆ d,min ). The following example shows that (Arb) is not satisfied. Let ω 1 , ω 2 , ω 3 be three interpretations s.t. d(ω 1 , ω 3 ) = 1, d(ω 1 , ω 2 ) = 1 and d(ω 2 , ω 3 ) = 2. The bases K 1 and K 2 are defined by K 1 = {ω 2 } and K 2 = {ω 3 }; and the constraints µ 1 and µ 2 are defined by µ 1 = {ω 1 , ω 3 },µ 2 = {ω 1 , ω 2 }. Then we have:

It turns out that k-median operators satisfy some but not all the expected rationality properties. In particular one very natural postulate (IC2), asking that the result of the merging is just the conjunction of the bases when this conjunction is consistent, is not satisfied (except for values of k making the k-median identical to max ). We also have:

No other equity condition is satisfied by such operators:

Proposition 11 Whatever k, ∆ d,med k does not satisfy (PD) or (SHE).

Proof: Consider the following counter-example, for k < 0.5: med k (1, 3) = 1 and med k (2, 2) = 2: (1, 3) < med k (2, 2): none of (PD) or (SHE) is satisfied. Consider the following counter-example, for 0.5 ≤ k < 1: med k (0, 4, 4, 7) = 4 and med k (0, 4, 5, 6) = 5 (0, 4, 4, 7) < med k (0, 4, 5, 6): none of (PD) or (SHE) is satisfied. Consider the following counter-example, for k = 1: med k (0, 4, 4, 7) = 7 and med k (0, 3, 4, 8) = 8 (0, 4, 4, 7) < med k (0, 3, 4, 8): none of (PD) or (SHE) is satisfied.

2

Let us now turn to the k-leximedian operators, that satisfy more expected properties: