η(t) = vt. Evidently F has attack-width 1 and value-width 2, and it is clear that F can be constructed from Φ in polynomial time.

We establish part (A) of Theorem 1 by showing the following claim.

Claim 1. Φ is satisfiable if and only if x1 *is subjectively accepted in* F.

Proof. First we note that every certifying path for x1 in F must have the form (x1, z1, x i1 1
, z i1 1
, x2, z2, x i2 2
, z i2 2
,
x3, z3**, . . . , x**m, zm, x imm , z imm , t) where ij ∈ {1, 2, 3} for every 1 ≤ j ≤ m and for every pair 1 ≤ **j < j**′ ≤ m there is no attack (x ij′
j
′ , x ij j
) ∈ A. Hence there exists a certifying path for x1 in F if and only if there exists a set L of literals that corresponds to a satisfying truth assignment of Φ (i.e., L contains a literal of each clause of Φ
but does not contain a complementary pair of literals).

In order to show part (B) of Theorem 1, let F be the value-based system as constructed above and define F
′ = (X′, A′, V ′, η′) to be the value-based system with 1. X′:= X ∪ {x0}, 2. A′:= A ∪ {(x1, x0)},
3. V
′:= V ∪ {v0},
4. η
′(x0) = v0 and η
′(x) = η(x) for every x ∈ X.

Part (B) of Theorem 1 follows from the following claim which follows from Claim 1 and Lemma 2.

Claim 2. Φ is satisfiable if and only if x0 *is not objectively accepted in* F
′.

By a slight modification of the above reduction we can also show the following, answering a research question recently posed by Dunne [14]. The detailed argument is given in the appendix.

Corollary 1. SUBJECTIVE and OBJECTIVE ACCEPTANCE remain NP*-hard and* co-NP-hard, respectively, for value-based systems whose value graphs are bipartite.

## 3.3 Certifying Paths And Dialogues

Bench-Capon, Doutre, and Dunne [5] developed a general *dialogue framework* that allows to describe the acceptance of arguments in a value-based system in terms of a game, played by two players, the proponent and the opponent. The proponent tries to prove that a certain argument (or a set of arguments) is accepted, the opponent tries to circumvent the proof. An argument is subjectively accepted if the proponent has a winning strategy, that is, she is able to prove the acceptance regardless of her opponent's moves.

In the following we outline a simplified version of the dialogue framework that applies to value-based systems of value-width 2. We will see that certifying paths correspond to winning strategies for the proponent.

Let F = (**X, A, V, η**) be a value-based system of value-width 2. We have two players, the proponent and the opponent, who make moves in turn, at each move asserting a new argument. This produces a sequence
(x1, y1, x2, y2 **. . .**) of arguments and a set of audiences ≤ with η(x1) = η(y2) < η(x2) = η(y2) **< . . .** . The proponent has the first move, where she asserts the query argument x1 whose subjective acceptance is under consideration. After each move of the proponent, asserting argument xi, the opponent asserts a new argument yi ∈ X \ {x1, y1, . . . , xi−1, yi−1, xi} which has the same value as xi but is not attacked by xi, and attacks some argument asserted by the proponent. If no such argument yi exists, the proponent has won the game. After each move of the opponent asserting an argument yi, it is again the proponent's turn to assert a new argument xi+1 ∈ X \ {x1, y1, . . . , xi, yi}. This argument xi+1 must attack the opponent's last argument yi, but must not attack any argument asserted by the proponent. If no such argument xi+1 exists, the proponent has lost the game. Because the value-width of F is assumed to be 2, the opponent has at most one choice for each move.

Therefore, the proponent's wining strategy does not need to consider several possibilities for the opponent's counter move. Hence, a winning strategy is not a tree but just a path and can be identified with a sequence
(x1, y1, . . . , xn−1, yn−1, xn) that corresponds to a play won by the proponent. It is easy to verify that such a sequence is exactly a certifying path.