Policy-Adaptable Methods For Resolving Normative Conflicts Through Argumentation and Graph Colouring

We will need tools to allow us reason about the conflicts between norms directly. To do so, we can use argumentation, a type of framework pioneered by Dung in 1995 [2]. Argumentation involves a set of arguments $A$ and an attack relation $R$ between these arguments. For two arguments $a,b\in A$, if there is a tuple $(a,b)\in R$, we say that argument $a$ attacks argument $b$. In our case, we will view each norm as an argument (and will henceforth use “norm” and “argument” interchangeably) and we will view a conflict between two norms as their corresponding arguments attacking one another. Note that we will therefore be considering attack arguments to be bidirectional — if argument $a$ attacks argument $b$, then argument $b$ attacks argument $a$. This is not usually the case in argumentation, but this assumption will simplify the remainder of this paper.

By using argumentation, we now have access to notions within the field which are used to reason about which arguments are reasonable and should be accepted and which arguments should be rejected. This will help us resolve conflicts by discarding norms we value less highly than others when a conflict arises. The following list contains some common notions within argumentation which we will be using throughout the remainder of this paper:

Note: We will use $\Omega$ to denote a subset of the set all arguments $A$. This is non-standard notation which we are adopting due to a notational conflict which will arise later in Section 2.3.

• •

  We say that a set of arguments $\Omega$ is conflict-free iff there are no arguments $a,b\in\Omega$ s.t. $a$ attacks $b$

• •

  We say that an argument $a\in A$ is acceptable wrt. a set of arguments $\Omega$ iff for any $b\in A$ s.t. $b$ attacks $a$, there exists some $c\in\Omega$ s.t. $c$ attacks $b$. That is, $\Omega$ attacks every argument which attacks $a$ (or in other words, $\Omega$ defends $a$).

• •

  We say that a set of arguments $\Omega$ is admissible iff it is conflict-free and for every $a\in\Omega$, $a$ is acceptable wrt. $\Omega$

• •

  A set of arguments $\Omega\subset A$ is a complete extension of $A$ iff $\Omega$ is admissible and for every $a\in A$ which is acceptable wrt. $\Omega$, $a\in\Omega$

• •

  A set of arguments $\Omega\subset A$ is a preferred extension of $A$ iff $\Omega$ is a maximal admissible set. That is, $\left|\Omega\right|=\max\big{\{}\left|E\right|\big{|}E\subset A\text{ is admissible wrt.\ }A\big{\}}$.

There are also other notions and types of extensions within argumentation, such as stable extensions and grounded extensions, but we will not consider these in this paper. For further reading on notions in argumentation, the reader is directed to Dung’s seminal paper [2].

Though there are various ways of representing normative conflicts, we will be using conflict graphs, put forth by Oren et al. [1]. The advantage of conflict graphs is that we can use existing work from both argumentation and graph theory to our advantage when resolving conflicts, as well as standard normative reasoning.

In standard graph theory, a graph consists of a finite set of discrete vertices $V$ (often also called nodes, as with Oren et al.) and a set of edges $E$. Each edge consists of a pair of two vertices $v,w\in V$ and can be thought of as a link or a relation between vertices $v$ and $w$. Edges may be unordered pairs $\{v,w\}$ or ordered pairs $(v,w)$ — if a graph contains ordered pairs as edges, then these edges are said to be directional, and the corresponding graph is called a directed graph, or a digraph. Directional edges represent a relation which is one-sided. On the other hand, graphs without directed edges are called undirected graphs, or simply “graphs”.

In a conflict graph, each vertex represents a norm (or an argument), while each edge represents a normative conflict between two norms. We will assume that edges are undirected — that is, whenever norm $v$ conflicts with norm $w$, norm $w$ also conflicts with norm $v$. A potential area for further work may involve directional conflicts, but we will not consider these cases in this paper.

As an example, let us consider a system where our agent Andy from before has been given the six norms we discussed in Section 1:

Norm 1: “Andy is obligated to go to work each weekday”.
Norm 2: “Andy is prohibited from disclosing confidential work information to employees of other companies”.
Norm 3: “Andy is permitted to take a day off of work if he has requested it in advance”.
Norm 4: “Andy is obligated to share information with CompanyCorp about the joint project”.
Norm 5: “Andy is obligated to immediately answer the phone when a customer calls”.
Norm 6: “Andy is obligated to attend to customers at the cash register between 10:00-11:00 each weekday”.

Here, we have that norms 2 and 4 directly conflict with one another in their statements. Whenever Andy is busy attending to customers, there is also a conflict between norms 5 and 6 since Andy would be unable to fulfil both duties at once. Therefore, the normative conflict graph would appear as shown in Figure 1. Note that we have not drawn an edge from norm 1 to norm 3 because Andy’s permission to take time off of work can override his obligation to go to work when norm 3 is applicable.

As we continue, we will use graph colouring as one of our tools to solve normative conflicts, which we will introduce in this section. Given a graph consisting of vertices and edges, the aim of graph colouring is to assign each vertex a colour such that no two vertices of the same colour are connected by an edge — typically, one tries to accomplish this using the fewest possible number of colours.

A graph colouring which uses at most $k$ colours is called a $k$-colouring, and a graph $G$ is said to be $k$-colourable if there exists a proper $k$-colouring for $G$. The minimum $k$ for which a graph $G$ is $k$-colourable is called the chromatic number of $G$, denoted $\chi(G)$. For a given colour $c$, the set of vertices corresponding to colour $c$ is called the colour class of $c$.

In general, deciding whether there exists a $k$-colouring for $k\in\mathbb{N}\setminus\{0,1,2\}$ for a graph is an NP-complete problem. Furthermore, finding the chromatic number $\chi(G)$ for a graph $G$ is an NP-hard problem [3]. As such, we will not focus on finding graph colourings which use the exact minimum number of colours. Instead, we will consider known algorithms for creating colourings which may use more colours than the chromatic number, which we will discuss later. Some examples of possible colourings for a graph can be seen in Figure 2. For further reading on graph colouring, the reader is directed to Lewis’ book on graph colouring [4].

Note that for any valid colouring of any graph, each colour class is an independent set — that is, there are no edges connecting any two vertices in the same colour class. This fact will serve as the backbone of the algorithms we will propose, where we will compare colour classes to find independent sets which correspond to the most important norms in the system.

As we continue into subsequent sections, we will use the following notation:

• •

  We will use standard graph-theoretic notation for most objects. $G=(V,E)$ will represent a graph with vertex set $V$ and edge set $E$.

• •

  When colouring any graph, one can create a bijection from the set of colours to $\{1,2,3,...,n\}\subset\mathbb{N}$, where $n$ is the number of colours being used in the graph (so $n\leq\left|V\right|$). As such, $\mathbb{N}$ will represent the space of all possible colours which can be used and $c\in\mathbb{N}$ will represent an arbitrary colour.

• •

  For a graph $G=(V,E)$, a graph colouring $\phi$ is equivalent to a function $\phi:V\rightarrow\mathbb{N}$ since each vertex maps to a colour and each colour can be represented by an arbitrary natural number. We will denote arbitrary graph colourings by $\phi$ and the set of possible graph colourings by $\Phi$.

• •

  Since $E$ represents the edge set of a graph, this notation conflicts with the standard notation for an extension or a set of arguments in argumentation (also $E$). Therefore, we will use $\Omega$ to denote a set of arguments/norms or a selected set of vertices while $E$ will represent the edge set of a graph.

• •

  We will use $A$ to denote the set of all arguments in the domain of our problem. Since we are modelling norms as arguments and arguments as vertices in a conflict graph, the set of arguments $A$ and the set of vertices $V$ represent the same objects seen through a different level of abstraction.

One example of a method for resolving normative conflicts without argumentation comes from Vasconcelos et al. [5]. They show that a normative conflict arises when any action is within scope of two conflicting norms, such as a prohibition and an obligation. That is, a conflict exists when an action is both simultaneously forbidden and obliged by some agent. Vasconcelos et al. also discuss policies for resolving conflicts, including lex posterior (where the more recent norms takes priority over less recent norms) and lex superior (where norms put forth by greater authorities take priority over others).

An appropriate example for demonstrating another type of policy comes from Horty [6], who put forth the following set of conflicting norms as a motivating example:

Here, neither lex superior nor lex posterior are applicable as we do not have information on the sources of norms nor on when they were imposed. Instead, the policy of lex specialis (where norms which are more specific than others take priority) is more suitable, since the first norm should be ignored when presented with asparagus. Straßer and Arieli [7] have used an approach based on lex specialis to resolve normative conflicts through argumentation. In their work, arguments (or sequents as they call them) are eliminated when they contain another argument which attacks them either via rebuttal (directly refuting the opposing conclusion) or undercutting (refuting one or more of the opposing antecedents).

One of our previously stated aims for creating a new framework for conflict resolution is that we wish for it to be adaptable with respect to policies. Setting this as a specific objective, we wish for our resulting system to be compatible with the policies of lex superior, lex posterior, and lex specialis.

Normative conflicts could also be resolved based on a system of trust. This bears a similarity to how one would apply lex superior, though instead of considering the amounts of authority of individuals who impose norms, we instead consider individuals based on their reputation. Examples include the work of Parsons et al. [8] [9] and of Keung et al. [10]. However, trust-based systems require more involved processes than the previously discussed policies since one would have to derive a measure of trust for each individual rather than using easily obtainable information within the system. That said, given a sufficiently adaptable system, should be possible to include trust-based policies as an “add-on” to the framework.

Similarly to how policies exist for resolving normative conflicts, there are various criteria which can be used in argumentation for determining which arguments defeat others. One such example is the weakest link criterion. Consider a system where each argument is composed of several elementary arguments, called context arguments, where the conclusion of each context argument leads to the antecedent of the subsequent context argument. Here, the weakest link criterion dictates that the strength of an argument is determined by the strength its weakest context argument [11]. Another example would be the last link criterion, where the strength of an argument is determined by the strength of its final context argument. Our framework will not consider these criteria for defeating arguments and will instead focus on policies which do not involve argumentation-based reasoning. However, an alternate system based upon ours which uses argumentation-specific criteria to decide which norms to follow may be an avenue for future work.

Other criteria for defeating arguments exist where arguments can be attacked without being defeated. For example, Amgoud and Ben-Naim [12] have proposed a system where arguments are sorted by strongest to weakest based upon how many attackers an argument has.

Some frameworks and methods for non-monotonic reasoning have later been shown to have equivalent approaches using argumentation. For example, Liao et al [11] showed that using a “greedy” approach for creating an extension using the weakest link criterion creates a set of conclusions identical to those of an approach by Brewka and Eiter [13] from 17 years prior. It is expected that these parallels between argumentation and non-monotonic logic should exist, since it has been shown that Dung’s argumentation framework is equivalent to classical logic with the addition of the Peirce-Quine dagger (i.e. the “NAND” operator) [14]. As such, approaches with and without argumentation should not be seen as mutually exclusive, with various degrees of overlap existing between different approaches. Therefore, by applying argumentation to normative conflict resolution, loss of detail or generality should not be considered a major concern.

It should be noted that the approaches featured in [11] and [13] require the existence a preference relation over context arguments, which could be derived using policies as in Section 3.1, or they could be given a priori. Other argumentation-based systems, such as those of Modgil and Luck [15], do not require an a priori relation, while other systems which do not involve argumentation also do not require an a priori relation [5]. We can therefore see that whether or not one chooses to involve argumentation in a system or framework does not directly impose a requirement (or lack thereof) for an ordering to be given as a component of the system. However, it is more advantageous to have this relation be derived as a part of the system. As explained by Modgil and Luck, “flexible and adaptive agents need to engage in motivational argumentation over the respective merits of goals. Therefore, argumentation frameworks in which preferences […] are ‘given’, and not themselves subject to reasoning, do not suffice.” [15]. We will follow this philosophy with our own framework, aiming to use preference orderings which can be derived from the properties of norms and arguments, rather than relying on orderings given a priori.

Now that we have access to both graph colouring and conflict graphs, we can use these two tools to begin to solve normative conflicts. Now assume we have an arbitrary heuristic function $h:G\times\Phi\times\mathbb{N}\rightarrow\mathbb{R}$ — calling $h$ would appear in the form $h(G,\phi,c)$. That is, $h$ takes a graph, a colouring, and a colour as inputs and evaluates the overall importance of the set of norms corresponding to the given colour by returning a real number.

Let us now introduce our first new algorithm ColourResolve in Algorithm 1, which uses graph colouring, conflict graphs, and an arbitrary heuristic to resolve normative conflicts.

ColourResolve first creates a colouring using an arbitrary graph colouring algorithm (we will discuss this further later). On line 1, it then uses the given heuristic to find the colour which maximises the heuristic value, then assigns this to the variable $c_{\text{best}}$. On line 4, it finds the subset of vertices $V^{\prime}\subset V$ corresponding to the colour $c_{\text{best}}$. On line 1, the norms corresponding to the vertices with colour $c_{\text{best}}$ are found, which are then returned on line 1. ColourResolve always produces an admissible set, which we will now prove.

Since both the graph colouring algorithm and heuristic in Algorithm 1 are arbitrary, ColourResolve is flexible and can be adapted to suit the needs of the situation at hand. For example, one could use advanced graph colouring algorithms to minimise the number of colours used in the graph, which would thereby maximise the number of vertices corresponding to any given colour — this would therefore maximise the number of norms which are admitted at the end of the algorithm. Alternatively, one could use simpler graph colouring algorithms to save computational time. As an example of a polynomial time algorithm one could use, we will briefly outline the DSatur algorithm [16], which has worst-case running time $\mathcal{O}(n^{2})$ [4]. This was first put forth by Brélaz in 1979 [16] and can be seen in Algorithm 2.

Here, the degree of saturation of a vertex $v$ refers to the number of coloured vertices $v^{\prime}$ with an edge $(v,v^{\prime})$ or $(v^{\prime},v)$. DSatur prioritises colouring vertices with the highest degree of saturation, thereby focusing on assigning colours to vertices which have the fewest colour options available. Ties are broken by selecting the highest-degree vertex, allowing DSatur to focus on vertices which impose the most constraints upon other vertices. The intended purpose of this example is to show the reader a powerful yet intuitive graph colouring method.

To demonstrate the flexibility of using arbitrary heuristics, we will now define some possible heuristics one could use with ColourResolve. Definition 1 defines a version of lex posterior adapted for use as a heuristic and Definition 2 defines an adapted version of lex superior. Definition 4 defines a heuristic which selects the colour class corresponding to the greatest number of vertices and therefore admits the greatest number of norms.

The heuristic $h_{\text{pos}}$ finds the number of times any argument corresponding to a vertex with colour $c$ defeats another argument by being declared earlier.

Our definition of $h_{\text{pos}}$ checks for an edge “$\{v,v^{\prime}\}\in E$”. If we were to generalise our methods to directed graphs, then this edge could either be $(v,v^{\prime})$ or $(v^{\prime},v)$, where we would accept either option. We do not need to check the colour of each vertex $v^{\prime}$ which each $v$ attacks since no two vertices with the same colour can be connected by an edge.

One could further modify this definition by subtracting the number of times each argument corresponding to a vertex with colour $c$ is defeated by another argument. In section 5 later, we will perform empirical evaluations on our newly proposed algorithms. There, we will use the modified version of this definition (and similarly modified versions of other definitions in this section). However, the version shown in Definition 1 is simpler to state, which is why this definition has been declared in this way.

The preference relation $\succ_{\rho}$ is defined by a weak ordering defined as follows:

This relation is a simplified version of one used by Vasconcelos et al. [5, Section 7]. Again, as with our definition for lex posterior, we check for edges going in both directions — $(v,v^{\prime})$ and $(v^{\prime},v)$. We can also modify the definition by subtracting the number of times each argument with the specified colour is defeated.

In fact, this preference relation can be generalised to fit any preference ordering over vertices in a conflict graph, and new policies can be created when and where necessary. Definition 3 gives a generalised version of Definitions 1 and 2 which is compatible with any weak ordering over all vertices in the conflict graph.

We see that Definition 3 becomes equivalent to Definition 1 if the given weak ordering depends only the time at which norms were declared. It also becomes equivalent to Definition 2 if the given weak ordering depends only on the power of the authority who imposed the given norm. We can also see that Definition 3 generalises lex specialis if the given weak ordering is defined by the following:

…where ant($x$) is the set of antecedents of $x$ for any argument $x$ (or in the case of a norm, ant($x$) corresponds to the requirements for norm $x$ to come into effect).

Since we have shown that $ColourResolve$ is compatible with lex posterior, lex superior, and lex specialis, we have met our criteria for showing that our system is adaptable with respect to conflict resolution policies. In later sections, we will be modifying $ColourResolve$, but as long as the system continues to use the notion of heuristics, it will remain policy-adaptable.

There is one more heuristic of note which we will define before we consider it further in Section 4.3. This heuristic selects the colour class which corresponds to the greatest number of vertices overall, and can be seen in Definition 4.

Upon inspection, it may appear that using the $h_{\max}$ heuristic with a suitable graph colouring algorithm for ColourResolve would produce a preferred extension. Intuitively, both the preferred extension and the $h_{\max}$ heuristic aim to maximise the number of arguments which are admitted. This certainly is the case with the graph and the colouring shown in Figure 2(b), where the colouring is both optimal and corresponds to a preferred extension under $h_{\max}$. However, although $h_{\max}$ has the potential to often produce a preferred extension, this is not always the case.

Consider the graph shown in Figure 3(a) – let us arbitrarily call this graph $G_{6}$ since it has 6 vertices. It is possible to create a valid 3-colouring for $G_{6}$, which can be seen in Figure 3(b). Furthermore, it is impossible to colour $G_{6}$ using only two colours since $G_{6}$ contains a fully-connected subgraph with three vertices. In other words, $G_{6}$ contains “triangles”, and these cannot be coloured with two colours since at least one vertex of the triangle would neighbour a vertex with a colour which matches its own. Therefore, the 3-colouring shown in Figure 3(b) uses the optimal number of colours ¹¹1Here, we say that $G_{6}$ is 3-chromatic and that $\chi(G_{6})=3$.. By using ColourResolve on $G_{6}$ with heuristic $h_{\max}$ and an exact graph colouring algorithm, we would admit exactly two arguments — those corresponding to either red, green, or blue.

If we now consider Figure 3(c), we can see that $G_{6}$ contains a vertex subset of three disjoint vertices, shown in grey. If we consider $G_{6}$ to be a conflict graph, then these grey vertices would correspond to a preferred extension of the corresponding set of arguments. If we wished to colour the graph in Figure 3, we would need one colour for the three grey vertices, then another distinct colour for each of the three remaining vertices. This would give a 4-colouring, which is sub optimal.

Therefore, an exact graph colouring algorithm used with $h_{\max}$ on a problem with $G_{6}$ as its conflict graph would admit two arguments, but a preferred extension would contain at least three arguments. So ColourResolve does not always find a preferred extension when using an exact colouring.

This example serves to show that although ColourResolve is highly versatile, there are situations where the results it produces differ from those of preferred semantics. The caveat here is that we assume that using an exact graph colouring algorithm will allow us to admit the highest possible amount of arguments with heuristic $h_{\max}$, but this may not always be the case. For example, it may be possible that other sub-optimal graph colouring algorithms would assign all vertices in the independent set in Figure 3(c) to a single colour while assigning each of the remaining vertices their own unique colours. This would create a 4-colouring of $G_{6}$ and would allow heuristic $h_{\max}$ to admit three vertices despite the colouring being sub-optimal. We can therefore see that colouring corresponding to other types of extensions exist, but to find them would depend on the colouring algorithm one uses.

Although a preferred extension is not guaranteed with ColourResolve, it is straightforward to guarantee a complete extension by modifying our algorithm. To do so, we will now introduce a variant of ColourResolve called ColourResolveComplete, which can be seen in Algorithm 3.

The difference between our new algorithm and our original algorithm is the addition of lines 3-3. Here, we loop through each vertex in the conflict graph. For each vertex $v$, we check whether there exists a neighbouring vertex, say $w$, such that $\{v,w\}\in E$ and $\phi(w)=c_{\text{best}}$. If no such $w$ exists, then we replace the colour of $v$ with the colour $c_{\text{best}}$. Note that our colouring $\phi$ will always remain valid since we have checked for conflicts between neighbouring vertices before changing any colours. We will now prove that ColourResolveComplete always produces a complete extension.

The proof of Proposition 2 is independent of the order in which we consider vertices to be recoloured, so we will obtain a complete extension regardless of this order. One could iterate through verices in a random order, create an ordering using the heuristic function, or through any other method. However, the complete extension created as a result may be different depending on the method used. Additionally, we cannot recolour all vertices simultaneously since recolouring one vertex may cause another to become the neighbour of a vertex with colour $c_{\text{best}}$.

So far, we have resolved normative conflicts by completely omitting one of the two conflicting norms. As such, only a single colour in the colourings we create is of any value to us in creating the output of the algorithms we have used so far. In this section, we will admit norms corresponding to multiple colours into our algorithm’s output, making the advantages of involving graph colouring more apparent.

We have so far used our heuristic function to find a best colour, but we can easily extend this to find an entire preference relation over all colours. We would define this preference relation for two colours $c_{1},c_{2}\in\mathbb{N}$ as $c_{1}\succeq c_{2}$ iff $h(c_{1})\geq h(c_{2})$. From this, for any $k$-colouring, we can infer a weak ordering of colours $(c_{1},c_{2},...,c_{k})$ where $c_{1}\succeq c_{2}\succeq...\succeq c_{k}$.

With this ordering, we can first admit all arguments corresponding to our most preferred colour, then those corresponding to the next most preferred colour, and so on, until we have admitted as many arguments as possible. However, a key issue arises here in that we cannot admit two conflicting arguments with our current set of tools — this is where we will need curtailment.

Our inspiration for curtailment comes from Vasconcelos et al. [5, Definition 10]. In their work, curtailment is defined rigorously for constraining one norm with respect to another. Their framework takes into account the times at which norms were declared, when norms come into effect, and when norms expire, and they therefore introduce a robust definition of curtailment which utilises these factors. However, we will consider curtailment to be a generalised concept to keep our framework as broadly applicable and as abstract as possible. Given two conflicting norms, norm 1 and norm 2, we will consider the curtailed variant of norm 2 with respect to norm 1 to be as follows:

Whenever norm 1 is applicable and it is possible to abide by norm 1, then ignore norm 2. Else, abide by norm 2.

Replacing a norm with its curtailed version eliminates the conflict between the two corresponding norms and therefore removes an edge from the conflict graph. The concept of curtailment can also be viewed as another form of contrary-to-duty obligations, where an agent must abide by a secondary norm whenever some primary norm cannot be followed.

As an example, let us consider two norms with time dependencies. Norm $x_{1}$ says “Between 09:00 and 17:00, Agent 1 should focus on work tasks”. Norm $y$ says “Between 12:00 and 13:00, Agent 1 should take a lunch break”. By curtailing norm $x$ wrt. norm $y$, we obtain a new norm $x_{2}$ which does not conflict with $y$. Here, $x_{2}$ would say “Between 09:00 and 12:00, and between 13:00 and 17:00, Agent 1 should focus on work tasks”. Figure 4(a) shows norms $y$ and $x_{1}$ in a timeline, where we can see a conflict between 12:00 and 13:00. Figure 4(b) shows norms $y$ and $x_{2}$, where the normative conflict has been resolved through curtailment. This allows the agent to follow norm $y$ (take a lunch break) when it is applicable whilst also following norm $x_{1}$ at all other times. One could view this example as an application of lex specialis since we have prioritised norm $y$ over norm $x_{1}$ as it specifies a narrower time interval.

With curtailment in place, we are now ready to introduce an algorithm which uses every colour in the conflict graph. This can be seen in Algorithm 4, which shows ColourCurtail.

The algorithm starts in the same way as ColourResolve and ColourResolveComplete by creating a $k$-colouring on line 4. However, rather than admitting only the vertices corresponding to a specified colour, we iterate over colours on line 4. Line 4 tells us that we iterate over colours in descending order of value according to our heuristic. On line 4 we select the set $V^{\prime}\subset V$ of vertices corresponding to the colour on the current iteration of the main loop.

On lines 4 and 4, for each vertex $v$ with the colour in question, we find each vertex $w$ with an edge connected to $v$ where $w$ is already admitted into the final set $\Omega$. Since $w$ is already admitted and $w$ is attacking $v$ or vice versa, either $w$ or $v$ must be curtailed with respect to the other. Since $w$ corresponds to a more valuable colour than $v$, we should curtail $v$ with respect to $w$, which we do on line 4. Since all arguments corresponding to the current colour are curtailed with respect to all arguments admitted so far, we can now admit all arguments which correspond to the current colour, which we do on line 4. Each time new arguments are admitted, the set $\Omega$ remains conflict-free since each possible conflict has been considered beforehand.

With this algorithm, every argument is eventually admitted into the final set, but some may be completely curtailed to the point of having no effect. For example, if we consider our previous example in Figure 4, we curtailed norm $x_{1}$ wrt. norm $y$. However, if we were to instead curtail norm $y$ wrt. norm $x_{1}$, then norm $y$ would no longer have any effect. However, ColourCurtail would seek to minimise situations where a higher priority norm is curtailed wrt. a lower priority norm since colour classes are considered in descending order of preference according to our heuristic.

As we did with ColourResolve, we can make ColourCurtail more robust by “completing” each colour class when we consider it. This results in our final algorithm, ColourCurtailComplete, which can be seen in Algorithm 5. This utilises all techniques we have seen so far by creating a colouring, iterating through colour classes in descending order of preference, then admitting each colour class with curtailment. The difference between ColourCurtailComplete and ColourResolveComplete is that when we try to complete a colour class with ColourCurtailComplete, we only consider vertices which do not correspond to a colour which has already been admitted into the final set.

On the first iteration of ColourCurtailComplete, a set equivalent to ColourResolveComplete is created, meaning that this set is a complete extension according to Proposition 2. However, on subsequent iterations, we continue to admit further norms into the set. Therefore the set created by ColourCurtailComplete does not fit into notions defined within argumentation (since we have directly altered the norms/arguments by curtailing them), but is nonetheless a superset of a complete extension.

Since ColourCurtailComplete in Algorithm 5 is the most robust algorithm out of those we have introduced, let us informally derive its computational complexity.

Suppose we use a graph $G=(V,E)$ as an input into ColourCurtailComplete, where $\left|V\right|=n$ for some $n\in\mathbb{N}$. Then in the worst-case scenario, we would use one colour for each vertex, creating an $n$-colouring. This would mean that the loop on line 5 would be executed $n$ times. Within this loop, on line 5 we would consider at most $n$ vertices. However, the other inner loop on line 5 is more computationally expensive. Here, we would consider at most $n$ vertices, then for each of these vertices we would consider at most another $n$ vertices (which would happen when the vertex in question is connected to every other vertex via an edge).

Therefore, the worst-case computational complexity of ColourCurtailComplete is dependent on three nested loops, each of which considers at most $n$ items, so the complexity is $\mathcal{O}(n\times n\times n)=\boldsymbol{\mathcal{O}(n^{3})}$. This result assumes that we are not constrained by the complexity of our graph colouring algorithm (as would be the case with DSatur, for example, which has worst-case running time $\mathcal{O}(n^{2})$).

Oren et al. [1] evaluated the performances of three heuristics for admitting norms with conflict graphs. The first heuristic, random drop, created a conflict-free set by repeatedly selecting a random edge in the conflict graph, then dropping the edge — this process repeats until the graph is conflict-free. The second heuristic, maximal conflict-free set, found the conflict-free set which was maximal wrt. the number of norms it contained, with ties being broken randomly. The final heuristic, preferred extension, found a preferred extension with the conflict graph, then admitted all norms corresponding to arguments in the extension.

These heuristics were evaluated by generating a system of 16 norms. The total number of (directional) conflicts between these norms ranged from 1 to 240 (²²2Though not explicitly discussed by Oren et al., 240 is the maximum number of edges possible in a directed graph with 16 edges. An undirected graph with $n$ vertices may have up to ${n\choose 2}$ vertices, so an undirected graph with 16 edges has ${16\choose 2}=120$ edges. We call a graph with the maximal number of edges a complete graph. A complete directed graph with 16 vertices has twice as many edges, giving 240 total.). For each possible number of conflicts, 10 trials were run for each of the three heuristics and the average number of norms admitted over these 10 trials was recorded. The results can be seen in Figure 6.

Oren et al. also point out that as the number of conflicts increases, the number of norms admitted goes down for all three heuristics.

By following the same methodology as Oren et al., we can obtain a direct comparison between the performances of $ColourCurtail$ and $ColourCurtailComplete$ and the performances of the heuristics proposed by Oren et al.

Although Oren et al. use directed graphs and our algorithms are built for undirected graphs, we can still obtain a direct comparison by allowing directed edges and treating them as though they were undirected. This way, we can go up to 240 edges in our graph. All other hyperparameters for our trials will remain the same as with Oren et al.; the graph will always have 16 vertices, edges will be randomly picked, and each number of edges will be trialled 10 times for each algorithm before the average is taken.

First, let us consider $ColourCurtail$. In Section 4.2, we showed that the policies of lex superior, lex posterior, and lex specialis can all be characterised in our algorithm by an arbitrary weak ordering. As such, we will consider the performance of our algorithm for both a weak ordering (Def. 3) and a heuristic which selects the largest colour overall class (Def. 4). Without loss of generality, a weak ordering was defined over the 16 norms by assigning each norm a unique integer representing their value from 1 to 16. We will use Brélaz’s DSatur algorithm [16] (Algorithm 2) for graph colouring. By following this methodology and the methodology of Oren et al. we obtain results which can be seen in Figure 7

As with Figure 6, we can see in Figure 7 that as the number of conflicts increases, the number of norms admitted decreases as expected. To obtain a direct comparison between our results and those of Oren et al., we can overlay Figures 6 and 7 directly — the results of doing so can be seen in Figure 8 ³³3This was achieved by plotting our results over the same intervals as Oren et al. in each axis. GIMP, a photo manipulation program, was then used to scale raster images of the axes directly on top of one another before duplicate elements were erased..

Figure 8 shows us that $ColourResolve$ outperforms the random drop heuristic in terms of number of norms admitted both when using a weak ordering and the maximal colour class heuristic. The amount of norms admitted when using the maximal colour class heuristic appears to be approximately on par with the maximal conflict-free set heuristic by Oren et al. This is encouraging as it shows that our use of graph colouring has not restricted us to only being able to select sets which are significantly smaller than the largest independent set (though as discussed in Section 4.3, there are cases where restrictions exist). When using weak orderings, $ColourResolve$ was marginally outclassed by the maximal conflict-free set heuristic in terms of number of norms admitted — however, this is to be expected since the weak ordering heuristic’s strength comes from being able to admit the most important norms rather than the greatest overall number of norms. We can also see that the weak ordering and maximal colour class heuristic were both outperformed by the preferred extension heuristic, which as explained earlier in this section, is wholly expected

Let us now consider the performance of $ColourResolveComplete$. We know that $Colour\allowbreak Resolve\allowbreak Complete$ will always admit either the same amount of norms or more than $Colour\allowbreak Resolve$ when given the same heuristic. By following the same evaluation procedures, we obtain results which can be seen in Figure 9. In particular, Figure 9(b) shows these results laid over those of Oren et al., as we did earlier. Again, we see that $ColourCurtail$ performs roughly similarly to the maximal conflict-free set heuristic when we use the maximal colour class heuristic. However, a key difference compared to $ColourResolve$ is that when we use a weak ordering as a heuristic, the number of norms we admit is roughly similar to the amount admitted under the maximal conflict-free set heuristic. Therefore, we can see that by “completing” our set of admitted norms, the number of newly added norms is greatest when we use a weak ordering, so heuristics based on weak orderings benefit the most from completion.

We have so far compared our results to those of Oren et al. by using the same methodology. We can also do some brief comparisons between the algorithms we have presented so far. Figure 10 shows a direct comparison between the performances of $ColourCurtail$ and $Colour\allowbreak Curtail\allowbreak Complete$. The number of norms admitted is roughly the same for each algorthim under the maximal colour class heuristic, which serves to reaffirm our hypothesis that completing the admitted set is most beneficial when using a weak ordering. We can also see that the benefits of doing so are most pronounced when we have fewer conflicts between norms — this is to be expected, since it is easier to append more norms to the admitted set if there are fewer conflicts preventing us from doing so.

We can also observe that the maximal colour class heuristic appears to admit approximately the same number of norms under $ColourResolve$ and $ColourResolveComplete$, meaning that fewer extra norms are admitted by completing the colour class. This implies that, in practice, the largest colour class in a graph is often equal to the maximal independent set of vertices despite this not being a mathematical certainty.

Our evaluation has so far focused on the number of norms admitted by each algorithm. However, this metric neglects the importance of each norm when we use a weak ordering. We can evaluate this by using the same methodology we have been using throughout this section, though instead of counting the number of vertices admitted, we will count the number of times each norm we admit is more preferred than a conflicting norm which was not admitted. In other words, we will measure the value of the arbitrary weak ordering heuristic over the set of norms we admit. Further to this, the number of times each vertex in the set is less preferred than a conflicting vertex, we will subtract 1 from the heuristic’s value. This way, the sum of the heuristic values over all norms is 0, so we can judge the worth of an admitted set of norms by how much greater is value is than 0.

Since we are no longer following the methodology of Oren et al., we will no longer allow two edges between each vertex in the conflict graph and we will run 250 trials per number of edges rather than 10 trials. The results of measuring the heuristic values for $ColourResolve$ and $ColourResolveComplete$ can be seen in Figure 11(a). Additionally, Figure 11(b) shows the same results, except where the score of the admitted set is measured as an average over the admitted vertices.

Surprisingly, we can see that using $ColourResolveComplete$ rather than $ColourResolve$ did not result in a change in either the per-vertex score or the overall score of the set of admitted norms. We can also see from Figure 11(b) that the average score per vertex approaches 15 as the number of conflicts approaches its maximum of 120. This is as expected since when we have 120 conflicts, every norm conflicts with every other norm. The heuristic will therefore choose the most preferred norm in the whole set — this outranks every other norm in the weak ordering and therefore scores 15 by scoring 1 in each of its conflicts. On the other hand, when there are very few conflicts, the average score per vertex is near 0. This is to be expected since in this case we are likely to admit a large number of norms, only a few of which are involved in any conflicts.