A Boolean model for conflict-freeness in argumentation frameworks

1.   Introduction

Argumentation is a non-monotonic reasoning model based on the construction and evaluation of interacting arguments. One of the most widely studied argumentation systems is Dung's abstract argumentation frameworks (abbreviated as AF) ^[1]. An AF consists of a set of arguments and a binary attack relation between the arguments. Based on conflict-freeness and acceptability, a series of extension-based semantics is established, including admissible extensions, stable extensions, preferred extensions, etc.

The computation of argumentation semantics is critical and complex when the arguments and attacks are numerous. People explored several methods to calculate them. For example, Caminada ^[2] introduced the labelling approach, where each argument is assigned a value in the set {in, out, undecide}, and the semantics are checked according to legal principles. Liao ^[3] investigated the dynamic AFs, which reduce the computation complexity when the AF's arguments increase or reduce. Pu et al. ^[4] solved the complex problem with Boolean vectors and Boolean matrices. Cerutti et al. ^[5] summarized the Boolean satisfaction of the AFs. This paper is also a study in the Boolean approach. Its goal is to investigate a simple Boolean model for argumentation.

In this paper, an evaluation of an AF assigns each argument a value of 0 or 1. Every attack is considered as an operator between arguments. Its value is calculated according to the interpreted values of its target and its source arguments. Then, by checking the values of the attack, an evaluation can be checked to be some semantics or not. Following this idea, a Boolean model of conflict-free sets is established, where the value of each attack should be 1. Moreover, the soundness and the completeness are given.

This work provides a new Boolean method for computing conflict-free sets. It simplifies the previous Boolean methods by removing the various constraints. The calculation process avoids checking these constraints. Hence, the new method is efficient. At the same time, the idea of this method demonstrates a possible way of constructing Boolean models for other semantics. Therefore, this work is also an exploration of new methods for the Boolean solutions for AFs.

The contents are arranged as follows. In Section 2, we recall the theory of Dung's AFs and Boolean algebras. In Section 3, we introduce a Boolean algebra-based conflict-free model for an AF. In Section 4, some related work is discussed. Finally, the last section concludes.

2.   Basic knowledge

Boolean algebra has a history of more than one hundred years and has been widely applied in mathematical logic. A Boolean algebra is a tuple $(A, \wedge, \vee, \neg)$, where $\wedge$, $\vee$ and $\neg$ are operations on the set $A$. In this paper, the set $A$ is selected as $\{0, 1\}$, and the three operations are defined as follows: $\forall x, y\in \{0, 1\}$:

A Dung's AF contains a set of arguments and a set of attack relations between the arguments.

Definition 2.1. An AF is a pair $(Args, Atts)$ where $Args$ is a set of arguments and $Atts\subseteq Args \times Args$ shows the attack relation between the arguments.

For example, an attack $(A, B)\in Atts$ means that the argument $A$ attacks the argument $B$. In AF theory, $(A, B) \in Atts$ is usually denoted by $A\rightarrow B$, where the arrow symbol $\rightarrow$ is not a logic operator.

Given $S\subseteq Args$, the set $R^+(S) = \{A\in Args\colon \exists B\in S \ s.t.\ B\rightarrow A\}$ represents all the arguments attacked by $S$, and the set $R^-(S) = \{A\in Args\colon \exists B\in S \ s.t.\ A\rightarrow B\}$ represents all the arguments attacking $S$.

The semantics of AFs are based on two key notions: conflict-free sets and acceptability.

Definition 2.2. (Conflict-free sets) A set $S \subseteq Args$ is conflict-free if there are no arguments $A, B\in S$ such that $(A, \; B) \in Atts$.

Definition 2.3. (Acceptability) An argument $A\in Args$ is acceptable to (or defended by) a set $S \subseteq Args$ if for every $B\in Args$ s.t. $(B, \; A) \in Atts$, there is some $C\in S$ s.t. $(C, \; B) \in Atts$.

A variety of semantics are then established. For instance, an admissible extension is a conflict-free set of arguments which defends each argument in it; a complete extension is an admissible extension including every element it defends; a preferred extension is the maximal admissible extensions; and a stable extension is a conflict-free set which attacks each element out of it.

3.   A Boolean model for conflict-free sets

In this section, a Boolean algebra-based algorithm is presented for calculating conflict-free sets. In line with embedding proposition logic in Boolean algebra, we assign a number in $\{0, 1\}$ to each argument and then calculate a value for each attack. The same as before, 1 means valid or accepted, and 0 stands for rejection.

Definition 3.1. Given an AF $(Args, Att)$, an evaluation $e$ on it is a total function from $Args$ to $\{0, 1\}$, assigning each argument $A$ a number $e(A) \in \{0, 1\}$.

Obviously, if an AF has $n$ elements, then there are $2^n$ evaluations.

Example 3.1. Consider the AF: $A\rightarrow B\rightarrow C$, where the letters stand for arguments, and the arrows stand for attacks. There are $2^3 = 8$ evaluations from $e_1 = \{0, 0, 0\}$ to $e_8 = \{1, 1, 1\}$.

Several approaches have been introduced to check whether an evaluation $e$ is conflict-free. Here, we examine it by computing the values of all the attacks: When the values of all the attacks are 1, $e$ is regarded as conflict-free.

According to Definition 2.2, if there exists an attack $A\rightarrow B$ in an AF, then conflict-free semantics must reject at least one of $A$ and $B$. In other words, $e(A)$ and/or $e(B)$ is 0. In these cases, we assign value 1 to the attack $A\rightarrow B$ as the evaluation of this attack, as shown in Table 1. Intuitively, value 1 on an attack indicates that the status of this attack adheres to conflict-free semantics. Otherwise, when both $e(A)$ and $e(B)$ are 1, we assign number 0 to $A\rightarrow B$, meaning that given the status of arguments $A$ and $B$, $A\rightarrow B$ blocks ${A, B}$ being conflict-free.

According to the above table, the values of attacks can be calculated by a binary operator $*$ on {0, 1}, where

Therefore, we introduce the next definition for the values of the attacks.

Definition 3.2. Given an evaluation $e$ of an AF $(Args, Att)$, for each attack $A\rightarrow B\in Atts$,

Example 3.2. (Continued from Example 3.1) The evaluation in Example 3.1 can be extended to include the evaluation of the attacks, as shown in Table 2.

Given an attack $A \rightarrow B$, if a set of arguments $S$, prescribed by an evaluation $e$, is conflict-free (i.e., $\exists X \in \{A, B\}$ s.t. $X \notin S$), then we say $e$ models $A \rightarrow B$. This is captured by the following definition.

Definition 3.3. Given an attack $\alpha$ in an AF, an evaluation $e$ models $\alpha$ if its value is 1, i.e., $e(\alpha) = 1$.

Example 3.3. (Continued from Example 3.2) Obviously, $e_4$ models $A\rightarrow B$, but it does not model $B\rightarrow C$. While $e_7$ models $B\rightarrow C$, it does not model $A\rightarrow B$. The evaluations $e_1$, $e_2$, $e_3$, $e_5$ and $e_6$ model both $A\rightarrow B$ and $B\rightarrow C$.

Given an AF, if an evaluation models all the attacks, then the set of arguments prescribed by this evaluation is conflict-free. We call such an evaluation a conflict-free model.

Definition 3.4. Given an AF, a conflict-free model of the attack is an evaluation $e$ on the AF, where it models every attack in the AF.

Example 3.4. (Continued from Example 3.2) From the above table, we can see that $e_1$, $e_2$, $e_3$, $e_5$ and $e_6$ are conflict-free models, and $e_4$, $e_7$ and $e_8$ are not.

The next two theorems provide soundness and completeness of our model. They follow from the establishing process of the conflict-free models in Definition 3.4.

Theorem 3.1. (Soundness) Given an AF, let $e$ be a Boolean model of it. Then, the set $\{A\in Args\colon e(A) = 1\}$ is a conflict-free set in the AF.

Theorem 3.2. (Completeness) Given an AF, let $S$ be a conflict-free set in it. Then, the function $e: Args \longrightarrow \{0, 1\}$ defined in Eq (3.1) is a Boolean model of the AF.

4.   Discussion

Dung's AF theory has proven to be a simple and powerful theoretical analysis tool, and it has been applied in many fields of artificial intelligence, ranging from decision-making ^[6,7], multi-agent systems ^[8,9,10], input/output systems ^{[11,12,13,14]} to law ^[15], voting ^[16], etc. Theoretically, the AF theory has been developed in various ways ^[17]. For example, ^[18] studied the ranking semantics. The work ^[19] investigated AFs with support relation. The works ^{[20,21,22,23]} discussed the gradual AFs.

Boolean algebra and its extended forms ^[24,25,26] are classical tool in exploring logic semantics. The Boolean satisfaction problem is, of course, an interesting and useful topic in AF theory. Cerutti et al. reviewed previous works in Boolean approaches in ^[5]. Dung's original restrictions for each semantics are translated into a complex formula. An evaluation is a Boolean model of some semantics, if the corresponding formula is valid. Pu et al. introduced a Boolean method in ^[4] by Boolean-vectors and Boolean-matrices. Similar to other works, for each semantics, there are around four constraints to represent Dung's original conditions. Every Boolean model satisfies all the constraints.

Unlike these existing methods, our method does not translate the original conditions. On the contrary, whether an evaluation is a Boolean model is determined by the calculated attack values. When the values of all the attacks are 1, the evaluation is considered as a conflict-free model. This method avoids the steps to check the kinds of constraints. Therefore, our method simplifies the previous methods. Furthermore, this method can possibly be extended for other semantics. Hence, it provides a novel and simple idea for the establishment of Boolean models of AF semantics.

At the same time, there are some weaknesses in our work. First of all, this work is only the first step to follow this idea, and it only provides Boolean models for conflict-free sets. Second, although our Boolean conflict-free model can calculate all the conflict-free sets in an AF, its efficiency is not high. For example, if the cardinality of the arguments set is $n$, it needs to check $2^n$ evaluation functions.

5.   Conclusions

Mathematical models of propositional logic transform logic deduction into algebraic calculations. The Boolean model of an AF also connects the derivation of the semantics with computation in a Boolean structure.

This paper builds the Boolean evaluations of an AF by viewing the attack relation as a connection between arguments, which is mapped to a composite operator in the Boolean algebra. Then, the concept of conflict-free models is introduced, and the soundness and completeness theorems are given.

The main contribution is a new way to build Boolean models for argumentation. Different from the constraints in the existing works, the argument semantics can be simply checked by checking the attacks' values. Another contribution is the establishment of the Boolean models for conflict-free sets. This new model of conflict-free sets demonstrates our idea to build Boolean semantics. It also provides a foundation for further exploration of Boolean models for argumentation semantics.

In the future, we will discuss the Boolean models of other extensions, like complete extensions, stable extensions, etc. Also, the models of extended AFs can be discussed.

Conflict of interest

The author declares no conflict of interest.