=Paper=
{{Paper
|id=Vol-2157/paper3
|storemode=property
|title=Measuring Disagreement among Knowledge Bases
|pdfUrl=https://ceur-ws.org/Vol-2157/paper3.pdf
|volume=Vol-2157
|authors=Nico Potyka
|dblpUrl=https://dblp.org/rec/conf/cade/Potyka18
}}
==Measuring Disagreement among Knowledge Bases==
https://ceur-ws.org/Vol-2157/paper3.pdf
Measuring Disagreement among Knowledge Bases
Nico Potyka
University of Osnabrück, Germany
Abstract. When combining beliefs from different sources, often not only new
knowledge but also conflicts arise. In this paper, we investigate how we can mea-
sure the disagreement among sources. We start our investigation with disagree-
ment measures that can be induced from inconsistency measures in an automated
way. After discussing some problems with this approach, we propose a new mea-
sure that is inspired by the η-inconsistency measure. Roughly speaking, it mea-
sures 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.
1 Introduction
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 [1, 2] or performing paraconsistent reasoning [3–5]. Inconsistency
measures [6, 7] quantify the degree of inconsistency and help analyzing and resolving
conflicts. While work on measuring inconsistency was initially inspired by ideas from
repairing knowledge bases and paraconsistent reasoning [8], inconsistency measures
also inspired new repair [9, 10] and paraconsistent reasoning mechanisms [11, 12].
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 mea-
suring 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 repair-
ing single knowledge bases [13]. We will therefore propose some new principles for
measuring disagreement and introduce a new measure that complies with them.
After explaining the necessary basics in Section 2, we will discuss the relation-
ship between inconsistency measures and disagreement measures in Section 3. To be-
gin 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 pro-
pose 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 in-
duced 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 [6]. Intuitively, it attempts to satisfy all agents’ beliefs
as well as possible and then measures the average dissatisfaction. We will show that
the measure satisfies the principles proposed in Section 4 and some other properties
that correspond to principles for measuring inconsistency. To give additional motiva-
tion for this work, we will sketch how the measure can be used for belief merging and
inconsistency-tolerant reasoning at the end of Section 5.
2 Basics
We consider a propositional logical language L built up over a finite set A of proposi-
tional atoms using the usual connectives. Satisfaction of formulas F ∈ L by valuations
v : A → {0, 1} 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 ) ∈ Kn
F F n
is called a belief profile. We let B = i=1 κi , where t denotes multiset union.
Note that using multisets is crucial to avoid information loss when several sources con-
tain syntactically equal beliefs. For instance, {¬a} t {a} t {a} = {¬a, a, a}. We let
B ◦ κ = (κ1 , . . . , κn , κ), that is, B ◦ κ is obtained from B by adding κ at the end of the
profile. Furthermore, we let B ◦1 κ = B ◦ κ and B ◦k κ = B ◦k−1 κ ◦ κ for k > 1.
That is, B ◦k κ is obtained from B by adding k copies of κ. We call a non-contradictory
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 ∈ κ. 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 incon-
sistent (consistent) and minimal (maximal) with this property. If Mod(κ) ⊆ Mod(κ0 ),
we say that κ entails κ0 and write κ |= κ0 . If κ |= κ0 and κ0 |= κ, we call κ and κ0
equivalent and write κ ≡ κ0 . If κ = {f } and κ0 = {g} are singletons, we just write
f |= g or f ≡ g.
An inconsistency measure I : Kn → R+ 0 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 [14]. Hence, it basically per-
forms a satisfiability test. There exist various other measures, see [15] for a recent
overview. While there is an ongoing debate about what properties an inconsistency
measure should satisfy, there is general agreement that it should be consistent in the
sense that I(κ) = 0 if and only if κ is consistent. Hence, the inconsistency value is
greater than zero if and only if κ is inconsistent. Various other properties of inconsis-
tency measures have been discussed [14, 16, 15]. We will present some of these later,
when talking about corresponding properties of disagreement measures.
3 Induced Disagreement Measures
To beginSwith, we define disagreement measures as functions over the set of all belief
∞
profiles n=1 Kn that satisfy two basic desiderata.
Definition
S∞ 1 (Disagreement Measure). A disagreement measure is a function D :
n=1 K n
→ R+
0 such that for all belief profiles B = (κ1 , . . . , κn ), we have
Fn
1. Consistency: D(B) = 0 iff i=1 κi is consistent.
2. Symmetry: D(B) = D(κσ(1) , . . . , κσ(n) ) for each permutation σ of {1, . . . , n}.
Consistency generalizes the corresponding property for inconsistency measures. Sym-
metry 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 [17]
and guarantees equal treatment of different sources.
Note that each disagreement measure D induces a corresponding inconsistency
measure ID : K → R+ 0 defined by ID (κ) = D(κ). Conversely, we can induce dis-
agreement 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.
Proposition
S∞1 (t-induced Measure). If I is an inconsistency measure, then the func-
tion DIt : n=1 Kn → R+ t n
F
0 defined by DI (B) = I( B) for all B ∈ K is a disagree-
t
ment measure. We call DI 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 mea-
sures and let P 0 be a property for disagreement measures. We call (P, P 0 ) a pair of
corresponding properties iff
1. if an inconsistency measure I satisfies P , then the t-induced measure DIt satisfies
P 0,
2. if a disagreement measure D satisfies P 0 , then the corresponding inconsistency
measure ID satisfies P .
One big class of properties for inconsistency measures gives guarantees about the rela-
tionship between inconsistency values when we extend the knowledge bases by particu-
lar formulas. We start with a general lemma and give some examples in the subsequent
proposition.
Lemma 1 (Transfer Lemma). Let R be a binary relation on R and let C ⊆ K3 be a
ternary constraint on knowledge bases. Given a property for inconsistency measures
For all κ, S, T ∈ K, if C(κ, S, T ) then I(κ t S) R I(κ t T ), (1)
define a property for disagreement measures as follows:
n
G
For all κ1 , . . . , κn , S, T ∈ K, if C( κi , S, T ) then
i=1
D(κ1 t S, κ2 , . . . , κn ) R D(κ1 t T, κ2 , . . . , κn ). (2)
Then ((1), (2)) is a pair of corresponding properties.
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 , κ2 tS) = Inc∗ (κ2 tS, κ1 ) R Inc∗ (κ2 t
T, κ1 ) = Inc∗ (κ1 , κ2 t T ).
We now apply Lemma 1 to some basic properties for inconsistency measures from [14]
and adjunction invariance from [16] that will play an important role later.
Proposition 2. The following are pairs of corresponding properties for inconsistency
and disagreement measures:
– Monotony:
I(κ) ≤ I(κ t κ0 )
D(κ1 , κ2 , . . . , κn ) ≤ D(κ1 t κ0 , κ2 , . . . , κn )
– Dominance: For f, g ∈ L such that f |= g and f 6|= ⊥,
I(κ t {f }) ≥ I(κ t {g})
D(κ t {f }, κ2 , . . . , κn ) ≥ D(κ t {g}, κ2 , . . . , κn )
– Safe Formula Independence: If f ∈ L is safe in κ, then
I(κ t {f }) = I(κ) Fn
If f ∈ L is safe in i=1 κi , then
D(κ1 t {f }, κ2 , . . . , κn ) = D(κ1 , κ2 , . . . , κn )
– Adjunction Invariance: For all f, g ∈ L,
I(κ ∪ {f, g}) = I(κ ∪ {f ∧ g})
D(κ1 ∪ {f, g}, κ2 , . . . ) = D(κ1 ∪ {f ∧ g}, κ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 invari-
ance 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 [18] satisfies Monotony,
Dominance, Safe Formula Independence and Adjunction Invariance. From Proposition
2, we can conclude that the t-induced disagreement measure Inct
LPm satisfies the cor-
responding properties for disagreement measures.
What we can take from our discussion so far is that each inconsistency measure in-
duces 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 be-
lief profile and is independent of the distribution of these pieces. In the following propo-
sition, a partition of a multiset M is a sequence of non-empty multisets M1 , . . . , Mk
Fk
such that i=1 Mi = M .
Proposition 3 (Characterizations of Induced Families). The following statements
are equivalent:
1. D is t-induced by an inconsistency measure.
2. D is t-induced by ID . F n1
D is partition invariant, that is, for all κ ∈ K and for all partitions i=1
3. F Pi =
n2 0 0 0
P
i=1 i = κ of κ, we have that D(P 1 , . . . , P n 1
) = D(P 1 , . . . , P n2 ).
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 = ({f, w, f → w}, {w, h, w → h}, {f, ¬w, w → ¬f }).
In this scenario, the parties only disagree about w. We modify B by moving w → ¬f
from the third to the second party:
B 0 = ({f, w, f → w}, {w, h, w → h, w → ¬f }, {f, ¬w}).
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(B 0 ).
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 in-
vestigate 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.
Proposition 4 (∧-induced Measure). If I F is an inconsistency measure, then DI∧ :
∞ n + ∧
→ R0 defined by DI (B) = I( κ∈B { F ∈κ F }) for B ∈ Kn is a dis-
S V
n=1 K
agreement measure. We call DI∧ the measure ∧-induced by I.
By repeated application of adjunction invariance (c.f. Proposition 2), oneVcan show
that each adjunction invariant inconsistency measure satisfies I(κ) = I({ f ∈κ f }),
see [16], Proposition 9. We can use this result to show that for adjunction invariant
inconsistency measures, the ∧-induced and the t-induced measures are equal.
Corollary 1. If I is an adjunction invariant inconsistency measure, then DI∧ = DIt .
F
This is actually the only case in which the ∧-induced measure can be -induced.
Proposition 5. Let I be an inconsistency measure. DI∧ is t-induced if and only if I is
adjunction invariant.
The t-induced disagreement measures are characterized by partition invariance. Ad-
junction invariance plays a similar role for ∧-induced measures.
Proposition 6. For each inconsistency measure I, DI∧ satisfies adjunction invariance.
Note that the inconsistency measure IDI∧ induced by DI∧ will also be adjunction invari-
ant. 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 IM I from [18] counts the number of minimal
inconsistent sets of a knowledge base. IM I is not adjunction invariant. For instance,
IM I ({a, ¬a, a ∧ b}) = 2 because {a, ¬a} and {¬a, a ∧ b} are the only minimal incon-
sistent sets. However, IM I ({a∧¬a∧a∧b}) = 1 because the only minimal inconsistent
set
V is the knowledge base itself. Furthermore, we will have DI∧M I (κ) = 1 whenever
∧
f ∈κ f is inconsistent and DIM I (κ) = 0 otherwise. Hence, the inconsistency measure
corresponding to DI∧M I is the drastic measure.
Proposition 6 tells us that ∧-induced measures are necessarily adjunction invari-
ant. Whether or not each adjunction invariant disagreement measure is ∧-induced is
currently an open question. However, we have the following result.
Proposition 7. If D satisfies adjunction invariance and
n
G
D({f1 }, . . . , {fn }) = D( {fi }), (3)
i=1
then D is ∧-induced by an inconsistency measure.
We call property (3) singleton union invariance in the following. While adjunction in-
variance 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 IM I from [18] that was ex-
plained in Example 3. We have DI∧M I ({a ∧ b}, {¬a ∧ b}, {a ∧ ¬b}) = IM I ({a ∧
b, ¬a ∧ b, a ∧ ¬b}) = 3 by definition of the ∧-induced measure. However, DI∧M I ({a ∧
b, ¬a ∧ b, a ∧ ¬b}) = IM I ({a ∧ b ∧ ¬a ∧ b ∧ a ∧ ¬b}) = 1. Hence, DI∧M I is not singleton
union invariant.
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 [18] is ad-
junction invariant. Therefore, DItLPm = DI∧LPm according to Corollary 1. Hence, the
intersection of t-induced and ∧-induced disagreement measures is non-empty.
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 IM I from [18].
As demonstrated in Example 3, IM I is not adjunction invariant. Therefore, the Transfer
Lemma implies that DItM I is not adjunction invariant either. Hence, DItM I cannot be ∧-
induced according to Proposition 6.
On the other hand, DI∧M I is adjunction invariant because each ∧-induced measure
is. However, since IM I is not adjunction invariant, we know from Proposition 5 that
DI∧M I is not t-induced. Hence, DI∧M I is an example of a disagreement measure that is
∧-induced, but not t-induced.
Fig. 1. Venn diagram illustrating induced measures in the space of all disagreement measures.
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 incon-
sistency 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 distin-
guish 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 ∈ Kn and let κ> ∈ K be tautological. Then D(B ◦ κ> ) ≤ D(B).
Contradiction Let B ∈ Kn and let κ⊥ ∈ K be contradictory. Then 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 ) ∈ Kn , we call a subset C ⊆ {1, . . . , n} a consistent coalition
S
S κj is involved in a conflict in B iff there is a con-
iff i∈C κi is consistent. We say that
sistent coalition C such that κj ∪ i∈C κi is inconsistent. Our next principle demands
that conflicts can be eased by majority decisions.
Majority Let B = (κ1 , . . . , κn ) ∈ Kn . If κj is consistent and involved in a conflict,
then there is a k ∈ N such that D(B ◦k κj ) < D(B).
Intuitively, Majority says that we can decrease the severity of a conflict by giving suf-
ficient 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 [17], but Majority seems to
be a natural starting point.
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 ∈ Kn . If M is a ⊂-maximal consistent sub-
set of B, then limk→∞ D(B ◦k M ) = 0.
F
We close this section with an impossibility result: Monotony and Partition Invari-
ance 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 fol-
lowing proposition.
Proposition 8. If D satisfies Monotony and Partition Invariance, then D(B ◦k κ) ≥
D(B) for all B ∈ Kn , κ ∈ K, k ∈ N.
The conditions of Proposition 8 are in particular met by several induced measures.
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 mea-
sure from [6]. Roughly speaking, the η-inconsistency measure attempts to maximize
the probability of all formulas within a knowledge base. By subtracting this proba-
bility from 1, we get an inconsistency value. In order to assign probabilities to for-
mulas, we consider probability distributions over the set of all valuations Ω = {v |
vP: A → {0, 1}} of our language. Given a probability distribution π : Ω → [0, 1]
( v∈Ω π(v) = 1) and a formula F ∈ L, we let
X
Pπ (F ) = π(v).
v|=F
Intuitively, Pπ (F ) is the probability that F is true with respect to π. The η-inconsistency
measure from [6] is defined by
Iη (κ) = 1 − max{p | ∃π : ∀F ∈ κ : Pπ (F ) ≥ p}.
This formula describes the intuition that we explained in the beginning. p∗ = max{p |
∃π : ∀F ∈ κ : Pπ (F ) ≥ κ} is the maximum probability that all formulas in κ can
simultaneously take. We will have p∗ = 1 if and only if κ is consistent [6].
Let us first look at the disagreement measures induced by Iη . Iη satisfies Monotony
[15]. Therefore, DItη will violate our majority principles as explained in Corollary 2.
However, Iη is not adjunction invariant [15]. Therefore, Proposition 5 implies that
DItη 6= DI∧η . Still, DI∧η does not satisfy our majority principles either.
Example 5. Let B = ({a}, {¬a}). Since Pπ (a) = 1 − Pπ (¬a), we have for all n ∈ N
DI∧η ({a}, {¬a}) = Iη ({a, ¬a}) = 0.5
n
G
{a}) = DI∧η ( {a}, {¬a} ◦n {a}).
= Iη ({a, ¬a} t
i=1
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π (κ) = min{Pπ (F ) | F ∈ κ}.
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
1 X
Sπ (B) = sπ (κ)
|B|
κ∈B
and call S(B) the degree of satisfaction of B. We now define a new disagreement mea-
sure. 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 − max{p | ∃π : Sπ (B) = p}.
To begin with, we note that Dη is a disagreement measures as defined in Definition 1
and can be computed by linear programming techniques.
Proposition 9. Dη is a disagreement measures and can be computed by solving a linear
optimization problem.
As we show next, Dη is neither t- nor ∧-induced from any inconsistency mea-
sure. 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 B 0 from Example 2. We have
Dη (B) ≈ 0.33 and Dη (B) ≈ 0.44. As desired, Dη recognizes the increased disagree-
ment in the profile. In particular, Dη is not partition invariant.
Example 7. To see that Dη is not adjunction invariant, note that Dη ({a, ¬a}) = 0.5,
whereas Dη ({a ∧ ¬a}) = 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.
Proposition 10. Let B ∈ Kn . If B contains a consistent coalition of size k, then
Dη (B) ≤ 1 − nk .
Proposition 10 implies, in particular, that the disagreement value goes to 0 as the pro-
portion 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.
Proposition 11. Dη satisfies Tautology and Contradiction. Furthermore,
– If Dη (B) > 0, then Dη (B ◦ κ> ) < Dη (B).
– If Dη (B) < 1, then Dη (B ◦ κ⊥ ) > Dη (B).
Regarding the properties corresponding to principles for measuring inconsistency from
Proposition 2, Dη satisfies all except Adjunction Invariance (Example 7).
Proposition 12. Dη satisfies Monotony, Dominance and Safe Formula Independence.
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 ∈ 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 formu-
las, 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 fol-
lowing 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η ({a}, {¬a}) = 21 . For n = 3, we have
Dη ({a ∧ b}, {¬a ∧ b}, {¬b}) = 23 . In general, if we have n satisfiable but pairwise
inconsistent (Fi ∧ Fj ≡ ⊥) formulas F1 , . . . , Fn , then Dη ({F1 }, . . . , {Fn }) = 1 − n1 .
Hence, if we want to restrict to consistent knowledge bases, we can renormalize Dη by
n
multiplying by n−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 [19]. While the number of optimization variables
is exponential in the number of atoms |A| of our language, the number of constraints is
linear in the number of formulas in all knowledge bases in the profile. Roughly speak-
ing, computing Dη (B) is very sensitive to the number of atoms, but scales well with
respect to the number of agents. In the language of parameterized complexity theory
[20], computing Dη (B) is fixed-parameter tractable (that is, polynomial if we fix the
number of atoms) .
Proposition 14. Computing Dη (B) is fixed-parameter tractable with parameter |A|.
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 expo-
nential runtime for some artificial examples, but empirically runs in time linear in the
number of optimization variables (exponential in |A|) and quadratic in the number of
constraints (quadratic in the overall number of formulas in the belief profile) [19].
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 so-
lutions 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 [21], where we compute lower and upper bounds with
respect to probability distributions that satisfy probabilistic knowledge bases. If, for a
belief profile B, the lower bound of the formula F is l and the upper bound is u, we
write PB (F ) = [l, u]. If l = u, we just write PB (F ) = l. We call PB the aggregated
group belief.
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 = ( ({d, f, s}, {¬d, f, s})◦95
{f, s} ◦3 {¬f, ¬s}). 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 [22] considered the problem of measuring disagreement in limited choice
problems, where each agent can choose from a finite set of alternatives. The measures
are basically defined by counting the decisions and relating the counts. The authors
give intuitive justification for their measures, but do not consider general principles. In
order to transfer their approach to our setting, one may identify atomic formulas with
alternatives in their framework, but it is not clear how this approach could be extended
to knowledge bases that contain complex formulas.
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 func-
tions or fuzzy membership functions are [23–25]. In [26], some compatibility measures
for Markov logic networks have been proposed. The measures are normalized and the
maximum degree of compatibility can be related to a notion of coherence of Markov
logic networks. However, this notion cannot be transferred to classical knowledge bases
easily.
As we discussed, measuring disagreement is closely related to measuring inconsis-
tency [6, 14, 27] and merging knowledge bases [28–30]. The principles Majority and
Majority Agreement in the Limit from Section 4 are inspired by Majority merging op-
erators that allow that a sufficiently large interest group can determine the merging
outcome. The η-disagreement measure is perhaps most closely related to model-based
operators and DA2 operators, which attempt to minimize some notion of distance be-
tween interpretations and the models of the knowledge bases in the profile. In contrast,
the η-disagreement measure minimizes a probabilistic degree of dissatisfaction of the
belief profile.
[31] introduced some entailment relations based on consensus in belief profiles. We
will investigate relationships to entailment relations derived from the η-disagreement
measure in future work.
7 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 trans-
forming belief profiles to single knowledge bases. However, we noticed some prob-
lems 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 in-
consistency 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∧M I and DI∧η cannot distinguish
the profiles ({a, b}, {¬a, b}) and ({a}, {¬a}) because IM I and Iη cannot distinguish
the knowledge bases {a ∧ b, ¬a ∧ b} and {a, ¬a}.
The η-inconsistency measure Dη satisfies our principles for measuring disagree-
ment and some other basic properties that correspond to principles for measuring in-
consistency. 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 Exam-
ple 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 for-
mulas). 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 con-
tinuously, 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.
References
1. Kalyanpur, A., Parsia, B., Sirin, E., Cuenca-Grau, B.: Repairing unsatisfiable concepts in
owl ontologies. In: European Semantic Web Conference, Springer (2006) 170–184
2. Lehmann, J., Bühmann, L.: Ore-a tool for repairing and enriching knowledge bases. In:
International Semantic Web Conference, Springer (2010) 177–193
3. Benferhat, S., Dubois, D., Prade, H.: Some syntactic approaches to the handling of inconsis-
tent knowledge bases: A comparative study part 1: The flat case. Studia Logica 58(1) (1997)
17–45
4. Arieli, O., Avron, A., Zamansky, A.: What is an ideal logic for reasoning with inconsistency?.
In: IJCAI 2011. (2011) 706–711
5. Priest, G.: Paraconsistent logic. In: Handbook of philosophical logic. Springer (2002)
287–393
6. Knight, K.: Measuring inconsistency. Journal of Philosophical Logic 31(1) (2002) 77–98
7. Grant, J., Hunter, A.: Measuring inconsistency in knowledgebases. Journal of Intelligent
Information Systems 27(2) (2006) 159–184
8. Hunter, A., Konieczny, S.: Approaches to measuring inconsistent information. In: Inconsis-
tency tolerance. Springer (2005) 191–236
9. Thimm, M.: Measuring inconsistency in probabilistic knowledge bases. In: UAI 2009, AUAI
Press (2009) 530–537
10. Muiño, D.P.: Measuring and repairing inconsistency in probabilistic knowledge bases. In-
ternational Journal of Approximate Reasoning 52(6) (2011) 828–840
11. Potyka, N.: Linear programs for measuring inconsistency in probabilistic logics. In: KR
2014. (2014) 568–577
12. Potyka, N., Thimm, M.: Probabilistic reasoning with inconsistent beliefs using inconsistency
measures. In: IJCAI 2015. (2015) 3156–3163
13. Konieczny, S.: On the difference between merging knowledge bases and combining them.
In: KR. (2000) 135–144
14. Hunter, A., Konieczny, S.: Measuring inconsistency through minimal inconsistent sets. KR
2008 8 (2008) 358–366
15. Thimm, M.: On the compliance of rationality postulates for inconsistency measures: A more
or less complete picture. KI-Künstliche Intelligenz (2016) 1–9
16. Besnard, P.: Revisiting postulates for inconsistency measures. In: European Workshop on
Logics in Artificial Intelligence, Springer (2014) 383–396
17. Zwicker, W.: Introduction to the theory of voting. Handbook of computational social choice
(2016) 23–56
18. Hunter, A., Konieczny, S.: On the measure of conflicts: Shapley inconsistency values. Arti-
ficial Intelligence 174(14) (2010) 1007–1026
19. Matousek, J., Gärtner, B.: Understanding and Using Linear Programming. Universitext
(1979). Springer (2007)
20. Flum, J., Grohe, M.: Parameterized complexity theory. Springer Science & Business Media
(2006)
21. Hansen, P., Jaumard, B.: Probabilistic satisfiability. In: Handbook of Defeasible Reasoning
and Uncertainty Management Systems. Springer (2000) 321–367
22. Whitworth, B., Felton, R.: Measuring disagreement in groups facing limited-choice prob-
lems. ACM SIGMIS Database 30(3-4) (1999) 22–33
23. Liu, W.: Analyzing the degree of conflict among belief functions. Artificial Intelligence
170(11) (2006) 909–924
24. Castiñeira, E.E., Cubillo, S., Montilla, W.: Measuring incompatibility between atanassovs
intuitionistic fuzzy sets. Information Sciences 180(6) (2010) 820–833
25. Jousselme, A.L., Maupin, P.: Distances in evidence theory: Comprehensive survey and gen-
eralizations. International Journal of Approximate Reasoning 53(2) (2012) 118–145
26. Thimm, M.: Coherence and compatibility of markov logic networks. In: ECAI 2014, IOS
Press (2014) 891–896
27. Grant, J., Hunter, A.: Distance-based measures of inconsistency. In: European Conference
on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, Springer (2013)
230–241
28. Baral, C., Kraus, S., Minker, J.: Combining multiple knowledge bases. IEEE transactions
on knowledge and data engineering 3(2) (1991) 208–220
29. Liberatore, P., Schaerf, M.: Arbitration (or how to merge knowledge bases). IEEE Transac-
tions on Knowledge and Data Engineering 10(1) (1998) 76–90
30. Konieczny, S., Pérez, R.P.: Logic based merging. Journal of Philosophical Logic 40(2)
(2011) 239–270
31. Grégoire, É., Konieczny, S., Lagniez, J.: On consensus extraction. In: IJCAI 2016, New
York, AAAI Press (2016) 1095–1101