When combining beliefs from different sources, often not only new knowledge but also conflicts arise. In this paper, we investigate how we can measure the disagreement among sources. We start our investigation with disagreement measures that can be induced from inconsistency measures in an automated way. After discussing some problems with this approach, we propose a new measure that is inspired by the -inconsistency measure. Roughly speaking, it measures how well we can satisfy all sources simultaneously. We show that the new measure satisfies desirable properties, scales well with respect to the number of sources and illustrate its applicability in inconsistency-tolerant reasoning.
One challenge in logical reasoning are conflicts between given pieces of information.
Therefore, a considerable amount of work has been devoted to repairing inconsistent
knowledge bases [
Here, we are interested in belief profiles ( 1; : : : ; n) rather than single knowledge
bases . Intuitively, we can think of each i as the set of beliefs of an agent. Our goal
is then to measure the disagreement among the agents. A natural idea is to reduce
measuring disagreement to measuring inconsistency by transforming multiple knowledge
bases to a single base using multiset union or conjunction. However, both approaches
have some flaws as we will discuss in the following. This observation is similar to the
insight that merging belief profiles should be guided by other principles than
repairing single knowledge bases [
After explaining the necessary basics in Section 2, we will discuss the
relationship between inconsistency measures and disagreement measures in Section 3. To
begin with, we will define disagreement measures as functions with two basic properties
that seem quite indisputable. We will then show that disagreement measures induced
from inconsistency measures by taking the multiset union or conjunction satisfy these
basic desiderata and give us some additional guarantees. In Section 4, we will
propose some stronger principles for measuring disagreement. One key idea is to allow
resolving conflicts by majority decisions. We will show that many measures that are
induced from inconsistency measures must necessarily violate some of these principles.
In Section 5, we will then introduce a new disagreement measure that is inspired by the
-inconsistency measure from [
Basics We consider a propositional logical language L built up over a finite set A of propositional atoms using the usual connectives. Satisfaction of formulas F 2 L by valuations v : A ! f0; 1g is defined as usual. A knowledge base is a non-empty finite multiset over L. K denotes the set of all knowledge bases. An n-tuple B = ( 1; : : : ; n) 2 Kn is called a belief profile. We let F B = Fin=1 i, where t denotes multiset union. Note that using multisets is crucial to avoid information loss when several sources contain syntactically equal beliefs. For instance, f:ag t fag t fag = f:a; a; ag. We let pTBrhoafitlies=., FB(ur1tkh; e:r:im:s;oorbent,a;win)ee,dltehftaroBtmis,B1Bby=a diBsdionbgtakainncedodpBfieroskmofB=.bWyBaedcdakilnlga1 noant-tchoenfetornraddkioc>ft othr1ye. formula f safe in iff f and are built up over distinct variables from A. Intuitively, adding a safe formula to cannot introduce any conflicts.
A model of is a valuation v that satisfies all f 2 . We denote the set of all models of by Mod( ). If Mod( ) 6= ;, we call consistent and inconsistent otherwise. A minimal inconsistent (maximal consistent) subset of is a subset of that is inconsistent (consistent) and minimal (maximal) with this property. If Mod( ) Mod( 0), we say that entails 0 and write j= 0. If j= 0 and 0 j= , we call and 0 equivalent and write 0. If = ff g and 0 = fgg are singletons, we just write f j= g or f g.
An inconsistency measure I : Kn ! R0+ maps knowledge bases to non-negative
degrees of inconsistency. The most basic example is the drastic measure that yields
0 if the knowledge base is consistent and 1 otherwise [
To begin with, we define disagreement measures as functions over the set of all belief profiles S1
n=1 Kn that satisfy two basic desiderata.
Definition 1 (Disagreement Measure). A disagreement measure is a function D : Sn1=1 Kn ! R0+ such that for all belief profiles B = ( 1; : : : ; n), we have of f1; : : : ; ng.
Consistency generalizes the corresponding property for inconsistency measures.
Symmetry assures that the disagreement value is independent of the order in which the
knowledge bases are presented. It is similar to Anonymity in social choice theory [
Note that each disagreement measure D induces a corresponding inconsistency measure ID : K ! R0+ defined by ID( ) = D( ). Conversely, we can induce disagreement measures from inconsistency measures as we discuss next. 3.1
t-induced Disagreement Measures It is easy to see that each inconsistency measure induces a corresponding disagreement measure by taking the multiset union of knowledge bases in the profile.
tion DIt : Sn1=1 Kn ! R0+ defined by DIt(B) = I(F B) for all B 2 Kn is a disagreement measure. We call DIt the measure t-induced by I.
What can we say about the properties of t-induced measures? As we explain first, many properties for inconsistency measures have a natural generalization to disagreement measures that is compatible with t-induced measures in the following sense. Definition 2 (Corresponding Properties). Let P be a property for inconsistency measures and let P 0 be a property for disagreement measures. We call (P; P 0) a pair of corresponding properties iff
P 0,
One big class of properties for inconsistency measures gives guarantees about the relationship between inconsistency values when we extend the knowledge bases by particular formulas. We start with a general lemma and give some examples in the subsequent proposition.
ternary constraint on knowledge bases. Given a property for inconsistency measures
For all ; S; T 2 K, if C( ; S; T ) then I( t S) R I( t T ); define a property for disagreement measures as follows: n For all 1; : : : ; n; S; T 2 K, if C( G i=1
i; S; T ) then
D( 1 t S; 2; : : : ; n) R D( 1 t T; 2; : : : ; n):
Then ((1); (2)) is a pair of corresponding properties.
(1)
(2)
Remark 1. The reader may wonder why the corresponding property looks only at the
first argument. Note that by symmetry of disagreement measures, the same is true for all
other arguments. For instance, we have Inc ( 1; 2tS) = Inc ( 2tS; 1) R Inc ( 2t
T; 1) = Inc ( 1; 2 t T ):
We now apply Lemma 1 to some basic properties for inconsistency measures from [
I( ) I( t 0)
D( 1; 2; : : : ; n) D( 1 t 0; 2; : : : ; n) – Dominance: For f; g 2 L such that f j= g and f 6j= ?,
I( t ff g) I( t fgg)
D( t ff g; 2; : : : ; n) D( t fgg; 2; : : : ; n) – Safe Formula Independence: If f 2 L is safe in , then
I( t ff g) = I( ) If f 2 L is safe in Fin=1 i, then
D( 1 t ff g; 2; : : : ; n) = D( 1; 2; : : : ; n) – Adjunction Invariance: For all f; g 2 L,
I( [ ff; gg) = I( [ ff ^ gg)
D( 1 [ ff; gg; 2; : : : ) = D( 1 [ ff ^ gg; 2; : : : ) Monotony demands that adding knowledge can never decrease the disagreement value. Dominance says that replacing a claim with a (possibly weaker) implication of the original claim can never increase the disagreement value. Safe Formula Independence demands that a safe formula does not affect the disagreement value. Adjunction invariance says that it makes no difference whether two pieces of information are presented independently or as a single formula.
Example 1. The inconsistency measure ILPm that was discussed in [
What we can take from our discussion so far is that each inconsistency measure induces a disagreement measure with similar properties. As it turns out, each t-induced disagreement measure satisfies an additional property and, in fact, only the t-induced measures do. We call this property partition invariance. Intuitively, partition invariance means that the disagreement value depends only on the pieces of information in the belief profile and is independent of the distribution of these pieces. In the following proposition, a partition of a multiset M is a sequence of non-empty multisets M1; : : : ; Mk such that Fik=1 Mi = M .
Proposition 3 (Characterizations of Induced Families). The following statements are equivalent:
So the t-induced disagreement measures are exactly the partition invariant measures. However, partition variance can be undesirable in some scenarios.
Example 2. Consider the political goals ’increase wealth of households’ (h), ’increase wealth of firms’ (f ), ’increase wages’ (w). Suppose there are three political parties whose positions we represent in the profile
B = (ff; w; f ! wg; fw; h; w ! hg; ff; :w; w ! :f g): In this scenario, the parties only disagree about w. We modify B by moving w ! :f from the third to the second party:
B0 = (ff; w; f ! wg; fw; h; w ! h; w ! :f g; ff; :wg): The conflict with respect to w remains, but party 2’s positions now imply :f . Since we now have an additional conflict with respect to f , we would expect D(B) < D(B0). Partition invariant measures are unable to detect the difference in Example 2. Since partition invariance is an inherent property of t-induced measures, we should also investigate non-t-induced measures. 3.2
^-induced disagreement Measures Instead of taking the multiset union of all knowledge bases in the profile, we can also just replace each knowledge base with the conjunction of the formulas that it contains in order to induce a disagreement measure.
Sn1=1 Kn ! R0+ defined by DI^(B) = I(F 2BfVF 2 F g) for B 2 Kn is a disagreement measure. We call DI^ the measure ^-induced by I.
By repeated application of adjunction invariance (c.f. Proposition 2), one can show
that each adjunction invariant inconsistency measure satisfies I( ) = I(fVf2 f g),
see [
adjunction invariant.
The t-induced disagreement measures are characterized by partition invariance. Adjunction invariance plays a similar role for ^-induced measures.
Note that the inconsistency measure IDI^ induced by DI^ will also be adjunction invariant. Therefore, IDI^ 6= I if I is not adjunction invariant. In particular, DI^ can be a rather coarse measure if I is not adjunction invariant.
Example 3. The inconsistency measure IMI from [
Proposition 6 tells us that ^-induced measures are necessarily adjunction invariant. Whether or not each adjunction invariant disagreement measure is ^-induced is currently an open question. However, we have the following result.
n D(ff1g; : : : ; ffng) = D( G ffig); i=1 (3) then D is ^-induced by an inconsistency measure.
We call property (3) singleton union invariance in the following. While adjunction invariance and singleton union invariance are sufficient for being ^-induced, they are no longer necessary as the following example illustrates.
Example 4. Consider again the inconsistency measure IMI from [
We close this section by showing that the set of disagreement measures t-induced and ^-induced from inconsistency measures are neither equal nor disjoint.
To begin with, the ILPm inconsistency measure that was discussed in [
In order to show that there are partition invariant measures that are not adjunction
invariant and vice versa, we use the minimal inconsistent set measure IMI from [
On the other hand, DI^MI is adjunction invariant because each ^-induced measure is. However, since IMI is not adjunction invariant, we know from Proposition 5 that DI^MI is not t-induced. Hence, DI^MI is an example of a disagreement measure that is ^-induced, but not t-induced.
We illustrate our findings in Figure 1. The ^-induced incompatibility measures are a subset of the adjunction invariant measures (Proposition 6). The fact that all measures in the intersection of partition invariant and adjunction invariant measures are ^-induced follows from observing that partition invariance implies singleton union invariance (3) and Proposition 7. 4
Principles for Measuring Disagreement As illustrated in Figure 1, induced measures correspond to disagreement measures with very specific properties. t-induced measures are necessarily partition invariant. This may be undesirable in certain applications as illustrated in Example 2. If an inconsistency measure is adjunction invariant, the ^-induced measure will also be partition invariant. If it is not adjunction invariant, the ^-induced measure will not be partition invariant, but the measure may become rather coarse as illustrated in Example 3. This is some evidence that it is worth investigating non-induced measures. To further distinguish inconsistency from disagreement measures, we will now propose some stronger principles that go beyond our basic desiderata from Definition 1.
To guide our intuition, we think of each knowledge base as the belief set of an agent. We say that i contradicts j if i [ j is inconsistent. To begin with, let us consider an agent whose beliefs do not contradict any consistent position (its knowledge base is tautological). When adding such an agent to a belief profile, the disagreement value should not increase. Dually, if we add an agent that contradicts every position (its knowledge base is inconsistent), the disagreement value should not decrease. This intuition is captured by the following principles.
Tautology Let B 2 Kn and let > 2 K be tautological. Then D(B >) Contradiction Let B 2 Kn and let ? 2 K be contradictory. Then D(B ?)
D(B).
D(B).
Inconsistency measures focus mainly on the existence of conflicts. However, in a multiagent setting, conflicts can often be resolved by majority decisions. Given a belief profile B = ( 1; : : : ; n) 2 Kn, we call a subset C f1; : : : ; ng a consistent coalition iff Si2C i is consistent. We say that j is involved in a conflict in B iff there is a consistent coalition C such that j [ Si2C i is inconsistent. Our next principle demands that conflicts can be eased by majority decisions.
Majority Let B = ( 1; : : : ; n) 2 Kn. If j is consistent and involved in a conflict, then there is a k 2 N such that D(B k j ) < D(B).
Intuitively, Majority says that we can decrease the severity of a conflict by giving
sufficient support for one of the conflicting positions. It does not matter what position we
choose as long as this position is consistent. In future work, one may look at alternative
principles based on other methods to make group decisions [
Majority implies that we can strictly decrease the disagreement value by adding copies of one consistent position. However, this does not imply that the disagreement value will vanish. If we keep adding copies, the disagreement value will necessarily decrease but it may converge to a value strictly greater than 0. While one may argue that the limit should be 0 if almost all agents agree, one may also argue that the limit should be bounded from below by a positive constant if an unresolved conflict remains. We therefore do not strengthen majority. Instead, we consider an additional principle that demands that the limit is indeed 0 if the majority agrees on all non-contradictory positions. This intuition is captured by the next principle.
Majority Agreement in the Limit Let B 2 Kn. If M is a -maximal consistent subset of F B, then limk!1 D(B k M ) = 0:
We close this section with an impossibility result: Monotony and Partition Invariance cannot be satisfied jointly with our majority principles. The reason is that such measures can never decrease when receiving new information as explained in the following proposition.
D(B) for all B 2 Kn; 2 K; k 2 N.
The conditions of Proposition 8 are in particular met by several induced measures. k ) Corollary 2. Every disagreement measure that is – partition invariant and monotone or – t-induced from a monotone inconsistency measure or – ^-induced from a monotone and adjunction invariant inconsistency measure violates Majority and Majority Agreement in the Limit. 5
The -disagreement Measure
We now consider a novel disagreement measures inspired by the -inconsistency
measure from [
I ( ) = 1
maxfp j 9 : 8F 2
: P (F )
pg:
This formula describes the intuition that we explained in the beginning. p = maxfp j
9 : 8F 2 : P (F ) g is the maximum probability that all formulas in can
simultaneously take. We will have p = 1 if and only if is consistent [
Let us first look at the disagreement measures induced by I . I satisfies Monotony
[
Example 5. Let B = (fag; f:ag). Since P (a) = 1
P (:a), we have for all n 2 N DI^ (fag; f:ag) = I (fa; :ag) = 0:5
n = I (fa; :ag t G
fag) = DI^ ( fag; f:ag i=1 n fag):
However, we can modify the definition of the -inconsistency measure in order to get a disagreement measure that satisfies our desiderata. If we think of P (F ) as the degree of belief in F , then we should try to find a such that the beliefs of all agents are satisfied as well as possible. To do so, we can first look at how well satisfies the beliefs of each agent and then look at how well satisfies the agents’ beliefs overall. To measure satisfaction of one agent’s beliefs, we take the minimum of all probabilities assigned to the formulas in the agent’s knowledge base. Formally, for all probability distributions and knowledge bases over our language, we let
s ( ) = minfP (F ) j F 2 g: and call s ( ) the degree of satisfaction of . In order to measure satisfaction of a belief profile, we take the average degree of satisfaction of the knowledge bases in the profile. Formally, we let for all probability distributions and belief profiles B S (B) = 1
X s ( ) jBj 2B and call S(B) the degree of satisfaction of B. We now define a new disagreement measure. Intuitively, it attempts to maximize the degree of satisfaction of the profile. By subtracting the maximum degree of satisfaction from 1, we get a disagreement value. Definition 3 ( -Disagreement Measure). The -Disagreement Measure is defined by D (B) = 1
maxfp j 9 : S (B) = pg: To begin with, we note that D is a disagreement measures as defined in Definition 1 and can be computed by linear programming techniques.
optimization problem.
As we show next, D is neither t- nor ^-induced from any inconsistency measure. According to Proposition 3 and Proposition 6, it suffices to show that it is neither partition invariant nor adjunction invariant.
Example 6. Consider again the belief profiles B and B0 from Example 2. We have D (B) 0:33 and D (B) 0:44. As desired, D recognizes the increased disagreement in the profile. In particular, D is not partition invariant.
Example 7. To see that D is not adjunction invariant, note that D (fa; :ag) = 0:5, whereas D (fa ^ :ag) = 1 (contradictory formulas have probability 0 with respect to each ). Hence, D is also not adjunction invariant.
D satisfies our four principles for measuring disagreement as we show next. To begin with, we note that the disagreement value necessarily decreases as the proportion of agreeing agents increases.
D (B) 1 nk .
Proposition 10 implies, in particular, that the disagreement value goes to 0 as the proportion of agreeing agents nk goes to 1. Therefore, D satisfies our majority principles. Corollary 3. D satisfies Majority and Majority Agreement in the Limit. Tautology and Contradiction are also satisfied and can be strengthened slightly.
>) < D (B).
?) > D (B).
Regarding the properties corresponding to principles for measuring inconsistency from Proposition 2, D satisfies all except Adjunction Invariance (Example 7).
We already know that D yields 0 if and only if all knowledge bases in the profile are consistent with each other. In the following proposition, we explain in what cases it takes the maximum value 1.
Proposition 13. Let B 2 Kn. We have D (B) = 1 iff all i contain at least one contradictory formula.
Intuitively, if there is a knowledge base that does not contain any contradictory formulas, then all beliefs of one agent can be partially satisfied and the disagreement value with respect to D cannot be 1. So the degree of disagreement can only be maximal if each agent has contradictory beliefs.
In some applications, we may want to restrict to belief profiles with consistent knowledge bases. We can rescale D for this purpose. Proposition 10 gives us the following upper bounds on the disagreement value.
Corollary 4. Let B = ( 1; : : : ; n). If some i is consistent, then D (B) 1 n1 .
The bound in Corollary 4 is actually tight even if all knowledge bases in the profile are individually consistent as we explain in the following example.
Example 8. For n = 2 agents, we have D (fag; f:ag) = 12 . For n = 3, we have Dinco(fnasis^tebngt;(fF:i a^^Fjbg; f?:)bfgo)rm=ul23as. FIn1;g:e:n:e;rFaln, ,itfhwene Dhav(feFn1gs;a:ti:s:fi;afbFlengb)ut=pa1irwin1se. Hence, if we want to restrict to consistent knowledge bases, we can renormalize D by multiplying by nn 1 . The disagreement value will then be maximal whenever all agents have pairwise inconsistent beliefs.
As explained in Proposition 9, computing D (B) is a linear optimization problem.
Interior-point methods can solve these problems in polynomial time in the number of
optimization variables and constraints [
While interior-point methods give us a polynomial worst-case guarantee, they are often
outperformed in practice by the simplex algorithm. The simplex algorithm has
exponential runtime for some artificial examples, but empirically runs in time linear in the
number of optimization variables (exponential in jAj) and quadratic in the number of
constraints (quadratic in the overall number of formulas in the belief profile) [
In the long-term, our goal is to reason over belief profiles that contain conflicts
among agents. While we must leave a detailed discussion for future work, we will now
sketch how the -disagreement measure can be used for this purpose. The optimal
solutions of the linear optimization problem corresponding to D form a topologically
closed and convex set of probability distributions. This allows us to compute lower and
upper bound on the probability (or more intuitively, the degree of belief) of formulas
with respect to the optimal solutions that minimize disagreement. This is similar to the
probabilistic entailment problem [
Example 9. Suppose we have 100 reviews about a restaurant. While most reviewers agree that the food (f ) and the service (s) are good, two reviewers disagree about the interior design (d) of the restaurant. Let us assume that B = ( (fd; f; sg; f:d; f; sg) 95 ff; sg 3 f:f; :sg). We have D (B) 0:03. Intuitively, the degree of disagreement among agents is low because the majority of agents seem not to care about the interior design. The aggregated group beliefs for the atoms in this example are PB(d) = 0:5, PB(f ) = 1, PB(s) = 1.
We can use PB to define an entailment relation. For instance, we could say that B entails F iff the lower bound is strictly greater than 0:5. Then, in Example 9, PB entails f and s, but neither d nor :d. 6
Related Work
The authors in [
Some other conflict measures have been considered in non-classical frameworks.
These measures are often closer to distance measures because they mainly compare
how close two quantitative belief representations like probability functions, belief
functions or fuzzy membership functions are [
As we discussed, measuring disagreement is closely related to measuring
inconsistency [
[
Conclusions and Future Work In this paper, we investigated approaches to measuring disagreement among knowledge bases. In principle, inconsistency measures can be applied for this purpose by transforming belief profiles to single knowledge bases. However, we noticed some problems with this approach. For instance, many measures that are naively induced from inconsistency measures violate Majority and Agreement in the Limit as explained in Corollary 2. Even though this problem does not apply to measures ^-induced from inconsistency measures that violate adjunction invariance, these induced measures show another problem: they may be unable to notice that a conflict can be resolved by giving up parts of agents’ beliefs. For instance, the measures DI^MI and DI^ cannot distinguish the profiles (fa; bg; f:a; bg) and (fag; f:ag) because IMI and I cannot distinguish the knowledge bases fa ^ b; :a ^ bg and fa; :ag.
The -inconsistency measure D satisfies our principles for measuring disagreement and some other basic properties that correspond to principles for measuring inconsistency. Since D can perform satisfiability tests, we cannot expect to compute disagreement values in polynomial time with respect to the number of atoms. However, if our agents argue only about a moderate number of statements (we fix the number of atoms), the worst-case runtime is polynomial with respect to the number of agents.
In the long-term, we are in particular interested in reasoning over belief profiles that contain conflicts. We can use the -inconsistency measure for this purpose as we sketched at the end of Section 5. However, the aggregated group belief PB does not behave continuously. For instance, if we gradually increase the support for :s in Example 9, PB(s) will not gradually go to 0, but will jump to an undecided state like 0:5 or will jump to 0 at some point. This is not a principal problem for defining an entailment relation that either says that a formula is entailed or not entailed by a profile. However, a continuous notion of group beliefs would allow us to shift the focus from measuring disagreement among agents to measuring disagreement about statements (logical formulas). We could do so by measuring how well we can bound the aggregated beliefs about the formulas in the profile away from 0:5. However, if PB does not behave continuously, this approach will give us a rather coarse measure (basically three-valued). Therefore, an interesting question for future research is whether we can modify D or design other measures that give us an aggregated group belief with a more continuous behavior.