

![0_image_0.png](0_image_0.png)

Figure 2: Acyclic abstract argumentation system relative to the six specific audiences on values **T, S, E**.

## 2.3 Computational Problems For Value-Based Systems

We consider the following decision problems.

SUBJECTIVE ACCEPTANCE
Instance: A value-based system F = (**X, A, V, η**) and a query argument x1 ∈ X.

Question: Is x1 subjectively accepted in F?

OBJECTIVE ACCEPTANCE
Instance: A value-based system F = (**X, A, V, η**) and a query argument x1 ∈ X.

Question: Is x1 objectively accepted in F?

As shown by Dunne and Bench-Capon [15], SUBJECTIVE ACCEPTANCE is NP-complete and OBJECTIVE AC-CEPTANCE is co-NP-complete. Indeed, there are k! possible specific audiences for a value-based system with k values. Hence, even if k is moderately small, say k **= 10**, checking all k! induced abstract argumentation system becomes impractical. Dunne [14] studied properties of value-based systems that allow to reduce the number of audiences to consider.

## 2.4 Graphical Models Of Value-Based Systems

In view of the general intractability of SUBJECTIVE ACCEPTANCE and OBJECTIVE ACCEPTANCE, the main decision problems for value-based systems, it is natural to ask which restrictions on shape and structure of valuebased systems allow tractability.

A natural approach is to impose structural restrictions in terms of certain graphical models associated with value-based systems. We present three graphical models: the *graph structure* (an undirected graph on the arguments of the value-based system under consideration, edges represent attacks) the *value graph* (a directed graph on the values of the value-based system under consideration, edges represent attacks) and the *extended graph* structure (an undirected graph on the arguments of the value-based system under consideration, edges represent attacks and "equivaluedness"). The concept of value graphs was recently introduced and studied by Dunne [14]. The concept of *extended graph structures* is our new contribution.

Definition 6. Let F = (**X, A, V, η**) be a value-based system.

The graph structure of F *is the (undirected) graph* GF = (**X, E**) whose vertices are the arguments of F and where two arguments **x, y** are joined by an edge (in symbols xy ∈ E) if and only if X *contains the attack* (**x, y**) or the attack (**y, x**).

The value graph of F *is the directed graph* Gval F = (**V, E**) whose vertices are the values of F and where two values **u, v** are joined by a directed edge from u to v *(in symbols* (**u, v**) ∈ E*) if and only if there exist some* argument x ∈ X *with* η(x) = u, some argument y ∈ X *with* η(y) = v*, and* (**x, y**) ∈ A.

The extended graph structure of F *is the (undirected) graph* Gext F = (**X, E**) whose vertices are the arguments of F *and where two arguments* **x, y** *are joined by an edge if and only if* (x, y) ∈ A or η(x) = η(y).