Figure 3 shows the value-based system of Example 2 and the three associated graphical models.

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

Definition 7. *A value-based system* F = (**X, A, V, η**) *is called* bipartite if its graph structure is a bipartite graph, i.e., if X *can be partitioned into two conflict-free sets.*

## 3 Value-Width And Attack-Width

Dunne [13] suggested to consider restrictions on the number of arguments that share the same value, and the number of attacks between equivalued arguments. We state these restrictions in terms of the following notions.

Definition 8. Let F = (**X, A, V, η**) *be a value-based system. The* value-width of F is the largest number of arguments that share the same value, i.e., maxv∈V |η
−1(v)|*. The* attack-width of F *is the cardinality of the set*
{ (x, y) ∈ A | η(x) = η(y) }.

For instance, the value-based system of Example 2 has value-width 2 and attack-width 2.

Value-based systems of value-width 1 are not very interesting: Every argument x in such a value-based system is subjectively accepted (x is accepted with respect to any specific audience where η(x) is largest), and objectively accepted if and only if x is not attacked by any argument y (if y attacks x then x is not accepted with respect to any specific audience where η(y) is largest). Thus, for value-based systems of value-width 1 the problems SUBJECTIVE and OBJECTIVE ACCEPTANCE are trivial, and the expressive power of such value-based systems is very limited.

On the other hand, *value-based systems of value-width 3* are already too expressive to allow a tractable acceptance decision: Dunne [13] showed that the problems SUBJECTIVE and OBJECTIVE ACCEPTANCE are intractable
(NP-complete and co-NP-complete, respectively) for value-based systems of value-width 3, even if their graph structure is a tree.

This leaves the intermediate class of *value-based systems of value-width 2* as an interesting candidate for a tractable class. In fact, Dunne [13] conjectured that both acceptance problems are polynomial-time decidable for value-based systems of value-width 2. He also conjectured that the problems are polynomial for value-based systems with an attack-width that is bounded by a constant. We disprove both conjectures and show that the problems remain intractable for value-based systems of value-width 2 and (simultaneously) of attack-width 1.

On the positive side, we show that under the additional assumption that the value-based system is bipartite
(that entails value-based systems whose graph structures are trees) both acceptance problems can be decided in polynomial time for value-based systems of value-width 2. Theorem 1. (A) SUBJECTIVE ACCEPTANCE remains NP-hard for value-based systems of value-width 2 and attack-width 1. (B) OBJECTIVE ACCEPTANCE remains co-NP-hard for value-based systems of value-width 2 and attack-width 1. Theorem 2. (A) SUBJECTIVE ACCEPTANCE can be decided in polynomial time for bipartite value-based systems of value-width 2. (B) OBJECTIVE ACCEPTANCE can be decided in polynomial time for bipartite value-based systems of value-width 2.

In the remainder of this section we will demonstrate the two theorems.

6