L Cholvy

L Perrussel

J-M Thévenin

Toulouse Archive Ouverte

Keywords:

Any decision taken by an agent requires some knowledge of its environment. Communication with other agents is a key issue for assessing the overall quality of its own knowledge. This assessment is a challenge itself as the agent may receive information from unknown agents. The aim of this paper is to propose a framework for assessing the reliability of unknown agents based on communication. We assume that information is represented through logical statements and logical inconsistency is the underlying notion of reliability assessment. In our context, assessing consists of ranking the agents and representing reliability through a total preorder. The overall communication set is first evaluated with the help of inconsistency measures. Next, the measures are used for assessing the contribution of each agent to the overall inconsistency of the communication set. After stating the postulates specifying the expected properties of the reliability preorder, we show through a representation theorem how these postulates and the contribution of the agent are interwoven. We also detail how the properties of the inconsistency measures influence the properties of the contribution assessment. Finally we describe how to aggregate different reliability preorders, each of them may be based on different inconsistency measures.

Introduction

To be able to act or deliberate, any rational agent must acquire knowledge of its environment. It gets it by merging information provided by its own sensors and/or by merging information communicated by other agents. Merging basic information is a key issue for any agent as it is the underlying rational for decision making and it contributes to justify the agent's epistemic state. Techniques for merging raw information have been studied in an extensive way. These techniques usually assume that all information provided by the sources (i.e. agents) should be considered as a whole. Two different approaches have been studied: the first one considers sources in an equal way and has led to merging techniques such as majority merging, negotiation, arbitration merging or distance-based merging for solving conflict between contradicting information [START_REF] Konieczny | Merging information under constraints: a logical framework[END_REF][START_REF] Benferhat | Possibilistic merging and distance-based fusion of propositional information[END_REF][START_REF] Qi | Combining multiple prioritized knowledge bases by negotiation[END_REF][START_REF] Everaere | Disjunctive merging: Quota and Gmin merging operators[END_REF]. The second one distinguishes sources through a reliability criterion. Taking sources reliability into account provides rationales for discounting or ignoring pieces of information whose source is not considered as sufficiently reliable. Some promote a quantitative model of reliability: information sources are associated with a reliability level represented by a number used by the merging operator. According to the belief function theory, the reliability level of a source is a number between 0 and 1. This number is then used by the discounting rule in order to weaken the importance of infor-mation provided by this source [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. Some others promote a qualitative approach to reliability and consider that information sources are ranked according to their reliability. This order or pre-order is then used by the merging operator. In [START_REF] Cholvy | Reasoning About Merged Information[END_REF], the author defines a merging operator which assumes that the sources are totally ordered: if s is said to be more reliable than s and together provide contradicting information, then information provided by s is privileged; while information provided by s which does not contradict information of s is also considered as acceptable. The same idea is followed by [START_REF] Liau | A modal logic framework for multi-agent belief fusion[END_REF] for reasoning about more complex beliefs and in [START_REF] Lorini | A modal framework for relating belief and signed information[END_REF] for revising a belief base. All these works assume that the reliability of the sources is given as a parameter (quantitative or qualitative), they do not address the question of how to build up this reliability.

In this present paper our aim is to address the key question of how to build a reliability preorder of information sources, in a context where sources are unknown: no extra information about sources is available and information provided by the sources is only qualitative (i.e., statements). We adopt a qualitative point of view to represent reliability: the relative reliability of information sources is represented by a total preorder. We propose to consider a phase, before the information merging phase, during which information sources are observed in order to obtain a reliability preorder. The purpose of this phase is to analyze the inconsistency of information reported by the different sources w.r.t. some trusted knowledge.

Our main goal is thus to show that the relative reliability of information sources can be estimated from the inconsistency of reported information. Two different approaches can be followed. The first approach consists in using an ad-hoc model for reported information and in developing new inconsistency measures. The second approach consists in modeling reported information in a conventional way in order to use well known inconsistency measures.

In a recent paper [START_REF] Cholvy | Consistency-based reliability assessment[END_REF], we followed the first approach. Reported information was modeled by pairs: < agent, f ormula >, f ormula representing a piece of information communicated by agent. For instance, the set {< a, p >, < b, ¬p >, < b, q >} represented the fact that agent a had reported p, agent b had reported ¬p and had also reported q. The main notions (inconsistency, minimal inconsistent subsets, inconsistency measures...) available in the literature have been adapted to this model.

In this paper, our very motivation is to show an original application of inconsistency measures, i.e. reliability estimation. Our starting point is the existing inconsistency measures. Hereafter, we simplify the representation of reported information so that we can re-use these existing inconsistency measures for elaborating agent's reliability.

Our original contributions consist in (i) characterizing the individual contribution of each agent to the overall inconsistency of a set of reported information and (ii) introducing postulates which characterize the expected properties of the reliability preorder; Based on these axiomatic perspective on reliability assessment, we show (i) how the properties of the inconsistency measure influence the properties of the contributions measures and (ii) how postulates about reliability and properties of agent contribution are related through a representation theorem. Finally, we show how to aggregate several preorders possibly obtained through different inconsistency measures; namely we show how the overall aggregated preorder may satisfy the reliability postulates if the initial preorders also satisfy these postulates.

This paper is organized as follows. Section 2 and Section 3 introduce the main notions needed to assess reliability of agents. They introduce inconsistent communication sets and focus on measuring the inconsistency in communication sets. Based on the inconsistency measures, Section 4 shows how to assess the individual contribution of an agent to the overall inconsistency of a communication set. Contribution is first characterized in an axiomatic way and next two possible contribution functions instantiating the expected properties are detailed. Some implementation and complexity considerations are also addressed. Section 5 proposes a set of postulates which axiomatically characterize reliability preorders and show through two representation theorems how these postulates and the agent contributions are related. Still in Section 5, we present two possible solutions for building a reliability preorder compliant with these postulates. Section 6 considers the aggregation of several reliability preorders and shows how Arrow's condition for aggregation and our postulates interplay. Finally, Section 7 concludes the paper and discusses future work.

Inconsistent communication sets

This section introduces communication sets and focuses on their inconsistency.

Preliminaries

Let L be a propositional language of formulas defined over a finite set of propositional symbols P, propositional constants , ⊥ and the logical connectives ∧, ∨, ¬. We use p, q, r, ... to denote the propositional symbols and Greek letters φ, ψ, ... to denote formulas of the classical propositional logic defined over L. An interpretation i is a total function from P to {0, 1} from which an assignment to {0, 1} is generated for all the formulas of L defined in the usual way of classical logic. As usual, i( ) = 1 and i(⊥) = 0. Interpretation i is a model of formula φ iff i(φ) = 1. Tautologies are formulas which are interpreted by 1 in any interpretation. We write |= φ when φ is a tautology. A formula is consistent iff it has at least one model. Otherwise it is inconsistent.

A communication base 1 K is a finite (possibly empty) set of formulas of L. At(K ) denotes the set of propositional symbols appearing in formulas which belong to K . A communication base is consistent iff the conjunction of its formulas is consistent. Otherwise, it is inconsistent. For a communication base K , M I(K ) is the set of minimal inconsistent subsets of K , i.e., M I

(K ) = {K ⊆ K | K is inconsistent and ∀K ⊂ K K is consistent}. MC(K ) is the set of maximal consistent subsets of K , i.e., MC(K ) = {K ⊆ K | K is consistent and ∀K s.t. K ⊂ K K is inconsistent}. If M I(K ) = {M 1 , ..., M n } then Problematic(K ) = M 1 ∪ ... ∪ M n , and F ree(K ) = K \ Problematic(K ).
The set of formulas in K that are inconsistent is given by the function Self contradiction(K ) = {φ ∈ K | φ is inconsistent}. Notice that these definitions are provided by [START_REF] Grant | Measuring the good and the bad in inconsistent information[END_REF].

Finally, as shown in [START_REF] Grant | Measuring the good and the bad in inconsistent information[END_REF], a three-valued logic can be used to give a semantics to inconsistent formulae. The three values are T , F , B where T and F correspond to the classical values 1, 0 respectively and the additional truth value B stands for both and represents inconsistency. Assuming that the three values are ordered by: F < t B < t T , the valuation of formulae in an interpretation i is given by: i

( ) = T , i(⊥) = F , i(¬φ) = B ⇐⇒ i(φ) = B, i(¬φ) = T ⇐⇒ i(φ) = F , i(φ ∧ ψ) = min ≤t (i(φ), i(ψ)), i(φ ∨ ψ) = max ≤t (i(φ), i(ψ)). Interpretation i is a model of K if no formula in K is assigned the truth value F . We write i |= 3 K . Binar ybase(i) = {p ∈ P | i(p) = T or i(p) = F } and Conf lictbase(i) = {p ∈ P | i(p) = B}.
Notice that for i |= 3 K , Conf lictbase(i) returns the subset of propositional symbols directly involved in inconsistency according to i.

Communication sets

From now, we assume a finite set of agents A = {a 1 , ..., a n } (n ≥ 1). For each agent a i , K (a i ) is an L-formula which is the conjunction of all the pieces of information reported by a i . K (a i ) is called report of agent a i . The report of an agent which provides no information is any tautology or, for short, . Given K (a 1 ), ..., K (a n ), the multi-set of formulas = {K (a 1 ), ...,

K (a n )} is called communication set. Given = {K (a 1 ), ..., K (a n )} and C = {a i 1 , .., a i m } ⊆ A, we define (C) by (C) = {K (a i 1 ), .., K (a i m )}.
Consider now two situations, one in which agent reports are K (a 1 )...K (a n ) and a second one in which they report K (a 1 )...K (a n ). Let = {K (a 1 ), ..., K (a n )} and = {K (a 1 ), ..., K (a n )} be the corresponding communication sets. We write ≡ ( and

are equivalent) iff ∀a ∈ A, |= K (a) ↔ K (a). That is, a's report in is equivalent to a's report in
. We write ( and

are weakly equivalent) iff ∀a ∈ A, ∃b, ∃c ∈ A such that |= K (a) ↔ K (b) and |= K (a) ↔ K (c).
That is, we relax here the constraint that report of agent a should be equivalent both in and ; instead we only require some other agent, possibly different from a, reports equivalent information.

I C -inconsistent communication sets

In the context of a communication set , consistency will be evaluated with respect to some integrity constraints IC which is a consistent formula of L. IC has to be viewed as information taken for granted or certain. Thus we say that = {K (a 1 ), ...,

K (a n )} is I C -inconsistent iff ∪ {IC} is inconsistent; otherwise is I C -consistent.
In the following, we adapt the definitions given in the preliminaries to the case of communication sets.

Definition 1.

•

⊥ IC is the multi-set of minimal IC -inconsistent subsets of i.e the multi-set of X ⊆

such that X is IC -inconsistent and ∀X X ⊂ X, X is IC -consistent. • IC = {X ⊆ : X is IC -consistent and ∀X X ⊂ X , X is IC -inconsistent} is the set of maximal IC -consistent sub- multisets of . • Problematic( ) = M∈ ⊥IC M. • F ree( ) = \ Problematic( ). • Self contradiction( ) = {K (a) ∈ : K (a) ∧ IC is inconsistent}.

I C -inconsistent sets of agents

We finally introduce the notion of minimal IC -inconsistent subsets of agents and the notion of problematic agents which are agents whose reports are problematic:

Definition 2. • A ⊥ IC = {X ⊆ A : (X) ∈ ⊥ IC}. • Problematic( A) = {a ∈ A : K (a) ∈ Problematic( )}. Example 1. Consider A = {a, b, c}, IC = ¬q, K (a) = p, K (b) = ¬p ∧ q, K (c) = r ∧ s. i.e.
, a has reported p, b has reported ¬p and q, and c has reported r and s. Here, = {p, ¬p ∧q, r ∧ s}. Thus, ⊥ IC = {{¬p ∧q}}, IC = {{p, r ∧ s}}, A ⊥ IC = {{b}} and Problematic( A) = {b}.

Example 2. Assume

A = {a, b, c}, IC = ¬(p ∧ q), K (a) = K (b) = p, K (c) = q.
Here, = {p, p, q}. Thus, ⊥ IC = {{p, q}, {p, q}}. Problematic( ) = {p, q} and F ree( ) = ∅. A ⊥ IC = {{a, c}, {b, c}} and Problematic( A) = {a, b, c}.

Measuring the I C -inconsistency of communication sets

Understanding the nature of inconsistency of a set of formulas is an important topic which aroused a great amount of research during the past decade The purpose is to analyze to which degree a set of formulas is inconsistent. A lot of inconsistency measures have been proposed according to different points of view: some of them are based on minimal inconsistent subsets [START_REF] Hunter | Approaches to measuring inconsistent information[END_REF][START_REF] Hunter | Measuring inconsistency through minimal inconsistent sets[END_REF][START_REF] Mu | A syntax-based approach to measuring the degree of inconsistency for belief bases[END_REF][START_REF] Jabbour | Inconsistency measures thanks mus decomposition[END_REF] or on maximal consistent subsets [START_REF] Grant | Measuring the good and the bad in inconsistent information[END_REF][START_REF] Ammoura | On measuring inconsistency using maximal consistent sets[END_REF], some consider paraconsistent models such as three valued logic [START_REF] Hunter | On the measure of conflicts: Shapley inconsistency values[END_REF][START_REF] Grant | Measuring the good and the bad in inconsistent information[END_REF], some consider probabilistic functions over the underlying propositional language [START_REF] Thimm | Stream-based inconsistency measurement[END_REF], some consider model distance [START_REF] Grant | Distance-based measures of inconsistency[END_REF] and finally some are proof-based [START_REF] Jabbour | Measuring inconsistency through minimal proofs[END_REF]. For a detailed review of these inconsistency measures we refer the reader to [START_REF] Thimm | On the expressivity of inconsistency measures[END_REF]. In this section, we first review some well-known inconsistency measures then we show our requirements to adapt them to our context.

Inconsistency measures for sets of formulas

According to [START_REF] Grant | Measuring the good and the bad in inconsistent information[END_REF], an inconsistency measure on sets of formulas is a function I which assigns any set of formulas K to an element of R + satisfying at least the following three properties:

• Consistency: I(K ) = 0 iff K is consistent. • Monotony: if K ⊆ K , then I(K ) ≤ I(K ). • Free formula independence: If φ ∈ F ree(K ) then I(K ) = I(K \ {φ}).
That is, the measure of inconsistency of a set of formulas is null iff this set is not inconsistent. The measure of inconsistency of a set of formulas does not decrease if we add more formulas. Finally, removing a formula that does not cause any contradiction does not change the inconsistency measure.

Let us now briefly review some inconsistency measures for sets of formulas, introduced in the literature [START_REF] Hunter | Approaches to measuring inconsistent information[END_REF][START_REF] Hunter | Measuring inconsistency through minimal inconsistent sets[END_REF][START_REF] Hunter | On the measure of conflicts: Shapley inconsistency values[END_REF][START_REF] Grant | Measuring the good and the bad in inconsistent information[END_REF] •

I D (K ) = 0 if K is consistent; 1 otherwise. • I C (K ) = |M I(K )|. • I M (K ) = (|MC(K )| + |Self contradictions(K )|) -1. • I P (K ) = |Problematic(K )|. • I Q (K ) = 0 if K is consistent; K ∈MI(K ) 1 |K | otherwise. • I B (K ) = min{|Conf lictbase(i)| | i |= 3 K }.
I D (K ) is a trivial measure which assigns 0 to any consistent set of formulas and 1 to any inconsistent set. It does not quantify how much K is inconsistent. I C (K ) counts the number of minimal inconsistent subsets of K . I M (K ) counts the number of maximal consistent subsets together with the number of contradictory formulas but 1 to make I M (K ) = 0 when K is consistent. I P (K ) counts the number of formulas in minimal inconsistent subsets of K . I Q (K ) computes the weighted sum of the minimal inconsistent subsets of K , where the weight is the inverse of the size of the minimal inconsistent subset, so that smaller inconsistent subsets are regarded as more inconsistent than larger ones. I B (K ) returns the minimum number of propositional symbols that have to be set to value B in order to get a three valued model of K . Measures I C (K ), I P (K ) and I Q (K ) assume that inconsistency is rooted in minimal inconsistent subsets: removing any formula from a minimal inconsistent subset in sufficient to produce a maximal consistent subset. To some extent I M (K ) can be viewed as a variant of these inconsistency measures. It is interesting to note that while I C (K ) give the same score to sets of formulas containing the same number of minimal inconsistent subsets, I Q (K ) is able to differentiate their level of inconsistency considering that the smaller is the size of a minimal inconsistent subset, the bigger is the amount of inconsistency. Measures I B and I L P m follow a different approach assessing the severity of inconsistency by considering the number of propositional symbols involved in inconsistency.

J. Grant and A. Hunter showed in [START_REF] Grant | Measuring the good and the bad in inconsistent information[END_REF] that inconsistency measures can be used to order several sets of formulas from the least inconsistent one to the most inconsistent one. They defined two inconsistency measures I x and I y as being ordercompatible if for all sets of formulas K 1 and K 2 , I x (K 1 ) < I x (K 2 ) iff I y (K 1 ) < I y (K 2 ). They proved that I C , I M , I P , I Q and I B are pairwise order-incompatible and we add that I D is also order-incompatible with each of them. This result is interesting as it shows that each inconsistency measure gives a particular insight on the inconsistency of a set of formulas.

I C -inconsistency measures for communication sets

In order to assign a degree of IC -inconsistency to a communication set, we adapt the inconsistency measures. I D , I C , I M , I p and I Q are typically syntax-based inconsistency measures in the sense they mainly take into consideration the formulas composing K . This aspect is quite important in our context. However we need to introduce an extra property that IC -inconsistency measures should satisfy. This property is named syntax weak-independence. It states that IC -inconsistency measures should not be dependent of the syntax of IC and that two weakly equivalent communication sets should have the same IC -inconsistency measure. In other words, the measure does not depend on the sources of the communication. Definition 3. Let IC and IC be two integrity constraint and and be two communication sets on A. Function I IC : 2 A×L → R + is a syntax weak-independent I C -inconsistency measure iff it satisfies the following properties:

• Consistency: I IC ( ) = 0 iff is IC -consistent. • Monotony: If ⊆ then I IC (ψ) ≤ I IC (ψ ). • Free formula independence: If φ ∈ F ree( ) then I IC ( ) = I IC ( \ {φ}).
• Syntax weak-independence:

1. for all IC if |= IC ↔ IC then I IC ( ) = I IC ( ).

for all if then I IC ( ) = I IC ( ).

According to this definition, the measure of IC -inconsistency of a communication set is null iff this communication set is not IC -inconsistent. The measure of IC -inconsistency of a communication set does not decrease if we add more communications. Removing a report which does not cause any contradiction does not change the IC -consistency measure of the communication set. Finally, the measure of IC -inconsistency of a communication set does not depend on the syntax on the integrity constraints and two weakly equivalent communication sets get the same measure of IC -inconsistency.

The different measures introduced for sets of formulas can now be redefined for communication sets as follows: IC are defined as follows:

• I D IC ( ) = 0 if is IC -consistent; 1 otherwise. • I C IC ( ) = | ⊥ IC|. • I M IC ( ) = (| IC| + |Self contradictions( )|) -1. • I P IC ( ) = |Problematic( )|. • I Q IC ( ) = 0 if is IC -consistent; K ∈ ⊥IC 1 |K | otherwise. • I B IC ( ) = min{|Conf lictbase(i)| | i |= 3 K ∈ K ∧ IC}.

Contribution of an agent to inconsistency

In this section, we aim at characterizing the contribution of an agent to the overall inconsistency of a communication set.

Contribution function

Evaluating the contribution of an agent to the overall inconsistency of a communication set should be relative to an inconsistency measure. As previously stressed, inconsistency measures provides different perspectives on inconsistency and the contribution of an agent may then differ w.r.t. some inconsistency measure. Several possible solutions are possible for assessing this contribution but, as for the inconsistency measure, some constraints should also be satisfied. At first, the contribution of an agent should be null if it does not contribute to any inconsistency. Second, an agent not involved in any inconsistency should not influence the assessment of the contribution of the other agents; finally contribution should be syntax independent. Syntax-weak independence is not relevant here as illustrated by the following example: suppose two sets and such that they are weakly equivalent; in that context, it may be the case that some agent a is problematic w.r.t. while it is not w.r.t.

. Hence their contribution should not be the same.

Definition 5. Consider a set of agents A, a communication set on A, an integrity constraint IC and an IC -inconsistency measure I IC . Function Cont ,I IC is a syntax independent contribution function if it associates to any agent a ∈ A a positive real number Cont ,I IC (a) so that:

• Consistency:

Cont ,I IC (a) = 0 iff a / ∈ Problematic( A). • Free agent independence: if b / ∈ Problematic( A) then Cont ,I IC (a) = Cont \{K (b)},I IC (a). • Syntax independence: 1. for all IC if |= IC ↔ IC then Cont ,I IC (a) = Cont ,I IC (a).

for all if

≡ then Cont ,I IC (a) = Cont ,I IC (a).

Assessing the contribution

Hereafter, we adapt two well known metrics in order to define the contribution of an agent to the communication set inconsistency, namely the Shapley value and the Banzhaf index. They are well known measures for assessing the power of an agent in a voting procedure. Our context is similar: Shapley value enables to asses the personal contribution of an agent to overall inconsistency of a communication base; in other words it measures the importance of this agent in a coalitional game defined by function I IC [START_REF] Hunter | On the measure of conflicts: Shapley inconsistency values[END_REF]. The Banzhaf index assesses the pivotal role of an agent in the definition of an inconsistent set. It corresponds to the Banzhaf score as shown in [START_REF] Hunter | Measuring inconsistency in multi-agent systems[END_REF]. Theses functions are respectively denoted Cont

Cont s (a) = C ⊆A C =∅ (|C| -1)!(| A| -|C|)! |A|! (I IC ( (C)) -I IC ( (C \ {a}))).
The following proposition connects the inconsistency measure and the contribution function. It states that if the inconsistency measure is syntax weak independent then the contribution function is syntax independent.

Proposition 2. Function Cont s is a syntax independent contribution function if I IC is a syntax-weak independent I C -inconsistency measure.

Let us now consider the Banzhaf based contribution: As for the Shapley value, function Cont b is syntax independent as long as the inconsistency measure is syntax weak independent. Proposition 3. Function Cont b is a syntax independent contribution function if I IC is a syntax-weak independent I C -inconsistency measure.

Implementation and complexity considerations 4.3.1. Implementation of Cont s

Algorithm 1 implements function Cont s . Its parameters are a communication set , an integrity constraint IC and a list of inconsistency measures I IC list. It shows that if we only consider inconsistency measures based on minimal inconsistent subsets, then the Shapley values for all the inconsistency measures can be computed without adding extra calls to a SAT solver. It is composed of two steps. First step (Line 3) is a call to Function InconsistencyMeasures (detailed in Algorithm 2) which computes, for each coalition of agents, the inconsistency measures requested in I IC list and stores the results in a tuple of arrays indexed by the coalition number. Second step (Lines 4 to 16) computes, for each agent, the Shapley values for each inconsistency measure by applying simple operations on the arrays computed at the previous step. Clearly, the second step is not computationally hard except that it contains an internal loop on each coalition which is exponential with respect to the number of agents. This second step is precisely in O (n * 2 n-1 /2), n being the number of agents and considering that each agent is involved in half of the possible coalitions. It doesn't require any call to a SAT solver.

Algorithm 2 is composed of a preparation step and an execution step. The preparation step (Lines 3 to 5) is executed only if inconsistency measures based on minimal inconsistent subsets are requested and computes the set of minimal inconsistent subsets for the coalition composed of the whole set of agents ( ⊥IC). Computing the set of minimal inconsistent subsets of a belief base is a hard problem which requires to use a SAT solver. It is shown in [START_REF] Papadimitriou | The complexity of facets resolved[END_REF][START_REF] Grégoire | Using local search to find MSSes and MUSes[END_REF] that this problem is DP-complete.

Cont I C IC s [ j] = Cont I C IC s [ j] + Ratio[i] * (I C IC [i] -I C IC [i -2 j ])
10: case I P IC [START_REF] Grant | Distance-based measures of inconsistency[END_REF]: Fortunately, algorithms such as those published in [START_REF] Grégoire | Using local search to find MSSes and MUSes[END_REF] make the computation of minimal inconsistent subsets feasible in real-life applications. The execution step (Lines 6 to 18) computes, for each coalition of agents, the requested inconsistency measures plus the ratio based on the coalition size. We use function MIC (detailed later) which allows to extract for any coalition of agents the corresponding set of minimal inconsistent subsets out of ⊥IC without any more call to a SAT solver.

Cont I P IC s [ j] = Cont I P IC s [ j] + Ratio[i] * (I P IC [i] -I P IC [i -2 j ]) 12: case I B IC 13: Cont I B IC s [ j] = Cont I B IC s [ j] + Ratio[i] * (I B IC [i] -I B IC [i -2 j ])
Ratio[i] = (|Ci |-1)!(n-|Ci |)! n!
Thanks to this result computing I C IC , I P IC or I Q IC is very easy at this level. On the other hand computing I B IC still requires to compute the three valued models of the current coalition, which is computationally hard. The execution sub-step is in O (2 n-1 ) and is not computationally hard if we only compute inconsistency measures based on minimal inconsistent subsets.

Note that in [START_REF] Grégoire | Using local search to find MSSes and MUSes[END_REF], the set of maximal consistent subsets is computed before producing the set of minimal inconsistent subsets. Consequently, inconsistency measure I M IC can also be computed without extra complexity. It is not the case for inconsistency measure

I B IC In summary, computing Cont s is C preparationstep + C execution step + C second step where C preparation step is DP-complete, C execution step is in O (2 n-1 ) and C second step is in O (n * 2 n-1 /2).
In [START_REF] Hunter | Measuring inconsistency through minimal inconsistent sets[END_REF] the authors show that in the specific case using inconsistency measure I C (K ), it is possible to compute the Shapley value in polynomial time. This result can directly be applied for computing Cont s using inconsistency measure I C IC .

Let us detail some hints used by Algorithm 1. Suppose there are n agents named 0, ...n -1. Then there are 2 n possible coalitions of agents we name 0, 1...2 n -1 with 0 being the empty coalition and 2 n -1 the whole set of agents. We introduce two functions BinString and Bit. BinString(i) returns a binary string corresponding to the binary representation of coalition i. Bit( j, BinString(i)) returns the bit of weight 2 j in BinString(i). Thus, agent j is involved in coalition i iff Bit( j, BinString(i)) = 1.

Let us now detail some hints used by Algorithm 2. Line 5 calls function Compute ⊥IC ( , IC ) which returns ⊥IC. As previously mentioned, this is DP-complete. One can notice that once ⊥IC is computed, we immediately get ⊥IC for any included in i.e removing the report of some agent from does not create new inconsistent subset. This remark allows us to drastically reduce the complexity for producing the minimal inconsistent subsets of each coalition. Line 9 is a call to function M IC(i, ⊥IC) which returns the set of minimal inconsistent subsets of which are made of reports emitted by agents in coalition i, that is {X | X ⊆ (Agents(i)) and X ∈ ⊥ IC} ( Agents(i) returns the agents involved in coalition i, i.e. agents whose bit is set to 1 in BinString(i)).

Implementation of Cont b

Algorithm 3 provides an implementation of function Cont b . It takes as parameter a communication set and an integrity constraint IC . This algorithm is similar to Algorithm 1 and has the same computational complexity. Again, most of the complexity is in the computation of the inconsistency measures for each possible coalition. However it is interesting to notice that the Banzhaf-based contribution uses only two inconsistency values, namely > 0 and = 0. Consequently, the drastic inconsistency measure, whose computation is the cheapest one, should be preferred to compute the Banzhaf-based contribution of the agents.

(I IC ) = InconsistencyMeasures( , IC, I IC ) 4:
for j = 0 to n -1 do for each agent 5:

for i = 1 to 2 n -1 do
for each coalition 6:

if Bit( j, BinString(i))=1 then 7:

if then(I IC [i] > 0 and I IC [i -2 j ] = 0) 8: Cont I IC b [ j] = Cont I IC b [ j] + 1

Assessing reliability

We now consider the question of assessing reliability. In the following, we represent reliability as a preorder over the set of agents and statement a ≤ b stands for b is at least as reliable as a. The following postulates axiomatically characterize any reliability preorder based on what the agents have reported in the context of a given integrity constraint.

Given a set of agents A, an integrity constraint IC and a communication set , the total preorder representing the relative reliability of agents in A is denoted ≤ A, IC . This preorder is characterized by the following postulates which show that reliability should be rooted in inconsistency:

P1 ≤ A, IC is a total preorder on A. P2 If ≡ then ≤ A, IC =≤ A, IC . P3 If |= IC ↔ IC then ≤ A, IC =≤ A, IC . P4 If a / ∈ Problematic( A) then ∀b, c ∈ A, if b ≤ A\{a}, \{K (a)} IC c then b ≤ A, IC c. P5 If is IC -consistent then ≤ A, IC is the equality preorder. P6 If is IC -inconsistent then ∀a ∈ Problematic( A), ∀b / ∈ Problematic( A), a < A, IC b. P7 If {a 1 , ..., a k } ∈ A ⊥ IC for k ≥ 2, then ∃i, j such that j = i, a i < A, IC a j .
Postulate P1 specifies that the reliability preorder is a total preorder. P2 and P3 deal with syntax independence. More precisely, if we consider two equivalent communication sets or if we consider two equivalent integrity constraints, then we get the same total preorder on agents. P4 states that reliability is assessed with respect to inconsistency: in other words, agents which do not cause inconsistency issues have no influence. A typical example is an agent which reports a tautology or which reports no information, then it should not have influence on the relative reliability of other agents. P5, P6 and P7 focus on consistency of information provided by agents in A. Postulate P5 considers the case when set is not IC -inconsistent. In such a case, the agents are considered as equally reliable. P6 and P7 consider the case where is IC -inconsistent. According to P6, any agent which is responsible of the IC inconsistency of is considered as strictly less reliable than any other agent which is not. According to P7, the agents of a minimal IC -inconsistent subset cannot be equally reliable: at least one of these agents is strictly less reliable than the others. This is coherent with the way we understand reliability: if some agents are equally reliable, then after merging we will believe, with the same strength, information they will provide. However, it is generally assumed [START_REF] Demolombe | A logic of graded trust and belief fusion[END_REF][START_REF] Laverny | From knowledge-based programs to graded belief-based programs, Part I: on-line reasoning[END_REF] that graded belief satisfies the modal logic axiom which states that belief should be consistent: that is, two contradictory pieces of information cannot be believed with the same strength. Consequently, agents who are involved in a minimal IC -inconsistent set cannot be equally reliable.

Building reliability from contribution

It is clear that the more an agent contributes to the overall inconsistency of a communication set, the less is should be reliable. That is, a source is considered strictly more (resp, equally) reliable than a second one iff its contribution to the global inconsistency is strictly smaller than (resp equal to) the contribution of the other. Notice that this principle only takes care of the first six postulates as shown by the following postulates. The following example illustrates that P7 does not hold. This example shows that a tie-breaking rule is missing: if all agents involved in the definition of a minimal inconsistent subset have an equal contribution then one of them should still be considered as less reliable. For voting rules, a classical way to handle tie-breaking is to consider an additional lexicographic order over the set of agents in order to always get a winner [START_REF] Andréka | Operators and laws for combining preference relations[END_REF]. In our context, the contribution function should prevent the cases where all agent involved in an inconsistent coalition have similar contribution. The following constraint translates this principle in formal terms: Definition 8. Let Cont be a syntax independent Contribution Function. Cont is said to be tie-free if it satisfies the following constraint:

∀C ∈ A⊥IC, ∃a, b ∈ C , s.t. Cont(a) = Cont(b).
The immediate question is "does such function exist?". To get the answer, let us revisit our Shapley and Banzhaf based contribution functions and built on top of them a tie-free function. The idea is similar tie-breaking: for any inconsistent set of agents, one agent contribution is slightly increased so that there is no more inconsistent set of agents where all agents have the same contribution. As we have no information about the agents involved in the communication set, the modified contribution may be chosen in an arbitrary way. Hereafter we just consider a lexicographic order for this choice (as in the voting rules).

Definition 9.

Let Cont be a Contribution function defined either by Definitions 6 and 7. Function Cont t is then defined as follows:

• If Problematic( A) = ∅ then Cont t = Cont.
• Otherwise, let be a positive real number which is strictly smaller than the smallest difference between two contributions: 0

< < min({Cont(a) -Cont(b) | Cont(a) Cont(b)}).
1. Let S tie be the set of agents with equal contribution t:

S tie = {a | ∃C ∈ A⊥IC such that |C| > 1 and a ∈ C and ∀x, y ∈ C , Cont(x) = Cont( y)}.
Let S be the minimal subset of S tie w.r.t. the lexicographic order such that (i

) ∀C ∈ A⊥IC , ∃a ∈ S ∩ C and (ii) ∀C ∈ A⊥IC , C \ S = ∅. Set Cont t (a) = Cont(a) + for any a ∈ S. 2. Cont t (b) = Cont(b) for any agent b / ∈ S.
The following proposition shows that this function is a tie-free one.

Proposition 4. Cont t is tie-free.

We have proved that there exist Contribution functions which are tie-free, we can rephrase the previous theorem so that P7 holds. This second theorem shows at first that there exists a reliability preorder which satisfy all the postulates. Second, it shows that one of the key issue in the inconsistency definition of reliability is Postulate P7. It forces to rank the agents involved in a minimal IC -inconsistent subset. We propose to handle this issue by constraining the contribution function. Remind that all agents are unknown and we do not have extra information for setting the choice. Hence this function may lead to arbitrary choices. However, even if we do not know any extra information, we have seen that we can build up a reliability preorder by first assessing the overall inconsistency of a communication set; secondly by computing the "responsibility" degree or contribution of each agent in the overall inconsistency and thirdly by rooting the reliability of the agents into their contributions.

Theorem 2. Given a set of agents A, an integrity constraint I C and a communication set , the reliability preorder

Reliability aggregation

In the previous section, we have shown that assessing reliability of agents may be achieved by choosing a particular inconsistency measure and a particular contribution function, each specific pair measure,contribution assessing the sources in a different way. The choice of a specific pair is a challenge since we have no information about the sources. A solution may be to assess reliability with respect to several pairs and to merge all the resulting preorders to obtain a "consolidated" one. The immediate question is then: if each of the reliability preorders satisfies postulates P1-P7, can we then obtain an aggregated preorder which also satisfies these postulates? The aim of this section is to tackle this issue.

This problem is clearly connected to the field of preferences aggregation. Arrow impossibility theorem [START_REF] Arrow | Social Choice and Individual Values[END_REF] states that it is not possible to aggregate preferences while guaranteeing Universality, Non-Dictatorship, Unanimity and Independence to Irrelevant Alternatives. The question is then to evaluate how Arrow's conditions interplay with the reliability postulates.

Arrow's conditions

In the following, we first define our aggregation operator and next revisit the Arrow's conditions. Let ⊕ be our aggregation operator defined as follows: Definition 10. A n-ary reliability aggregation operator ⊕ is a function which associates n total preorders on A, respectively ≤ 1 , ..., ≤ n , with a total preorder on A denoted ≤ ⊕ .

Next, we rephrase the classical Arrow's conditions: Definition 11. Let ⊕ be a n-ary reliability aggregation operator. We consider the following properties: Universality the domain of ⊕ is the set of all possible n-tuple of reliability total preorders. Non-dictatorship i ∈ {1...n} such that ∀ ≤ 1 ... ≤ n total preorders on A, ≤ ⊕ =≤ i . Unanimity Let a ∈ A and b ∈ A. If ∀i ∈ {1...n} a ≤ i b then a ≤ ⊕ b. Independence of irrelevant alternatives (IIA) Let a and b be two agents. Let (≤ 1 , ..., ≤ n ) and (≤ 1 , ..., ≤ n ) be two sets of n total preorders. If ∀i ∈ {1...n}, (a

≤ i b ⇔ a ≤ i b) then (a ≤ ⊕ b ⇔ a ≤ ⊕ b).

Influence of arrow's conditions

The following propositions exhibit the interplay between Arrow's conditions and the seven postulates characterizing the consistency-based reliability assessment. Namely, assuming that each ≤ i satisfies our postulates, which Arrow's condition(s) are required so that the postulates are also satisfied by the resulting preorder. Propositions 5 to 11 all use the following elements: let be a communication set on A and IC an integrity constraint; let I i IC (i = 1...n) be n syntax weak-independent IC -inconsistency measures. For the sake of conciseness, ≤ i (i = 1...n) stands for ≤ A, IC ith reliability preorder.

Proposition 5 (P1 ⊕ ). If ⊕ satisfies the condition of Universality then

If all ≤ i satisfies P1, then ≤ ⊕ satisfies P1 (i.e., ≤ ⊕ is a total preorder).

This proposition states that if the input is itself a tuple of total preorders Universality will guarantee that the aggregation operator ⊕ will return a total preorder.

Proposition 6 (P2 ⊕ ). If all ≤ i satisfy P2 then ≤ ⊕ satisfies P2 (i.e., if ≡ then ≤ ⊕ =≤ ⊕ ).
|= IC ↔ IC , ≤ ⊕ =≤ ⊕ ).
This proposition is a consequence of Postulate P3: if each ≤ i is syntax independent w.r.t. some integrity constraint then the resulting preorder is also syntax independent. Notice that the last two propositions do not involve any Arrow conditions as opposed to the other ones.

Proposition 8 (P4 ⊕ ). If ⊕ satisfies the condition of Independence of Irrelevant Alternatives then

If all ≤ i satisfy P4 then ≤ ⊕ satisfies P4 (i.e., if ≤ -a denotes the preorder ≤

A\{a}, \K (a) IC , if a / ∈ Problematic( A), then ∀b, c ∈ A, if b ≤ -a ⊕ c then b ≤ ⊕ c).
This proposition states that P4 (no influence of agent a who only reports tautologies) can only be preserved if IIA holds. That is, if all preorders are unchanged after excluding agent a, then aggregation also produces a similar result if IIA also holds.

Proposition 9 (P5 ⊕ ). If ⊕ satisfies the condition of Unanimity then

If all ≤ i satisfy P5 then ≤ ⊕ satisfies P5 (i.e., if is I C -consistent then ≤ ⊕ is the equality preorder).

Postulate P5 states that consistency leads to a flat ordering. Consequently, if there is no conflict among agents, every ≤ i has to be flat and the aggregation produces a flat order as long as Unanimity holds for the operator ⊕.

Proposition 10 (P6 ⊕ ). If ⊕ satisfies the condition of Unanimity then

If all ≤ i satisfy P6 then ≤ ⊕ satisfies P6 (i.e., if is I C -inconsistent then ∀a ∈ Problematic( A), ∀b / ∈ Problematic( A), a < ⊕ b).

Proposition 10 stresses up a second time the key role of Unanimity condition. If Postulate P6 holds for every ≤ i then preorders ≤ i unanimously states that for any a ∈ Problematic( A) and b ∈ A \ Problematic( A), b is more reliable than a. a < ⊕ b also holds only if Unanimity holds.

Proposition 11 (P7 ⊕ ). If ⊕ does not satisfy the condition of Non-dictatorship then

If all ≤ i satisfy P7 then ≤ ⊕ satisfies P7 (i.e., if {a 1 , ..., a k } ∈ A ⊥ IC for k ≥ 2, then ∃i, j such that j = i and a i < ⊕ a j ).

This proposition shows the role of the Non-dictatorship condition. Postulate P7 states that at least one agent involved in a conflicting set of agents should be ranked with a lower reliability. If each ≤ i have decreased the reliability of a different agent then, if the Non-dictatorship property holds, no agent will be decreased by the aggregation procedure ⊕. Hence, the constraint enforces by P7 will hold only if the Non-dictatorship property is not satisfied, i.e. there is a dictator.

To sum up, as shown by Table 1 four Arrow's conditions have an influence on the fulfillment of the postulates. Notice that these conditions are sufficient conditions for satisfying the postulates.

With the help of Table 1, we are fully informed on what postulates or Arrow's conditions one should give up during the definition of an aggregation operator. The table shows that reliability aggregation is different from preference aggregation: the postulate are not compatible with Arrow's conditions. It also means that some underlying priority should be considered in the definition of the operator: if we give priority to the fulfillment of the postulates then fulfillment of Arrow's conditions is not that important. In the next section, we illustrate this issue by considering a simple aggregation procedure satisfying all the postulates but abandoning one Arrow's condition.

Lexicographic-based aggregation

The proposed aggregation procedure is a lexicographic procedure [START_REF] Gaertner | A Primer in Social Choice Theory[END_REF], widely used in preference aggregation and belief merging. In [START_REF] Andréka | Operators and laws for combining preference relations[END_REF], the authors show how preference relations can be aggregated. First consider a hierarchy among n preorders (with no loose of generality, ≤ 1 is the most important while ≤ n is the least important). According to this hierarchy, if all k first preorders state a = k b and at k + 1, a < k+1 b then a will be considered as less reliable than b in the resulting preorder. No divergence entails that a and b are considered as equal in the resulting preorder. Let ⊕ L denote the reliability aggregation operator defined as follows: Definition 12. If ≤ 1 , ... ≤ n are n reliability preorders on a set of agents A and if ≤ L denotes the preorder ⊕ L (≤ 1 ... ≤ n ), then ≤ L is defined by:

• a < L b iff ∃k = 1...n ∀ j ∈ {1...k -1} a = j b and a < k b. • a = L b else.

Example 5. Assume following total preorders defined over the set of agents

A = {a, b, c, d, e}. a = 1 b < 1 c < 1 d = 1 e. a < 2 b = 2 c < 2 d = 2 e. e = 3 b < c = 3 d = 3 a.
We obtain the following aggregated preorder a < L b L c < L e < L d. For instance, a < L b holds because a = 1 b and a < 2 b.

It is well known that among the four Arrow's conditions, Non-dictatorship does not hold for Lexicographic aggregation (see [START_REF] Andréka | Operators and laws for combining preference relations[END_REF]). I.e., It means that this reliability aggregation operator is a good candidate to aggregate reliability preorders as long as these individual preorders also satisfy P1-P7. Example 6. Consider agent a whose aim is to assess the relative reliability of three communicating agents b, c and d. With the specific pair < measure, contribution > it chose, a gets the preorder: b ≺ s c = s d, i.e., b has to be considered as strictly less reliable than c and d who have to be considered as equally reliable. Assume that before applying this method, a had an a priori about the three agents and thought that d was more reliable than the two others which were equally reliable, i.e., b = a c ≺ a d (where ≺ a denotes the a priori preorder). This a priori information can be used by a to decide weather c or d is the least reliable. More precisely, by aggregating the two preorders and by giving priority to ≺ s , a gets: b ≺ L c ≺ L d.

Avoiding dictatorship condition

If we want to consider each inconsistency measure in an equal way, we should avoid the dictatorship condition and instead go towards voting rules for the definition of a non-dictator reliability aggregation operator. An immediate consequence is that postulate P7 will not be satisfied in the aggregated preorder. Another consequence is that Arrow's theorem forces us to give up an other condition since we want the non-dictatorship condition to be satisfied. It means that some other postulates will also have to be abandoned depending on the condition that will be given up (IIA or Unanimity).

Let us consider the classical preferential voting rules such as Condorcet, Borda and Copeland [START_REF] Fishburn | The Theory of Social Choice[END_REF], which enforce the non-dictatorship condition. All these rules usually consider strict and total preorders as input and provide a preorder as output. In our context, we have to consider a variant where input is a set of preorders that may not be strict. We also consider that the aggregation method should take into account the relative position of each agent (w.r.t. other agents) in all preorders: agent a may be poorly ranked according to some inconsistency measure while it may obtain a good rank according to some other inconsistency measure. Hence the rank of an agent should be balanced by its position in the overall preorder. It means that a counting based procedure is more adapted than a pairwise comparison method, which argues for a Borda based aggregation procedure instead of an aggregation procedure based on Condorcet or Copeland.

The rule proposed hereafter rephrases the Borda-based rule initially proposed in [START_REF] Fishburn | The Theory of Social Choice[END_REF]Chapter 13] which handles total preorders (that may be strict). As mentioned, we want to take into account the relative position in the preorder (''good" or ''poor" position). Consequently, for any agent a and preorder ≤ i , the rule computes a score which takes into account its relative position w.r.t. the median agent associated to preorder ≤ i .

Let us detail the computation of the score of agent a, w.r.t. ≤ i . Set of agent A is first partitioned w.r.t. ≤ i such that in each partition all agents are equally reliable; let t be the number of partitions. The partitions are ranked w.r.t. ≤ i such that P 1 is the partition containing the most reliable agents and P t contains the less reliable agent. Let m be the median agent; the score of each agent is set according to its relative position with m w.r.t. the partitions. w.r.t. some preorder ≤: score(a, ≤) = (kj) iff a ∈ P j and m ∈ P k .

The median agent m receives a score equal to zero, while each agent strictly more reliable than m gets a positive score and agents strictly less reliable than m receive a negative score.

Notice, that the score also gives privileges to preorders which are informative (i.e. discriminating agents), that is if the number of partitions is large then the range of the score is also large.

{a, b} < 1 {c} < 1 {d, e} [1 0 -1] {a} < 2 {b, c} < 2 {d, e} [1 0 -1] {e, b} < 3 {c, d, a} [ 1 0]
We get the following scores:

score(a) = 2, score(b) = 2, score(c) = 0, score(d) = -2, score(e) = -1.
We then obtain the following aggregating preorder a = B b < B c < B e < B d. The key difference with the previous ranking is the equal rank for a and b: as they are both rank first twice in this example, the absence of dictator entails to not distinguish them.

We remind that among the four Arrow's conditions, IIA does not hold for Borda aggregation. As shown by the corollary, the main consequence is that even if all individual preorders satisfy Postulates P1-P7, the properties corresponding to P4 and P7 do not hold in the resulting preorder. For postulate P4, it means that an agent only reporting tautologies may influence the output, i.e. the overall reliability. Second, for postulate P7, it means that agents involved in some minimal IC -inconsistent subset may not be discriminated with the aggregated reliability ranking while they are supposed.

Conclusion

This work proposes to assess the relative reliability of some agents by analyzing the inconsistency of information they report w.r.t some trusted knowledge. We have defined postulates stating what the relative reliability preorder should be. Then we have shown through two representation theorems how such preorders are related to the contribution of each agent to the overall inconsistency of a communication set. Implementation and complexity questions have also been considered. Finally, we have shown how aggregating reliability preorders is constrained by Arrow's impossibility theorem.

This framework may be extended in several ways. First, inconsistency measures should deserve more attention. Recent work on this topic [START_REF] Grant | Distance-based measures of inconsistency[END_REF][START_REF] Besnard | Revisiting postulates for inconsistency measures[END_REF] shows promising results such as giving a weight to the inconsistency itself. A second issue concerns our key principle for reliability assessment which only considers inconsistency: the more an agent is connected to inconsistency, the less it is reliable. We could extend this principle by considering not only conflicts between agents but also agreement [START_REF] Qi | Measuring conflict and agreement between two prioritized knowledge bases in possibilistic logic[END_REF]. We could also extend it by considering that an agent producing more information than others should be rewarded. The problem here will be how to quantify the amount of information produced by an agent which is not contradicted. To this end some information measures have already been proposed in [START_REF] Grant | Measuring the good and the bad in inconsistent information[END_REF]. The main question will be to revise the postulates to take into account these extensions. The third issue concerns the one shot dimension of the assessment process: iteration should be possible and reliability assessment should then be viewed as a refinement process. Consequently, Cont b is syntax independent.

Appendix A. Proofs Proof of Proposition 1. First, if |= IC ↔ IC then ⊥ IC = ⊥ IC , IC = IC and i |= 3 K ∈ K ∧ IC iff i |= 3 K ∈ K ∧ IC . Secondly, if then | ⊥ IC |=| ⊥ IC |, | IC |=| IC | and i |= 3 K ∈ K ∧ IC iff i |= 3 K ∈ K ∧ IC . Proof of Proposition 2. Consistency. Assume a / ∈ Problematic( A), then K (a) ∈ F ree( ). Then ∀C I IC ( (C)) = I IC ( (C \ {a})) since I I C satisfies Free formula Independence. This proves that if a / ∈ Problematic( A) then Cont s (a) = 0. Assume a ∈ Problematic( A): if K (a) ∈ Problematic( ) then ∃M ∈ ⊥ IC K (a) ∈ M. Let's write M = {K (a), K (b 1 ), ... K (b k )}. Then ({a, b 1 , ...b k }) is IC -inconsistent while ({b 1 , ...b k }) is IC -consistent. Consequently, I IC ( ({a, b 1 , ...b k })) > I IC ( ({b 1 , ...b k })) =
/ ∈ Problematic( A) then Cont b (a) = 0. Assume a ∈ Problematic( A): if K (a) ∈ Problematic( ) then ∃M ∈ ⊥ IC K (a) ∈ M. Let's write M = {K (a), K (b 1 ), ... K (b k )}. Then ({a, b 1 , ...b k }) is IC -inconsistent while ({b 1 , ...b k }) is IC -consistent. Consequently, I IC ( ({a, b 1 , ...b k })) > I IC ( ({b 1 , ...b k })) =

A.1. Theorems about reliability preorders

Proof of Theorem 1. Let us first prove that Postulates P1-P6 hold. In the following, whenever it's clear ≤ denotes the reliability preorder instead of full notation ≤ A, IC .

• Function Cont outputs numerical values and thus preorder ≤ is total P1 is satisfied.

• If ≡ , then ∀C ⊆ A (C) ≡ (C). As Cont satisfies syntax independence, then, ∀x ∈ A Cont ,I IC (x) = Cont ,I IC (x).
Thus, P2 holds.

• If |= IC ↔ IC then, because Cont is syntax independent, ∀a ⊆ A, Cont ,I IC (a) = Cont ,I IC (a). Consequently, P3 holds. • Assume a is not problematic: K (a) ∈ F ree( ). Next function Cont is free agent independent, ∀x, y ∈ A Cont ,I IC (x) = Cont \{K (a)},I IC (x) and Cont ,I IC (y) = Cont \{K (a)},I IC (y). Then, if x ≤
A\{a}, \{K (a)} IC y then it must be the case that x ≤ y. This shows that P4 is satisfied by ≤.

• If is IC -consistent, then by consistency property, ∀x ∈ A, Cont(x) = 0 and then ∀x, y ∈ A, x = y. This shows that P5 is satisfied.

• Suppose is IC -inconsistent. Let a be in A.

-Assume a / ∈ Problematic( A). Then by consistency property for Function Cont, Cont(a) = 0. -Assume a ∈ Problematic( A). Then by consistency property for Function Cont, Cont(a) > 0.

This shows that P6 holds.

Let us focus on the other direction: assume a preorder ≤ A, IC , or ≤ for short such that P1-P6 hold. Next, we build a Function Cont as following: we partition the set of agents w.r.t. preorder ≤ as follows:

• A 0 = min( A, ≤) • A i = min( A -∪ 0 j<i A j , ≤) for any i > 0.
Notice, that as A is finite, then the number of partitions is also finite. Assume there are N partitions and then A 0 the less reliable agents while A N-1 contains the most reliable ones. For any agent a

∈ A k , Cont(a) = N -k -1.
Due to postulate P1, the immediate consequence of this definition is that for any agents a and b:

If a ≤ A, IC b then Cont(a) Cont(b)
Hence, the first requirement stating that for any agent a, Cont provides a positive real number is fulfilled. Let us now check that Function Cont is actually syntax independent.

First we check that Cont is consistent. Postulate P5 entails that there is a unique partition A 0 = A and consequently Cont(a) = 0 for all agent a. Assume now, that some agents are problematic. Then there is at least 2 partitions: suppose there are N > 1 partitions. Due to postulate P6, only agents a such that a / ∈ Problematic( A) belong to A N-1 . Hence, for all agents a / ∈ Problematic( A), it holds that Cont(a) = 0 and P6 also enforces that for all agents a ∈ Problematic( A), Cont(a) > 0. Then we check that Cont is free agent independent. Assume a such a / ∈ Problematic( A). Suppose that A is partitioned in N partitions. P6 entails that a belongs to A N-1 . Due to postulate P4, we get that the partition of A -{a} w.r. If the communication set is inconsistent then we have two cases: either S tie is empty or not. If S tie is empty then tie-free holds. Now suppose that S tie is not empty. Let S be the minimal subset of S tie w.r.t. the lexicographic order such that (i) ∀C ∈ A⊥IC , ∃a ∈ S ∩ C and (ii) ∀C ∈ A⊥IC , C \ S = ∅. Let us first show that such S exists. Assume it is not the case, then it entails that either condition (i) or (ii) does not hold. Suppose (i) holds but not (ii). Hence, it means there exists a coalition C such that there is no agent a which belongs to C \ S. Hence C = S, and S is then not minimal. Contradiction. Other cases can be considered in a similar way. Consequently, the definition of Cont t entails that for every coalition C where agents have an equal contribution: (i) one agent has its contribution increased as it belongs to S and C and (ii) one agent has its contribution unchanged as it belongs to C \ S. Next the second step guarantees that the contribution is not increased for all other members of the set. Hence, it means that in each minimal IC-inconsistent subset of agents, there is always two agents which have unequal contribution, i.e., the constraint of tie-free contribution function holds.

Proof of Theorem 2. We only focus on Postulate P7 as the proof for the other postulates is similar to the proof of Theorem 1.

Let us first prove that the postulate is satisfied: suppose that {a 1 , ..., a k } ∈ A ⊥ IC for k ≥ 2, then as Cont is tie-free, it entails ∃i, j, such Cont(a i ) = Cont(a j ). Then by definition of < A, IC , a i < A, IC a j or a j < A, IC a i holds and P7 holds. Now consider the other direction. Assume that we built up a function Cont similar to the one considered in the proof of Theorem 1. Due to P7, for any inconsistent coalition C such that |C| > 1, there always exist a, b ∈ C such that a < b. Hence, it means that there is no partition A i such that all agents of an inconsistent coalition belong to A i . Consequently, for any inconsistent coalition C ∈ A⊥IC , its members belong at least to two partitions. Then it means that there is no C ∈ A⊥IC such that |C| > 1 where ∀a, b ∈ C , Cont(a) = Cont(b). Consequently Cont satisfies the tie-free constraint.

A.2. Propositions on arrow's conditions and postulates

We do not detail the proofs of Propositions 6 and 7, they are obvious.

Proof of Proposition 5. Operator ⊕ is defined as an operator with n total preorders as input. Postulate P1 guarantees that each ≤ i is total. Second, Universality entails that all possible input ≤ i • • • ≤ n will give an output. Definition of ⊕ states that this output is a total preorder.

Proof of Proposition 8. Let a be such that |= K (a). If every ≤ i satisfies P4, then for any x and y in A if (x ≤ -a i y) then (x ≤ i y). Consequently, for any x and y in A, (x ≤ i y) ⇐⇒ (x ≤ -a i y). Thus, if ≤ ⊕ satisfies Independence of Irrelevant Alternatives, then it holds that (x ≤ ⊕ y) ⇐⇒ (x ≤ -a ⊕ y). Thus, for any x and y in A if (x ≤ -a i y) then (x ≤ i y), i.e., ≤ ⊕ is compatible with ≤ -a ⊕ .

Proof of Proposition 9. Suppose that A is not IC -conflicting. Now assume that P5 holds for all ≤ i . Then ∀i = 1..n, ≤ i is the equality preorder. Unanimity states that for all a, b ∈ A, if ∀i ∈ {1...n} a ≤ i b then a ≤ ⊕ b. Consequently, if Unanimity holds then ≤ ⊕ is the equality preorder and P5 holds for ≤ ⊕ .

Proof of Proposition 10. Let a ∈ Problematic( A). Assume P6 holds for all ≤ i . That is ∀i ∈ {1...n} and ∀a ∈ Problematic( A), ∀b / ∈ Problematic( A), a < A, IC b. If Unanimity holds then, it entails that a < ⊕ b as a ≤ i b ∀i ∈ {1...n}. Consequently P6 holds for ≤ ⊕ .

Proof of Proposition 11. If ⊕ does not satisfy the property of Non-dictatorship then ∃i 0 ∈ {1...n} such that ∀ ≤ 1 ... ≤ n total preorders on A, ⊕(≤ 1 , ..., ≤ n ) =≤ i 0 . Assume preorder ≤ i 0 satisfies P7 and suppose {a 1 ...a k } ∈ A ⊥ IC . Consequently, ∃ j, j ∈ {1 . . . k} such that j = j and a j < i 0 a j . Hence, as ⊕(≤ 1 , ..., ≤ n ) =≤ i 0 , it also holds that a j < ⊕ a j . Consequently P7 holds for ≤ ⊕ .

Definition 4 .

 4 Let be a communication set and IC an integrity constraint. The IC -inconsistency measures I D IC , I C IC , I M IC , I P IC , I Q IC and I B

  IC are syntax weak-independent inconsistency measures. (All proofs are detailed in the appendix section, before references) I D IC ( ) is still a trivial measure, while each other measure gives insight on the contribution of reports to inconsistency. I C IC ( ) counts the number of minimal IC -inconsistent subsets of reports. I M IC ( ) counts the number of the maximal IC -consistent subsets of reports together with the number of self contradictory reports but 1 to make I M IC ( ) = 0 when is IC -consistent. I P IC ( ) counts the number of problematic reports. I Q IC ( ) adds the inverse of the sizes of the minimal IC -inconsistent subsets of reports, so that smaller IC -inconsistent subsets of reports are regarded as more inconsistent than larger ones. I B IC ( ) returns the minimum number of propositional symbols that have to be set to value B in order to get a three valued model of ∪ IC .

Definition 6 .

 6 it's clear, we denote them Cont s and Cont b for short. The Shapley based contribution function is defined as follows. Consider a set of agents A, a communication set on A, an integrity constraint IC and an IC -inconsistency measure I IC . Function Cont s associates any agent a with a positive real number Cont s (a) so that:

Definition 7 .

 7 Consider a set of agents A, a communication set on A, an integrity constraint IC and an IC -inconsistency measure I IC . Function Cont b associates any agent a with a positive real number Cont b (a) so that: Cont b (a) =| {C : I IC ( (C ∪ {a})) = 0 and I IC ( (C)) = 0} | .

Algorithm 3

 3 Contribution function Cont b . 1: function Cont b ( , IC, I IC )

Theorem 1 .

 1 Given a set of agents A, an integrity constraint I C and a communication set , the reliability preorder ≤ A, IC satisfies P1-P6 iff there exists a syntax independent Contribution Function Cont such that for any two agents a and b: a ≤ A, IC b iff Cont(a) Cont(b).

Example 3 .

 3 Consider= {< a, p >, < b, ¬p >, < c, q >} and IC = . Then {a, b} is a minimal IC -conflicting set of agents but Shapley-based Contribution Function gives: Cont ,I IC s (a) = Cont ,I IC s (b) and consequently a = b which violates P7.

  ≤ A, IC satisfies P1-P7 iff there exists a syntax independent Contribution Function Cont which is tie-free such that for any two agents a and b: a ≤ A, IC b iff Cont(a) Cont(b).

Example 4 .

 4 Take again A = {a, b} and K (a) = p, K (b) = ¬p and IC = . {a, b} ∈ A ⊥ IC and, according to the Shapley based Contribution function, it holds that Cont s (a) = Cont s (b). Let us consider the tie-free Contribution function based on Cont s . According to the lexicographic agent a then, Cont t (a) > Cont t (b) and we get: a < b.

Theorem 3 .Corollary 1 .

 31 [START_REF] Gaertner | A Primer in Social Choice Theory[END_REF] ⊕ L satisfies Universality, Unanimity, Independence of Irrelevant Alternatives and does not satisfy Non-dictatorship. If all preorders < i satisfy Postulates P1-P7, then Preorder < L also satisfies Postulates P1-P7.

Definition 13 .Example 7 .

 137 If ≤ 1 , ... ≤ n are n reliability preorders on a set of agents A and if ≤ B denotes the preorder ⊕B (≤ 1 ... ≤ n ), then ≤ B is defined by: a ≤ B b ⇐⇒ n i=1 score(a, ≤ i ) ≤ n i=1 score(b, ≤ i ).Let us revisit the previous example Assume the following total preorders defined over the set of agents A = {a, b, c, d, e}. We present the partition and the associated score

Theorem 4 .Corollary 2 .

 42 [START_REF] Gaertner | A Primer in Social Choice Theory[END_REF] ⊕ B satisfies Universality, Unanimity, Non-dictatorship and does not satisfy Independence of Irrelevant Alternatives. If all preorders < i satisfy Postulates P1-P7, then preorder < B only satisfies Postulates P1-P3 and P5-P6.

  0 as I IC satisfies the Consistency property and is monotonic. Thus Cont s (a) = 0. This proves that if Cont s (a) = 0, then a / ∈ Problematic( A). Free agent independence. Assume b / ∈ Problematic( A). Then, ∀C ⊆ A, I IC ( (C)) = I IC ( (C \ {b})) since I I C satisfies Free formula Independence. Hence for any agent a, I IC ( (C)) -I IC ( (C \ {a})) = I IC ( (C \ {b})) -I IC ( (C \ {b} \ {a})). Consequently Cont ,I IC s (a) = Cont -{K (b)},I IC s (a).

  Syntax independence. Assume IC such that |= IC ↔ IC . Then ∀C , I IC ( (C)) = I IC ( (C)) since I I C satisfies the syntax weak independence property. Hence for any agent a, I IC ( (C)) -I IC ( (C \ {a})) = I IC ( (C)) -I IC ( (C \ {a})). Consequently Cont

Assume

≡

  . Then ∀C (C) ≡ (C). Thus ∀C (C) (C). Since I I C satisfies the syntax weak independence property, this implies that ∀C I IC ( (C)) = I IC ( (C)). Hence for any agent a, I IC ( (C))-I IC ( (C \ {a})) = I IC ( (C)) -I IC ( (C \ {a})). Then Cont ,I IC s (a) = Cont },I IC s (a).Hence Cont s is a syntax independent contribution function.Proof of Proposition 3. The proof is similar to the proof of Proposition 2.Consistency. Assume a /∈ Problematic( A), then K (a) ∈ F ree( ). Then ∀C I IC ( (C)) = I IC ( (C \ {a})) since I I C satisfies Free formula Independence. Hence there is no C where a is pivotal. This proves that if a

  0 as I IC satisfies the Consistency and Monotonicity property. Thus Cont b (a) = 0 as a is pivotal for coalition C = {b 1 , ...b k }. This proves that if Cont b (a) = 0, then a / ∈ Problematic( A). Free agent independence. Let b / ∈ Problematic( A). Then ∀C I IC ( (C)) = I IC ( (C \ {b})) since I I C satisfies Free formula Independence. Hence for any agent a, I IC ( (C)) = I IC ( (C \ {a})) and I IC ( (C \ {b})) = I IC ( (C \ {b} \ {a})). Consequently Cont ,I IC b (a) = Cont -{K (b)},I IC b (a). Syntax-weak independence. Syntax independence. Let IC be such that |= IC ↔ IC . Then ∀C I IC ( (C)) = I IC ( (C)) since I I C satisfies the syntax weak independence property. Hence for any agent a, I IC ( (C)) = I IC ( (C)) and I IC ( (C \ {a})) = I IC ( (C \ {a})). Consequently Cont Assume ≡ . Then ∀C, (C) ≡ (C), thus ∀C, (C) (C), thus ∀C, I IC ( (C)) = I IC ( (C)) since I I C satisfies the syntax weak independence property. Hence for any agent a, I IC ( (C)) = I IC ( (C)) and I IC ( (C \ {a})) = I IC ( (C \ {a})).

  t. ≤ A-{a}, -K (a) IC is equal to the partition of A w.r.t. ≤ A, IC except for A N-1 which does not contain a. Hence for every other agent b = a, we get that Cont ,I IC (b) = Cont -{K (b)},I IC (b) and thus Cont is free agent independent. Finally, we check that Cont is syntax independent. Assume IC such that |= IC ↔ IC . Then P3 entails that preorders ≤ A, IC and ≤ A, IC are identical. Then partitions will be the same and consequently, for any agent a, Cont ,I IC (a) = Cont ,I IC (a). In a similar way, assume such that ≡ . P2 entails that preorders ≤ A, IC and ≤ A, IC are identical. Then partitions will be the same and consequently, for any agent a, Cont ,I IC (a) = Cont ,I IC (a). Proof of Proposition 4. If the communication set is consistent then A ⊥ IC = ∅ thus the constraint of tie-free contribution function holds.

Algorithm 1

 1 Contribution function Cont s . Cont s ( , IC, I IC list)

	2:	n = | |
	3: 4:	(I C IC , I P IC , I B IC , Ratio) = InconsistencyMeasures( , IC, I IC list) for j = 0 to n -1 do	for each agent
	5:	for i = 1 to 2 n -1 do	for each coalition
	6:	if Bit( j, BinString(i))=1 then
	7:	switch I IC list do
	8:	case I C IC
	9:

1: function

  IC, I IC list)

	14:	end if
	15:	end for
	16: 17:	end for return (Cont	I C IC s , Cont	I P IC s , Cont	I B IC s )
	18: end function
	Algorithm 2 Computing inconsistency measures for each coalition.
	2:	n = | |
	3: 4:	switch I IC list do case I C IC or I P IC or I	Q IC
	5:
						for each coalition
	7: 8:	switch I IC list do case I C IC or I P IC or I	Q IC
	9:
	10:	switch I IC list do
	11: 12:	case I C IC I C IC [i] = |M I[i]|
	13: 14:	case I P IC I P IC [i] = Compute I P (M I[i])
	15: 16:	case I B IC I B

1: function InconsistencyMeasures( , ⊥IC = Compute ⊥IC ( , IC) 6:

for i = 0 to 2 n -1 do M I[i] = M IC(i, ⊥IC) IC [i] = Compute I B (C i ) 17:

Table 1

 1 Interplay between postulates and Arrow's conditions. Proposition 7 (P3 ⊕ ). If all ≤ i satisfy P3 then ≤ ⊕ satisfies P3 (i.e., for any IC s.t.

	Sufficient conditions	Satisfied postulates
	Universality	{P1}
	Dictatorship	{P7}
	Unanimity	{P5, P6}
	IIA	{P4}
	This proposition is an immediate consequence of Postulate P2: if each reliability assessment operator is syntax indepen-
	dent (w.r..t. communication set) then the resulting preorder is also syntax independent.

This term corresponds to the term "knowledge base", widely used in the community of belief merging.

Acknowledgements

We sincerely thank the anonymous reviewers whose questions and comments helped us to improve this paper. This work has been granted by ONERA and by IRIT. Laurent Perrussel is partially supported by ANR-11-LABX-0040-CIMI within the program ANR-11-IDEX-0002-02. We also deeply thank Zakia Mallouk who implemented a great part of the ideas presented in this paper.