Merginator: A belief merging tool for consensus support

Abstract

Belief merging aims to combine pieces of information from different (and possibly conflicting) sources so as to produce a single consistent belief base which retains as much information as possible. In this paper, we describe Merginator, a logic-based tool implementing three belief merging operators presented with specific characteristics that make them interesting for comparison: Δ_Σ, Δ_GMax and Δ_ps. We describe these operators while solving a set of basic examples found in the literature that we translate into natural language to provide insights for Merginator users. We also propose two more complex consensus-seeking examples: an adaptation to the role play “Lost at Sea” and the subject of administrative response to air pollution in Hong Kong. Results show that all three operators provide a consensus to the scenarios, and Δ_ps gives the most refined consensus. This demonstrates that belief merging, is a viable technique to support consensus decision-making in many domains. Merginator is open source software available at GitHub.

Keywords

Consensus decision-making knowledge representation propositional logic logic-based merging belief merging operators

1 Introduction

Whether in everyday life or in work environments, all individuals must choose between alternatives options that they might face. This process, called decision-making, is heavily based on the beliefs of the stakeholder. At home, work, or in social life, individuals are often involved in group decision-making, a process by which individuals collectively make a choice from a set of alternative options. In this case, when there is a group of stakeholders that have to make a decision on a certain topic involving multiple variables, they are very likely to have different beliefs that makes it difficult to reach an agreement.

Decisions made by groups are often different from those made by individuals, highlighting the need for consensus-based decision-making. Consensus is a cooperative process in which stakeholders agree to support a decision in the best interest of the whole [2].

In Artificial Intelligence, belief merging is a firmly established technique for the integration of knowledge coming from different sources. This logic-based technique is defined as the operation of combining information from a set of (possibly conflicting) belief bases obtained from different sources to produce a single, consistent belief base [18]. In this case, each belief base corresponds to the knowledge or preferences of a stakeholder. By merging these belief bases we obtain a belief base that represents the consensus of preferences, or the knowledge of the group.

Belief merging has been extensively studied in terms of postulates, which are the properties that the merging process must follow in order to produce rational results and, in terms of processes, which consist of a set of predefined steps in order to generate the results [4 , 13]. Some implementations have been proposed [7]1, [19]2, with notable practical applications [8, 16].

However, there is no accessible tool for non-experts showing the usefulness of this technique. In this paper, we described such a tool, called Merginator, which implements three belief merging operators. We then compare these operators by solving a set of classical examples found in the literature. We also design two real-world scenarios in order to show the applicability of belief merging.

Merginator can serve as support for Mathematics, Logic and AI lectures, and can assist in research from these areas.

2 Preliminaries

Belief merging generally described in terms of propositional logic, with the major of proposals based on model theory. We consider a language $L$ of propositional logic defined on a finite set of propositional variables or atoms P : = {p₁, p₂, …, p_n}. A propositional formula ψ is then constructed by a subset of variables from P and logic connectives ρ = {¬, ∧, ∨, →, ↔} in the classical way.

For convenience, if ψ is a formula or a set of formulae, then $P (ψ)$ denotes the set of atoms appearing in ψ. $| P |$ denotes the cardinality of set $P$ .

A literal l is an atom or the negation of an atom.

A term D is a finite conjunction of literals such that D = l₁ ∧ … ∧ l_k, with l_i = p_j or l_i = ¬ p_j.

Every formula $ψ \in L$ can be transformed into a Disjunctive Normal Form (DNF_ψ), such that ψ ≡ DNF_ψ, where DNF_ψ is a disjunction of terms, DNF_ψ =D₁ ∨ … ∨ D_m.

An interpretation, state, or world is a function w from P to {1, 0}, with these two values interpreted as the classical values of True (T) and False (F), respectively. w is also extended over $L$ in the usual way.

The set of all possible interpretations is denoted by $W$ , its elements will be denoted by vectors of the form (w (p₁), …, w (p_n)) where w (p_i) =1 or w (p_i) =0 for i = 1, …, n. The cardinality of $W$ is thus $| W | = 2^{n}$ .

K is said to be satisfiable (consistent) iff there is a model of K, i.e. iff w (K) =1 for some interpretation w. The set of models of a formula K is $\mod (K) = {w (K) = 1 ∣ w \in W}$ .

Along with these classical logical concepts, we consider the following definitions [11]:

Definition 1.A belief base K is a finite set of formulae of $L$ representing the beliefs of an agent. In this paper we sometimes identify K with the conjunction of its elements, for example if K = {ψ₁, ψ₂, …, ψ_n} then K = ψ₁ ∧ ψ₂ ∧ … ∧ ψ_n.

Definition 2.A belief profile E = {K₁, …, K_m} denotes the beliefs of the group of agents involved in the fusion process. E is a multiset of m belief bases, as two or more agents may have identical beliefs.

3 Belief merging

The integration of knowledge coming from different sources has been widely studied topic in the literature. From a logic-based scheme perspective, belief merging is used when the sources are equally reliable and at least two of them have a different opinion of the situation, i.e. the two views are contradictory. If there is no reason to consider one of the sources as the most reliable one, we must merge both views into a new one trying to retain as much information as possible of both opinions, without contradictions [11].

In this approach, the knowledge of each source of information is modelled as a belief base, which is defined as a finite set of propositional formulae representing wishes, opinions or knowledge of a source of information (e.g. agent, person, sensor) [14].

A characterization of rational belief merging is given by the following postulates [10]:

Δ (E) is consistent

If E is consistent, then Δ (E) = ⋀ E

If E₁ ↔ E₂ then ⊢Δ (E₁) ↔ Δ (E₂)

If K ∧ K′ is not consistent, then

Δ (K ⊔ K′) ⊬ K

Δ (E₁) ∧ Δ (E₂) ⊢ Δ (E₁ ⊔ E₂)

If Δ (E₁) ∧ Δ (E₂) is consistent, then

Δ (E₁ ⊔ E₂) ⊢ Δ (E₁) ∧ Δ (E₂)

A number of belief merging operators have been proposed in an attempt to satisfy this set of postulates [9 , 22]. A belief merging operator Δ is defined as [11]:

Definition 3.If Δ is an operator that satisfies A1–A6 and E a belief profile, then mod (Δ (E)) represents the set of interpretations resulting from the fusion, i.e. applying Δ to E results in the consistent knowledge base Δ (E).

It is common to represent the result of a fusion operator as a set of interpretations instead of belief bases. However, it is possible to obtain the formula representing the belief base from this set of interpretations, except equivalences.

Actually, belief merging operators are categorized in two main families: model-based operators and formula-based operators [13]. Merginator implements model-based operators and considers order relations between interpretations.

We can consider the following two subclasses of (model-based) merging operators [13]:

Majority merging operators. Focus on satisfying the agents’ beliefs as a whole. If a subset of beliefs in the belief profile has sufficient support, then they prevail. Majority operators try to minimize global dissatisfaction.

Arbitration merging operators. Focus on satisfying as focuses on satisfying as much as possible every agent. This subclass of operators select the median of possible choices. Arbitration operators try to minimize individual dissatisfaction.

Table 1 outlines the particular characteristics of all three merging operators implemented in Merginator. Several other operators have been defined, but most of them can be considered as variants of those considered. These three operators will be defined in the next sections.

Table 1
Main characteristics of Δ_Σ, Δ_GMax, Δ_ps

Δ_Σ Δ_GMax Δ_ps (PS-Merge)

Subclass

Majority √ - √

Arbitration - √ √

Measure

Hamming distance √ √ -

Partial satisfiability - - √

Belief format

DNF - - √

Indistinct √ √ -

Inconsistency

Inconsistent belief bases - - √

Postulates

(A1) √ √ √

(A2) √ √ √

(A3) √ √ √∗

(A4) √ √ √∗

(A5) √ √ √∗

(A6) √ √ √∗

	Δ_Σ	Δ_GMax	Δ_ps (PS-Merge)
Subclass
Majority	√	-	√
Arbitration	-	√	√
Measure
Hamming distance	√	√	-
Partial satisfiability	-	-	√
Belief format
DNF	-	-	√
Indistinct	√	√	-
Inconsistency
Inconsistent belief bases	-	-	√
Postulates
(A1)	√	√	√
(A2)	√	√	√
(A3)	√	√	√∗
(A4)	√	√	√∗
(A5)	√	√	√∗
(A6)	√	√	√∗

∗Under certain conditions [1].

3.1 Model-based Δ_Σ

Δ_Σ operator is defined using Hamming distance and sum aggregation functions [9].

Definition 4.The Hamming distance dist between two interpretations w, w′ corresponds to the number of propositional atoms in which two interpretations differ: $dist (w, w^{'}) = \sum_{i = 1}^{n} | w (p_{i}) - w^{'} (p_{i}) |$

Definition 5.The distance between an interpretation w and a belief base K is defined as:

$dist (w, K) = min_{w^{'} ⊨ K} dist (w, w^{'})$

Definition 6.The Σ-distance dist_Σ is defined, given a belief profile E and an interpretation w, as: ${dist}_{Σ} (w, E) = \sum_{K \in E} dist (w, K)$

Then the following pre-order is defined: $w \leq_{E}^{Σ} w^{'} \Leftrightarrow {dist}_{Σ} (w, E) \leq {dist}_{Σ} (w^{'}, E)$

Definition 7.Δ_Σ operator is defined by its models as: $\mod (Δ_{Σ} (E)) = min (W, \leq_{E}^{Σ})$ (1)

In other words, a valid merging of E with respect to Δ_Σ is any belief base K satisfying mod (K) = mod (Δ_Σ (E)).

3.2 Δ_GMax operator

The Δ_GMax operator was the first arbitration-merging operator formally proposed in [10]. This operator also employs the notions of distance between two interpretations (Definition 4) and distance between an interpretation with respect to a belief base (Definition 5).

Definition 8.The GMax-distance is defined with respect the distances between each interpretation w and the n belief bases of E: $({dist}_{1}^{w}, \dots, {dist}_{n}^{w})$ , with ${dist}_{j}^{w} = dist (w, K_{j})$ for j = 1, …, m. Let $L_{w}^{E}$ be an n-ary tuple obtained from $({dist}_{1}^{w}, \dots, {dist}_{n}^{w})$ by placing its elements in descending order. The GMax-distance dist_GMax between an interpretation w and a profile E corresponds to the list $L_{w}^{E}$ . Let ≤_lex be the lexicographic order between the sequences of integer numbers (of the same length), the following total pre-order is defined: $\begin{matrix} w \leq_{GMax}^{E} w^{'} \Leftrightarrow {dist}_{GMax} (w, E) \\ \leq_{lex} {dist}_{GMax} (w^{'}, E) \end{matrix}$

Definition 9.Δ_GMax operator is defined by its models as: $\mod (Δ_{GMax} (E)) = min (W, \leq_{GMax}^{E})$ (2)

3.3 Δ_ps (PS-Merge) operator

The Δ_ps operator is a majority-based operator that, unlike previous operators, also supports inconsistent belief bases. It is not based on a classic Hamming measure distance but rather on partial satisfiability. This notion allows savings at computing the models of belief bases.

Definition 10.Partial satisfiability is defined over a belief base normalized in DNF format: Q_K and any interpretation $w \in W$ . The partial satisfiability of Q_K for w, denoted by w_ps (Q_K), is defined as:

if Q_K is a conjunction C₁ ∧ … ∧ C_s where each C_i is a literal, then:

$\begin{matrix} w_{ps} (Q_{K}) \\ = max {\sum_{i = 1}^{s} \frac{w (C_{i})}{s}, \frac{n - | P (⋀_{i = 1}^{s} C_{i}) |}{2 n}} \end{matrix}$ (3) Where n denotes the number of atoms from the considered language, s denotes the number of literals appearing in the conjunction and $| P | = n$ .

If Q_K is a disjunction D₁ ∨ … ∨ D_r where each D_i is a conjunction of literals, then: $w_{ps} (Q_{K}) = max {w_{ps} (D_{1}), \dots, w_{ps} (D_{r})}$ (4)

Definition 11.The following pre-order is defined. $w \leq_{ps}^{E} w^{'} iff \sum_{i = 1}^{m} w_{ps} (Q_{K_{i}}) \leq \sum_{i = 1}^{m} w_{ps}^{'} (Q_{K_{i}})$ (5)

Definition 12.Δ_ps operator is defined by its models as: $\mod (Δ_{ps} (E)) = max (W, \leq_{ps}^{E})$ (6)

Despite Δ_ps being a majority-based operator, it can be refined as an arbitration operator by computing the minimum value from the partial satisfiability of the belief bases. With this refinement, we can choose impartially the resulting interpretations, satisfying each agent as much as possible.

4 Example scenarios

We use some basic scenarios to show the comparison of the results obtained by the three belief merging operators implemented in Merginator. First we show one of the most widely used scenario in the belief merging literature and then we show four basic examples, adding natural language descriptions for each.

Whilst solving these scenarios by hand can be time consuming and error-prone, by using Merginator this task is straightforward.

4.1 Motivating example

We will first describe Δ_Σ, Δ_GMax and Δ_ps in detail by solving an example that we have called the “Hello, World!” in belief merging. Originally appeared in [20] and explained in detail in [10], this exercise is commonly used in the description of new fusion operators.

Example 1. Database class. Consider a database class with three students. The teacher can give lessons of SQL, Datalog and O₂. He asks his students in turn to choose what they want to study. The first student wants to learn SQL or O₂ and doesn’t want to learn Datalog. The second wants to learn Datalog or O₂, but only one of them. The third wants to learn all three languages.

Considering the propositional variables P = {s, d, o} denoting the languages SQL, Datalog and O₂, respectively, the following formulae corresponds to the belief bases of each student: $\begin{matrix} K_{1} & = & (s \lor o) \land \neg d \\ K_{2} & = & (\neg s \land d \land \neg o) \lor (\neg s \land \neg d \land o) \\ K_{3} & = & s \land d \land o \end{matrix}$

Thus, the belief profile representing the belief set of the three students is: $E = {K_{1}, K_{2}, K_{3}}$

Additionally, Δ_ps requires the belief bases in DNF: $\begin{matrix} Q_{K_{1}} & = & (s \land \neg d) \lor (o \land \neg d) \\ Q_{K_{2}} & = & K_{2} \\ Q_{K_{3}} & = & K_{3} \end{matrix}$

Now let us consider how the three operators perform over this example.

4.1.1 Δ_Σ operation

As a model-based operator, Δ_Σ computes the Hamming-distance of each interpretation w_i with respect to each belief base in order to obtain the sum of the distances of the belief profile.

Table 2 shows the set of interpretations for Example 1 with the distances between interpretations w.r.t. the belief bases, and the sum of the distances linked to each interpretation w_i and the profile. Interpretations with the minimum value (marked with ∗ in the penultimate column) corresponds to the models of the Δ_Σ operator result.

Table 2
Belief merging using Δ_Σ and Δ_GMax

S D O dist (w_i, K₁) dist (w_i, K₂) dist (w_i, K₃) dist_Σ (w_i, E) dist_GMax (w_i, E)

w ₁ 1 1 1 1 2 0 3 (2,1,0)

w ₂ 1 1 0 1 1 1 3 (1,1,1)

w ₃ 1 0 1 0 1 1 2∗ (1,1,0)★

w ₄ 1 0 0 0 2 2 4 (2,2,0)

w ₅ 0 1 1 1 1 1 3 (1,1,1)

w ₆ 0 1 0 2 0 2 4 (2,2,0)

w ₇ 0 0 1 0 0 2 2∗ (2,0,0)

w ₈ 0 0 0 1 1 3 5 (3,1,1)

	S	D	O	dist (w_i, K₁)	dist (w_i, K₂)	dist (w_i, K₃)	dist_Σ (w_i, E)	dist_GMax (w_i, E)
w ₁	1	1	1	1	2	0	3	(2,1,0)
w ₂	1	1	0	1	1	1	3	(1,1,1)
w ₃	1	0	1	0	1	1	2∗	(1,1,0)★
w ₄	1	0	0	0	2	2	4	(2,2,0)
w ₅	0	1	1	1	1	1	3	(1,1,1)
w ₆	0	1	0	2	0	2	4	(2,2,0)
w ₇	0	0	1	0	0	2	2∗	(2,0,0)
w ₈	0	0	0	1	1	3	5	(3,1,1)

From Table 2, the lower distance dist_Σ is 2, so using Formula (1): $\begin{matrix} \mod (Δ_{Σ} (E)) = {w_{3}, w_{7}} = {(1, 0, 1), (0, 0, 1)} \\ or \\ Δ_{Σ} (E) = (s \land \neg d \land o) \lor (\neg s \land \neg d \land o) \equiv \neg d \land o \end{matrix}$

Hence, using Δ_Σ, Merginator recommends that the professor should teach both SQL and O₂, or O₂ alone to best satisfy the class.

4.1.2 Δ_GMax operation

As Δ_Σ, Δ_GMax computes the distance of each interpretation w_i w.r.t. each belief base in order to obtain the list of distances dist_GMax. Given the Example 1, last column of Table 2 corresponds to the list of distances in descending order dist_GMax. The lowest lexicographically value (indicated with ★) is related to the interpretations corresponding to the model of the Δ_GMax (E) merged belief base.

As shown in Table 2, the lowest distance dist_GMax is (1, 1, 0), so according to Formula \eqref ec:gmax: $\begin{matrix} \mod (Δ_{GMax} (E)) = w_{3} = {(1, 0, 1)} \\ or \\ Δ_{GMax} (E) = s \land \neg d \land o \end{matrix}$

Using Δ_GMax, Merginator thus recommends that the professor should teach both SQL and O₂ to best satisfy the class.

4.1.3 Δ_ps operation

Given Example 1, Table 3 shows the partial satisfiability of each belief base.

Table 3
Belief merging using Δ_ps

S D O w_{i
_ps} (Q_{K
₁}) w_{i
_ps} (Q_{K
₂}) w_{i
_ps} (Q_{K
₃}) $\sum_{j = 1}^{3} (w_{i_{ps}} (Q_{K_{j}}))$ ${min}_{j = 1}^{3} (w_{i_{ps}} (Q_{K_{j}}))$

w ₁ 1 1 1 $\frac{1}{2}$ $\frac{1}{3}$ 1 $\frac{11}{6} \approx 1.83$ $\frac{1}{3}$

w ₂ 1 1 0 $\frac{1}{2}$ $\frac{2}{3}$ $\frac{2}{3}$ $\frac{11}{6} \approx 1.83$ $\frac{1}{2}$

w ₃ 1 0 1 1 $\frac{2}{3}$ $\frac{2}{3}$ $\frac{14}{6} \approx 2.33 †$ $\frac{2}{3} ‡$

w ₄ 1 0 0 1 $\frac{1}{3}$ $\frac{1}{3}$ $\frac{10}{6} \approx 1.67$ $\frac{1}{3}$

w ₅ 0 1 1 $\frac{1}{2}$ $\frac{2}{3}$ $\frac{2}{3}$ $\frac{11}{6} \approx 1.83$ $\frac{1}{2}$

w ₆ 0 1 0 $\frac{1}{6}$ 1 $\frac{1}{3}$ $\frac{9}{6} \approx 1.50$ $\frac{1}{6}$

w ₇ 0 0 1 1 1 $\frac{1}{3}$ $\frac{14}{6} \approx 2.33 †$ $\frac{1}{3}$

w ₈ 0 0 0 $\frac{1}{2}$ $\frac{2}{3}$ 0 $\frac{7}{6} \approx 1.67$ 0

	S	D	O	w_{i _ps} (Q_{K ₁})	w_{i _ps} (Q_{K ₂})	w_{i _ps} (Q_{K ₃})	$\sum_{j = 1}^{3} (w_{i_{ps}} (Q_{K_{j}}))$	${min}_{j = 1}^{3} (w_{i_{ps}} (Q_{K_{j}}))$
w ₁	1	1	1	$\frac{1}{2}$	$\frac{1}{3}$	1	$\frac{11}{6} \approx 1.83$	$\frac{1}{3}$
w ₂	1	1	0	$\frac{1}{2}$	$\frac{2}{3}$	$\frac{2}{3}$	$\frac{11}{6} \approx 1.83$	$\frac{1}{2}$
w ₃	1	0	1	1	$\frac{2}{3}$	$\frac{2}{3}$	$\frac{14}{6} \approx 2.33 †$	$\frac{2}{3} ‡$
w ₄	1	0	0	1	$\frac{1}{3}$	$\frac{1}{3}$	$\frac{10}{6} \approx 1.67$	$\frac{1}{3}$
w ₅	0	1	1	$\frac{1}{2}$	$\frac{2}{3}$	$\frac{2}{3}$	$\frac{11}{6} \approx 1.83$	$\frac{1}{2}$
w ₆	0	1	0	$\frac{1}{6}$	1	$\frac{1}{3}$	$\frac{9}{6} \approx 1.50$	$\frac{1}{6}$
w ₇	0	0	1	1	1	$\frac{1}{3}$	$\frac{14}{6} \approx 2.33 †$	$\frac{1}{3}$
w ₈	0	0	0	$\frac{1}{2}$	$\frac{2}{3}$	0	$\frac{7}{6} \approx 1.67$	0

For illustration purposes, let us see the computation of the partial satisfiability for belief base Q_{K
₁} over interpretation w₃ = {1, 0, 1}. According to Formula (4): $w_{3_{ps}} (Q_{K_{1}}) = max {w_{3_{ps}} (s \land \neg d), w_{3_{ps}} (o \land \neg d)}$

w_{3_ps} (s ∧ ¬ d) is calculated using Formula (3): $\begin{matrix} w_{3_{ps}} (s \land \neg d) \\ = max {\frac{w (s) + w (\neg d)}{2}, \frac{3 - | P (s \land \neg d) |}{2 (3)}} \\ = max {\frac{1 + 1}{2}, \frac{3 - 2}{6}} = 1 \end{matrix}$

w_{3_ps} (o ∧ ¬ d) is calculated in a similar way producing 1.

Finally, partial satisfiability of belief base Q_{K
₁} over interpretation w₃ is: $w_{3_{ps}} (Q_{K_{1}}) = max {1, 1} = 1 .$

The column labelled $\sum_{j = 1}^{3} (w_{i_{ps}} (Q_{K_{j}}))$ shows the sum of the partial satisfiability of the belief profile per interpretation. The higher value (indicated with †) corresponds to the models of Δ_ps (E), representing the class best. This result match with the result of Δ_Σ operator.

Table 3 shows two interpretations resulting from the fusion: w₃ and w₇. Both interpretations maximize the desires of the class, however, the last column indicates that ${min}_{j = 1}^{3} (w_{i_{ps}} (Q_{K_{j}}))$ corresponds to the minimum of the partial satisfiability of w_{i
_ps} (Q_{K
₁}), w_{i
_ps} (Q_{K
₂}) and w_{i
_ps} (Q_{K
₃}). The interpretation with lower value of dissatisfaction in this column, w₃ (indicated with ‡), satisfies for at least two thirds of the students, in contrast to interpretation w₇, which satisfies for at least one third of each student. The result of this refinement match with the result of Δ_GMax operator, i.e. a more precise result acting as an arbitration operator.

From Table 3 the max sum is 2.33, corresponding to interpretations w₃ and w₇. But the min partial satisfiability from both interpretations corresponds to w₃. So, using Δ_ps, Merginator recommends that the professor should teach both SQL and O₂ to best satisfy the class.

As expected, the result of merging depends on the chosen operator, in this case because we have used operators with different characteristics. Δ_Σ result satisfies the majority of students, whereas Δ_GMax and Δ_ps operators have selected options that satisfy as much as possible each student. This outlines the difference between majority and arbitration subclasses and this can be seen in Merginator user interface.

4.2 Basic scenarios

The following scenarios show three examples proposed in [15], and one proposed in [1]. The first three examples can be used as a benchmark to compare results obtained by different belief merging operators. The fourth example is an exceptional case containing an inconsistent belief base.

Originally formulated using mathematical notation, we propose an intuitive meaning in natural language to solve them using the Merginator tool. Natural language translations of the first three scenarios were originally formulated in Spanish [3].

Scenario 1 Weight loss. An overweight woman consults two specialists to help her to reduce her weight. The first specialist recommends daily exercise; the second specialist recommends a balanced diet and daily exercise. The woman does not want to exercise at all. $\begin{matrix} K_{1} & = & {b} a = Balanced diet . \\ K_{2} & = & {a, b} b = Daily exercise . \\ K_{3} & = & {\neg b} \\ E_{1} & = & {K_{1}, K_{2}, K_{3}} \\ Δ_{Σ} (E_{1}) & \equiv & Δ_{GMax} (E_{1}) \equiv Δ_{ps} (E_{1}) = {a, b} \end{matrix}$ Result: Daily exercise and balanced diet.

Scenario 2 Waste management. A company needs to reach an agreement with respect to waste management. The production department believes that the company is producing waste and it should be disposed of in a nearby lake. The operations department says that if the company produces waste then they must hire a waste management contractor, and for no reason should they dispose of waste in the lake. The finance department notes that if they hire a specialist in waste management then the costs will increase, and concludes that waste must be disposed of in the lake. Quality department mentions that they should not dispose of waste in the lake. $\begin{matrix} K_{1} & = & {a, c} a = Waste production . \\ K_{2} & = & {a \to b, \neg c} b = Waste specialist \\ hiring . \\ K_{3} & = & {b \to d, c} c = Dispose of waste \\ in lake . \\ K_{4} & = & {\neg c} d = costs increase . \\ E_{2} & = & {K_{1}, K_{2}, K_{3}, K_{4}} \\ Δ_{Σ} (E_{2}) & \equiv & Δ_{GMax} (E_{2}) = {a, a \to b, b \to d} \\ Δ_{ps} (E_{2}) & = & {a, a \to b, b \to d, \neg c} \end{matrix}$ Δ_Σ and Δ_GMax result: Waste production; a specialist in waste management is hired and costs increase.

Δ_ps result: Waste production, a specialist in waste management is hired, costs increase and no waste is disposed of in the lake.

Scenario 3 Life-or-death. Three doctors in a hospital are examining a patient in critical condition. The first doctor diagnosed that the patient is about to lose his life. The second doctor says that if the patient is almost dying, then he must be subjected to surgery immediately. The third doctor diagnoses the patient is about to die, but that surgery should not be performed since the patient will not survive. $\begin{matrix} K_{1} & = & {a} a = Patient in critical \\ condition . \\ K_{2} & = & {a \to b} b = Surgery . \\ K_{3} & = & {a, \neg b} \\ E_{3} & = & {K_{1}, K_{2}, K_{3}} \\ Δ_{Σ} (E_{3}) & \equiv & Δ_{GMax} (E_{3}) = {a} \\ Δ_{ps} (E_{3}) & = & {a, a \to b} \end{matrix}$ Δ_Σ and Δ_GMax result: Patient in critical condition.

Δ_ps result: Patient in critical condition and surgery should be performed.

Scenario 4 Job future. The Human Resources department must make a decision about the future of an employee. One of the auditors says that if the employee had a professional misconduct then he must be dismissed, and the company should not provide a redundancy package. The person responsible for the department accepts that the employee was involved in professional misconduct but believes that the employee does not deserve to be dismissed, but also accepts that professional misconduct should result in dismissal. $\begin{matrix} K_{1} & = & {a \to b, \neg c} a = Professional \\ K_{2} & = & {a \to \neg b, a, b} misconduct . \\ b = Dismissal . \\ c = Redundancy \\ package . \\ E_{4} & = & {K_{1}, K_{2}} \\ Δ_{ps} (E_{4}) & = & {b, \neg c} \end{matrix}$ Δ_Σ and Δ_GMax result: Unable to compute models of inconsistent bases.

Δ_ps result: Dismissal and no redundancy package.

All three operators give the same results for Scenario 1. However, in Scenarios 2 and 3, Δ_ps operator produces a different result than the other operators. Only Δ_ps is able to solve Scenario 3. This can give us the hint than Δ_ps could be a more refined operator.

In practice, Merginator is able to solve each of these examples in less than a second on consumer hardware.

5 Adapted scenarios

We designed two more complex examples in order to evaluate Merginator further. Unlike the previous examples, these scenarios involve more belief bases with more variables, and are depicted in natural language.

Scenario 5 is based on the fictional yet popular role play called “Lost at Sea” [6]. We have restricted this decision-by-consensus challenge to five participants and we have enriched it with a set of rules representing the knowledge of each castaway.

Scenario 6 shows a decision-making exercise adapted from the Teaching and Learning for a Sustainable Future programme by UNESCO [21]. This exercise is about an enquiry into air pollution in Hong Kong. We include arguments for six participants discussing the causes—and possible solutions—to the air pollution.

Scenario 5 Lost at sea. A crew of friends is adrift on a private yacht in the South Pacific. As a consequence of a fire of unknown origin, much of the yacht and its contents have been destroyed and is now sinking. The yacht location is unclear because of the destruction of critical navigational equipment and the crew were distracted trying to bring the fire under control. The best estimate is that the yacht is approximately one thousand miles south-southwest of the nearest landmass.

The following items are intact and undamaged after the fire: sextant, shaving mirror, five-gallon can of water, mosquito netting, one case of U.S. Army C rations, maps of the Pacific Ocean, seat cushion (flotation device approved by the Coast Guard), two-gallon can of oil-gas mixture, small transistor radio, shark repellent, twenty square feet of opaque plastic, one quart of 160-proof Puerto Rican rum, 15 feet of nylon rope, two boxes of chocolate bars and a fishing kit.

The total contents of all survivors’ pockets are a packet of cigarettes, several books of matches, and five one-dollar bills.

In addition to these articles, there remains a serviceable rubber life raft with oars. The raft is large enough to carry the crew, but not all items. The crew includes:

A former policeman

A biologist

A politician

A computer scientist

A nutrition specialist

must join their knowledge while resolving their differences in order to make the best decision about which items are essential to carry on and which ones may be left behind to increase their chances of survival.

The policeman knows the essentials on survival, so he states that water, C rations, chocolate bars are critical, along with the fishing kit and the shark repellent. Also, the shaving mirror and the can of oil-gas mixture are imperative. He believes that sextant, maps, and transistor radio are not significant, neither the opaque plastic, the mosquito netting nor the rum (because he will use the oil-gas mixture to start fire, in such a case). He thinks that if the crew choose the seat cushion then they must keep the nylon rope.

The biologist wants to keep the maps and the sextant because she is hopeful to reach land using those items. She asserts that water, C rations, chocolate bars fishing kit and shark repellent are vital. She claims that only one of the rum or the oil-gas mixture is necessary. The seat cushion and nylon rope are optional items.

The computer scientist claims that if the sextant is saved then the maps are necessary for navigation, and if the radio is saved then the opaque plastic is necessary protection. He desires to save most of the items but he is skeptical about the need to save the mosquito netting, the seat cushion and the nylon rope.

The politician wants to keep all items except the sextant, the shaving mirror and the oil-gas mixture (because the life raft is motorless).

The nutrition specialist states that items to aid survival are most valuable, so water, C rations, chocolate bars are essential, along with the shark repellent. The fishing kit will be useful for fishing, including the opaque plastic or the mosquito netting (but not both). The oil-gas mixture is necessary but the rum is not; even though rum is a good source of calories, it causes dehydration. She does not have an opinion about the other items.

s = Sextant h = Shaving mirror w = Can of water n = Mosquito netting a = U.S. Army C rations m = Maps of the Pacific Ocean c = Seat cushion o = Can of oil-gas mixture r = Small transistor radio k = Shark repellent p = Opaque plastic u = 160-proof Puerto Rican rum y = Nylon rope b = Boxes of chocolate bars f = Fishing kit

$\begin{matrix} K_{1} & = & {\neg h, w, a, b, f, s, m, r, (u \land \neg o) \\ \lor (\neg u \land o), p \lor f \lor n, k} \\ K_{2} & = & {h, o, w, a, b, f, \neg u, c \to y, \\ \neg p, \neg n, k} \\ K_{3} & = & {h, o, w, a, b, f, u, s \to m, r, k} \\ K_{4} & = & {\neg h, \neg o, w, a, b, f, u, \neg s, r, k} \\ K_{5} & = & {\neg h, o, w, a, b, f, \neg u, r \to p, \\ (p \land \neg n) \lor (\neg p \land n), k} \\ E_{5} & = & {K_{1}, K_{2}, K_{3}, K_{4}, K_{5}} \\ Δ_{Σ} (E_{5}) & = & {\neg h, w, a, b, f, \neg s, m, r, \\ \neg u, o, k, \neg n} \\ Δ_{GMax} (E_{5}) & = & {\neg h, w, a, b, f, \neg s, m, r, \neg u, \\ o, k, \neg n, \neg p} \\ Δ_{ps} (E_{5}) & = & {\neg h, w, a, b, f, \neg s, m, r, \neg u, o, \\ k, \neg n, p} \end{matrix}$ Δ_Σ result: To keep the can of water, the U.S. Army C rations, the boxes of chocolate bars, the fishing kit, the maps of the Pacific Ocean, the small transistor radio, the can of oil-gas mixture and the shark repellent. To discard the shaving mirror, the sextant, the 160-proof Puerto Rican rum, and the mosquito netting. Optional items are the opaque plastic, the seat cushion and the nylon rope.

Δ_GMax result: To discard the opaque plastic, but otherwise the same as Δ_Σ.

Δ_ps result: To keep the opaque plastic, but otherwise the same as Δ_Σ.

Scenario 6 Air pollution in Hong Kong. Air pollution is a major concern of Hong Kong residents, according to various polls. As an industrial city, there are two main arguments about the issue: some think that air pollution is unavoidable if people wish to maintain a high standard of living, others argue that air pollution is serious and threats the health and quality of life of people in the city, therefore it is unacceptable.

A meeting has been called to allow stakeholders to share their different views on what should be done about the air pollution. Those invited to attend are:

An officer from the Environmental Protection Department

A representative from industry

A concerned mother

A representative of “Friends of the Planet”

A taxi-owner

A doctor

The government officer proposes the change of diesel cars to petrol and to impose stricter regulations on: (1) vehicle emissions and (2) dark smoke emissions from stationary combustion sources.

The representative of the industry wants no stricter regulations, because this will lead to inflation. He is open to other alternatives, for example, to increase the education on environmental pollution. He states that the government should improve roads and streets to help in the reduction of vehicle emissions (regulation 1), and he is at complete odds on changing the sort of machines used by industries (regulation 2).

A mother who lives in the downtown area wants any strategy that could help on the improvement of the quality of her daily life. However, she likes the convenience of modern life in Hong Kong and worries about anything that might increase the cost-of-living.

“Friends of the Planet” is an environmental organization which represents environmental concerns, those who suffer the effects of pollution, and workers in Hong Kong. Its official position is to change from diesel to petrol cars, and impose stricter regulations; or to increase environmental education, reduce the number of cars on the road, improve the sort of machines used by industries and improve the design of vehicle engines.

The attitude of the taxi owner is that diesel is a cheaper and more efficient fuel than petrol or electricity. He claims that freezing the number of vehicles would result in raised costs. It is the narrow streets which trap the fumes produced by the congested traffic; the problem is the roads not the vehicles.

The doctor has detected that people have frequently suffered from respiratory illnesses over the past few years. In areas where air pollution is high, people are more likely to suffer from heart and lung diseases. He affirms that it has recently been proved that children who have inhaled large amounts of lead dust particles from vehicle fumes have a lower level of concentration resulting from the accumulation of lead in the brain. That said, he believes that all means should be taken to reduce air pollution.

p = Change diesel cars to petrol r = Impose stricter regulations i = Inflation e = Educate the public and industries c = Reduce the number of cars on the road m = Change the sort of machines used by industries d = Improve the design of vehicle engines s = Improve roads and streets

$\begin{matrix} K_{1} & = & {p \land r, \neg s} \\ K_{2} & = & {\neg r, r \to i, e, s, \neg m, m \to i} \\ K_{3} & = & {(p \lor r \lor c \lor m \lor d \lor s \lor e), \neg i} \\ K_{4} & = & {(p \land r) \lor (e \land c \land m)} \\ K_{5} & = & {\neg p, p \to i, \neg r, \neg c, c \to i, s} \\ K_{6} & = & {p \land r \land e \land c \land m \land d \land s} \\ E_{6} & = & {K_{1}, K_{2}, K_{3}, K_{4}, K_{5}, K_{6}} \\ Δ_{Σ} (E_{6}) & \equiv & Δ_{GMax} (E_{6}) = {p, s, \neg i, e, d} \\ Δ_{ps} (E_{6}) & = & {p, r, s, \neg i, e, \neg m, \neg c, d} \end{matrix}$ Δ_Σ and Δ_GMax result: Change diesel cars to petrol, impose stricter regulations, no inflation so educate the public and industries and improve the design of vehicle engines.

Δ_ps result: Improve roads and streets, no need to change the sort of machines used by industries, and no need to reduce the number of cars on roads. Otherwise the same as Δ_Σ and Δ_GMax.

In Scenario 5, Δ_ps and Δ_GMax obtain similar results except for kipping the opaque plastic in the former and not in the latter. Intuitively, we can say that keeping the opaque plastic is a better option because the radio is kept.

In Scenario 6, Δ_ps sets all variables to True or False providing a more precise result.

These pair of scenarios take an order of minutes to be solved by Merginator on a personal computer, but it will be virtually impossible to solve by hand by an expert human within that time and with no errors.

6 Merginator: A belief merging based software prototype

Merginator is a knowledge-based system prototype implementing Δ_Σ, Δ_GMax and Δ_ps operators.

The prototype was developed and tested on an Alienware M17x™ laptop, with an Intel Core i7-2670QM CPU@2.20 GHz×8, 8 GB in RAM, 500 GB in HDD, Ubuntu Linux 17.04 64-bit and OpenJDK 7 64-bit. Merginator is a heavy-processing desktop application.

Operation of Merginator requires to first introduce the number of belief bases, the number of variables and the descriptions of both. Figures 2 and 3 show this process. Based on several tests, we placed a limit of hundreds in the number of bases, while the number of variables is limited to tens according to common processing power and memory. A belief profile including 20 variables takes around 87 minutes to be solved. A problem with 24 variables throws a out-of-memory exception.

Fig.1

Merginator program flow.

Fig.2

Input values for Example 1.

Fig.3

Input details for Example 1.

Merginator accepts arbitrary formulae as input, although it converts all given formulae to DNF, since Δ_ps requires bases in this specific format to operate. It evaluates beliefs first and then computes Δ_Σ and Δ_GMax concurrently along with Δ_ps. Finally, it outputs detailed results and the consensus of the stakeholders. Figure 1 shows the program flow.

Figure 4 shows the Merginator main screen. The top-left toolbar includes the logical operators in ρ. The bottom-left toolbar contains all propositional variables, where each variable is represented as a single letter for ease of expression. At the centre of the window stands the belief profile editor. Each row represents an individual belief base, and each belief base is built via click-and-drop with items from both tool bars.

Fig.4

Belief bases for Example 1.

Figure 5 shows the output panel. Several details are displayed: stakeholders and variables data; belief bases; truth table with models, distances, partial satisfiability and sums of Δ_Σ, refinement of Δ_ps and ordered list of Δ_GMax; tables with models of each operator; and the consensus of stakeholders.

Fig.5

Merginator results for Example 1.

Figures 2 to 5 show screenshots of Merginator solving Example 1. We solved all scenarios using Merginator, with an average time of 0.2 seconds for Scenarios 1 to 4, approximately 20 min for Scenario 5 and 3 seconds for Scenario 6.

Merginator, along with the source code, are freely available at http://github.com/chavezbosquez/merginator

7 Discussion

Belief merging is a viable alternative to solve problems that involve making decisions.

On the one hand, we provide a natural language “translation” to Scenarios 1 to 4. There is plenty of theoretical information in the literature regarding belief merging, but that is not enough to guide an inexperienced user who is interested in applying this technique to specific problems. With the translation of four basic examples used in literature we address this issue.

We also proposed two more elaborated scenarios to show the applicability of belief merging on real-world domains. With these two examples we successfully stress-tested Merginator, a user-friendly tool developed with simplicity in mind. This tool allowed us to make a comparison against the three implemented belief merging operators.

In this sense, Δ_ps differs in the first two scenarios at setting all variables and it merges inconsistent bases in the third one, which means that the refined results of Δ_ps eases the consensus decision-making to the final user.

The differences in the operator’s results are noticeable in the two larger scenarios. In Scenario 5, Δ_GMax and Δ_ps set 13 variables out of 15, but differ in one atom. Δ_Σ set 12 variables.

Scenario 6 shows a remarkable difference in results obtained by Δ_ps against the other two operators. While Δ_Σ and Δ_GMax got same results setting 5 out of 8 variables, Δ_ps sets all 8 variables in a fair consensus.

Δ_ps success lies in giving lesser number of alternatives than Δ_Σ and Δ_GMax. The goal of Merginator is to aid a final user in the consensus-seeking task, so setting the values to True or False to at most possible variables means a more precise consensus.

We propose the modelling of more practical problems and test them in Merginator.

8 Conclusion

In this paper, we implemented three belief merging operators (Δ_Σ, Δ_GMax and Δ_ps) in a single tool suitable for non-experts, called Merginator. We evaluated our tool by solving six decision-making scenarios and one “Hello, world!” example. The first four scenarios were borrowed form the literature and the remaining two are our own proposals, representing more elaborate examples.

Merginator solved effectively all the presented problems. Analysing empirically the results of each merging operator, we can say that Δ_ps is the most refined operator.

We expect that users with little experience in belief merging can get make use of Merginator and understand the overall functioning of the technique. It would be useful to have more test examples from real-world use cases to make more comparisons between the results obtained by each operator.

Further work would be to consider code optimization, the development of a complete decision support system adding a Natural Language Processing to the user interface, and the implementation of additional belief merging operators.

Footnotes

Acknowledgments

To CONACYT (Ministry of Science and Technology of México) for supporting the National System of Researchers.

References

Borja Macías

and Pozos Parra

, Implementing PS-Merge Operator . Arturo Hernández

Aguirre

, Raúl Monroy

Borja

and Carlos Alberto Reyes

García

, editors, MICAI: Advances in Artificial Intelligence, volume 5845 of Lecture Notes in Computer Science, pp 39–50. Springer

Berlin Heidelberg

2009.

Bressen

, Consensus decision making, The change handbook: The definitive resource on today’s best methods for engaging whole systems, In chapter 16, Holman

and Devane

and Cady

and Adams

W.A.

, 2007

Berrett-Koehler Publishers

212–217.

Chávez-Bosquez

and Pozos-Parra

, Modelando la toma de decisiones mediante fusión de creencias, Recta15(2) (2014), 141–158.

Chopra

, Ghose

and Meyer

, Social choice theory, belief merging, and strategy-proofness,61–79. Logic-based Approaches to Information Fusion, Information Fusion7(1) (2006).

Dubois

, Liu

, Ma

and Prade

, The basic principles of uncertain information fusion. an organised review of merging rules in different representation frameworks, Information Fusion32 (2016), 12–39.

Gordon

, Pfeiffer’s Classic Activities for Building Better Teams, 2003John Wiley & Sons, Canada, 1, https://www.vistacampus.gov/sites/default/files/legacy/87/moddata/forum/577/15751/Survival_Scenarios-_Team_building.pdf.

Gorogiannis

and Hunter

, Implementing semantic merging operators using binary decision diagrams, International Journal of Approximate Reasoning49(1) (2008), 234–251.

Kareem

S.A.

, Pozos-Parra

and Wilson

, An application of belief merging for the diagnosis of oral cancer. Applied Soft Computing;, 2017.

Katsuno

and Mendelzon

A.O.

, Propositional knowledge base revision and minimal change, Artificial Intelligence52(3) (1991), 263–294.

10.

Konieczny

and Pino

, Pérez, On the logic of merging, 98)1998, 488–498.

11.

Konieczny

and Pino

, Pérez, Merging information under constraints: A logical framework, Journal of Logic and Computation12(5) (2002), 773.

12.

Konieczny

and Pino

, Pérez, Propositional belief base merging or how to merge beliefs/goals coming from several sources and some links with social choice theory, European Journal of Operational Research160(3) (2005), 785–802.

13.

Konieczny

and Pino

, Pérez, Logic based merging, Journal of Philosophical Logic40(2) (2011), 239–270.

14.

Liberatore

and Schaerf

, Arbitration (or How to Merge Knowledge Bases), IEEE Transactions on Knowledge and Data Engineering10(1) (1998), 76–90.

15.

Lin

and Mendelzon

A.O.

, Knowledge Base Merging by Majority, In Pareschi

and Fronhoefer

, editors, Dynamic Worlds: From the Frame Problem to Knowledge Management. Kluwer, 1999.

16.

McAreavey

, Liu

and Miller

P.C.

, Computational approaches to finding and measuring inconsistency in arbitrary knowledge bases, International Journal of Approximate Reasoning55(8) (2014), 1659–1693.

17.

Perrussel

, Marchi

and Bittencourt

, Quantum-Based Belief Merging, pp. 21–30. Springer Heidelberg, Heidelberg; Berlin; 2008.

18.

Pigozzi

, Belief merging and judgment aggregation. In Zalta

Edward N.

editor, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, winter 2016 edition, 2016.

19.

Pozos Parra

and Borja Macías

, Partial satisfiability-based merging. In Gelbukh

and Kuri Morales

Á.F.

, editors, MICAI 2007: Advances in Artificial Intelligence. 6th Mexican International Conference on Artificial Intelligence, , volume 4827 of Lecture Notes in Computer Science, pp. 225–235. Springer Berlin Heidelberg, 2007.

20.

Revesz

P.Z.

, On the semantics of theory change: Arbitration between old and new information, In Proceedings of the 12th ACM SIGACT-SIGMOD-SIGART symposium on principles of databases, pp. 71–92. Association for Computing Machinery, 1993.

21.

UNESCO: Air pollution in Hong Kong. http://www.unesco.org/education/tlsf/mods/theme_d/popups/mod24t05s01.html, 2010. Teaching and Learning for a Sustainable Future programme.

22.

Viana

and Alcântara

, Priority-Based Merging Operator Without Distance Measures, pp. 398–413. Springer International Publishing Cham, 2015.

Merginator: A belief merging tool for consensus support

Abstract

Keywords

1 Introduction

2 Preliminaries

3 Belief merging

4.1 Motivating example

4.1.1 Δ Σ operation

4.1.3 Δ ps operation

5 Adapted scenarios

6 Merginator: A belief merging based software prototype

8 Conclusion

Footnotes

Acknowledgments

References

4.1.1 Δ_Σ operation

4.1.3 Δ_ps operation