We propose a new discussion game for abstract argumentation frameworks (AFs), related to, but di erent from other dialectical proof procedures and discussion games: the Skeptic's Argumentation Game (SAG). Unlike in other AF games, Player I (the Skeptic) aims to establish that an argument x is defeated, while Player II (the Optimist) tries to prove the opponent wrong, i.e., that x is accepted. If neither player has a winning strategy, the position is a draw and x's status is undecided. This “reversal of roles” (compared to the usual Proponent vs Opponent dialogue games about the acceptance status of an argument) might appear strange at rst, but has a number of important, fruitful consequences. Since SAG corresponds exactly to (i) the grounded labeling semantics of AFs, and (ii) the standard semantics of “win-move” (WM) games for normal play on nite graphs, a rich body of research and results can be transferred directly to grounded AF labelings. In this paper we show one such result transfer: The value ( / / ) of a position x in a solved WM game can be fully explained by the provenance of x, i.e., a subgraph de nable by a regular expression. Consequently, via SAG, we can provide a detailed, well-founded explanation for the acceptance status (value) of an argument. We also exploit well-founded explanations for visualization to expose the structural dependencies inherent in an AF under the grounded semantics.
Dung’s seminal work on abstract argumentation [
Defeated(x) Accepted(y)
Attacks(y, x), Accepted(y).
¬ Defeated(y).
Given an AF, i.e., a digraph GAF = (V, E) whose edges y ! x in E model that an argument y 2 V attacks an x 2 V , the rst rule states that an argument x is defeated if there is an accepted argument y that attacks x. The second rule speci es that an argument is accepted if it is not defeated. The subgoal “Accepted(y)” in the rst rule can be replaced with the negated atom from the second rule, resulting in an equivalent single-rule program:
Defeated(x)
(PAF2) (PAF1) This rule can be written equivalently in a “reversed edges” form as follows: Defeated(x)
An edge x ! y in the graph then means that argument x is attacked-by an argument y.
Now compare PAF0 with the single-rule “win-move” (WM) program from [
Move(x, y), ¬ Win(y).
The rule PWM can be seen as a game processing unit (GPU), i.e., a meta-interpreter that solves two-player games: A position x in the game, given by a graph GWM, is (objectively) won if there exists a move to a position y such that the new position is lost for the opponent. In particular, if there are no more moves left to play1 a position is lost.
It is easy to see that the game-solving rule PWM and the AF-solving rule PAF0 are “identical twins”, i.e., syntactic variants of the same generic query:
Q(x)
E(x, y), ¬ Q(y).
In other words, the variants PWM and PAF0 only di er in the interpretation of E and Q.
Solving Games with WFS. It is well known that the three-valued well-founded semantics (WFS)
of PWM solves games [
Solving AFs with WFS. Similarly, Dung has shown [
(PQ)
8
<
:
9
=
;
Research Questions. This WM-AF correspondence raises a number of interesting issues:
What is the nature of this game GWM that we can play on the (reversed) AF graph GAF0 ? At
rst glance, it seems rather counter-intuitive that an (defeated) argument x in AF should
correspond to a position in GWM! On the other hand, the simple (and “standard”) form
1In chess: Checkmate!
of GWM suggests that many classic results from game theory [
In Section 3, we solve the puzzle from above and present (iii) the Skeptic’s Argumentation
Game (SAG), a new discussion game for AF implied by the WM-AF correspondence described
above. Via the duality of WM and AF, the results developed for game provenance (Section 2)
carry over to abstract argumentation and allow us to (independently) rediscover well-established
notions and results from AF (demonstrating the robustness of these AF notions). For example,
the concept of min-max numbering of arguments, known from strongly admissible sets [
In Section 4, we present an application facilitated by our game-theoretic, provenance-aware
approach to grounded AF solutions, notably (v) a layered visualization approach, illustrated
using a well-known example from case law [
We begin by brie y describing win-move games and algorithms for solving them. We then
discuss game provenance [
Consider the graph GWM in Figure 1a, which will serve as our running example. With such a graph we can associate a “classic” (i.e., impartial two-player) game as follows. De nition 1 (Game). A (win-move) game is a nite digraph GWM = (V, E) where V is a set of positions, and edges (x, y) 2 E ✓ V ⇥ V (also denoted x ! y) represent possible moves.
After agreeing on a starting position x0 2 V , the game is played with a pebble by two players who take turns moving in rounds (a round consists of two moves). Player I starts from x0. A player can move from position x to y if (x, y) 2 E. In this case, y is a follower of x.
B.0 F.0
A play ⇡ is an alternating sequence of moves x0 ! x1 !II x2 ! · · · by the players. The I I length |⇡ | of a play is the length of the sequence. A play ⇡ is complete if either |⇡ | = 1 (repeating moves2) or ⇡ ends after |⇡ | = n moves in a terminal node. A player who cannot move loses (so-called normal play) and the opponent wins. If |⇡ | = 1 the play is a draw. Example 1. If Player I starts from position D in Figure 1a, the optimal move is to F, thereby leaving Player II stranded in a terminal node. However, the move D ! E by Player I is a blunder: it leaves Player II in a winning position (via the move E ! H). Alternatively, if Player I starts from C, regardless of their next move (which is either to D or to E), Player II can win the game.
Intuitively, the (objective!) value of a position ( , , or ) only depends on “best moves” (optimal play). In particular, “bad moves” (blunders) do not a ect the value of a position. De nition 2 (Value of a Position). A position x is if a player can force a win from x, independent of the opponent’s moves; x is if there are no moves to play or if the opponent can force a win; and x is if neither player can force a win.
A player that can force a win from a position has a winning strategy: a set of moves they can make that lead to a loss for their opponent regardless of the moves their opponent makes. Example 2. The winning strategy for a player at E in Figure 1a consists of a single move {E ! H}. The other moves from E are blunders. There are three winning strategies for a player starting at A: {A ! B}; {A ! O}; and {A ! C, D ! F, E ! H} (depending on whether the opponent moves to D or E, respectively).
Determining the value of each position results in a solved game, which is represented via a total labeling function .
De nition 3 (Solution Labeling of a Game). The (solution) labeling : V ! {W, L, D} of GWM = (V, E) yields the position values, where W, L, and D are shorthand for , , and positions, respectively. The corresponding solved game is denoted GWM = (V, E, ). 2On nite graphs, cycles are necessary (but not su cient) for a play to end in a draw.
It is well known that games can be solved by iterating the following two rules3. • (x) := L if 8 (x, y) 2 E: (y) = W. • (x) := W if 9 (x, y) 2 E: (y) = L. (RR) (GR) The red rule (RR) states that a position x is (labeled L) if all of x’s followers y have already been (labeled W): No matter which follower y of x a player moves to, the opponent can force a win from y. The green rule (GR) states that a position x is (labeled W) if at least one of x’s followers y has already been (labeled L): A player can thus choose to move from x to such a y, leaving the opponent in a lost position.
On an unlabeled graph GWM, the rst applicable rule is RR: Terminal positions have no moves
and so the RR 8 -condition is vacuously true. The result is that each such terminal position
is assigned L. In the next iteration, GR becomes applicable, assigning W to all positions that
have have at least one direct move according to the GR 9 -condition to a terminal position. The
second iteration of RR labels positions whose moves all lead to positions previously won. The
second iteration of GR then assigns labels to positions with at least one move to a lost position.
This stage-wise iteration eventually converges to a xpoint, and any remaining nodes are drawn
positions [
A game can also be solved by evaluating the rule PWM under the well-founded semantics [
The provenance P(x) represents an explanation of why and how a position x has a particular
value in a (solved) game. To compute P(x), we rst add additional provenance information,
which includes position lengths and edge labels, to solved games. We then use the provenance
information to construct the explanation P(x) as a subgraph of the solved game rooted at
x (together with the additional provenance information). Here we consider two notions of
provenance: the actual [
Solving games using either AFP or (equivalently) backward induction yields additional
gametheoretic information, notably the length (or remoteness [
De nition 4 (Position Length). Let GWM = (V, E, ) be a solved game. The length |x| of a position x 2 V is: the minimum number of moves necessary to force x’s win if (x) = W (i.e., x’s value becomes known after its rst follower is ); the maximum number of moves that 3Initially, (x) := ; for each position x 2 V . x’s losing can be delayed if (x) = L (i.e., x’s value is known after its last follower is ); and 1 (denoting in nite play) if (x) = D.
Position length corresponds to the classic game-theoretic notion of optimal play: players
try to win as quickly or lose as slowly as possible thus avoiding blunders. The length of a
position can be computed simply by using the iteration/state number in which the position’s
value becomes rst known (starting at 0) [
De nition 5 (Provenance Move Labels). Let GWM = (V, E, ) be a solved game. A provenance move labeling ⇤ : E ! {w , l , d , b} assigns labels for winning (w ), delaying (l ), drawing (d ), and blundering (b) moves, such that: 8 ><> l ⇤( x, y) := :>> bd w if (x) = W and (y) = L if (x) = L and (y) = W if (x) = D and (y) = D otherwise A solved game with move labels is denoted G⇤WM = (V, E, , ⇤) .
Not all moves are created equal. The previous de nition assigns four di erent edge types (labels) ⇤( x, y) to moves (x, y) 2 E. The edge type depends on the value (x) of the move’s origin x and the value (y) of its follower position y. Table 1 provides an overview: If a position x is won, there must be a winning move to a follower y that is lost for the opponent. Choosing any other follower (i.e., one that is drawn or won for the opponent) is a blunder. On the other hand, if x is drawn, there cannot be a lost follower (otherwise x would be winning, not drawn). Instead one must nd a drawn follower y to keep the draw. Moving to a follower that is won (for the opponent) is another kind of blunder. Finally, in a lost position x, there are no lost or drawn followers (otherwise, x would not be lost) and the only option is a delaying move to a position y that is won for the opponent.
From x | To y (W) (D) (L) winning (w ) — — (L)
(D) blunder (b) drawing (d ) —
(W) blunder (b) blunder (b) delaying (l ) Like positions, moves in a solved game are also associated with a length: De nition 6 (Move Length). Let G⇤WM = (V, E, , ⇤) be a solved game with move labels. The length |(x, y)| of a move (x, y) 2 E is: 1 + |y| if ⇤( x, y) 2 { w , l }; 1 if ⇤( x, y) = d ; and unde ned if ⇤( x, y) = b.
Move labels (edge types) are used directly to de ne the actual provenance Pac(x) of a position
x in a solved game [
Example 3. Figure 1c shows the solved game of Figure 1b with corresponding provenance move labels and lengths. Edge colors indicate corresponding labels, where primary winning moves are denoted using solid edges, secondary winning moves are denoted using dashed edges, and blundering moves are drawn using gray dashed edges.
The type graph in Figure 3a below summarizes the overall provenance structure of solved games with respect to position values and move types. The seven edge types can be split into provenance-relevant moves (winning, delaying, drawing) and provenance-irrelevant moves (three types of blunders). The winning moves can be further subdivided into fast-winning (primary provenance) and slow-winning (secondary provenance). Figure 3a (like Table 1) also shows that there are three types of “ghost moves” that cannot exist in a solved game.
For example, a position would not be lost if there were a move to a lost or to a drawn position. Similarly, a drawn x can never have a move to a lost follower y, otherwise x would be winning rather than being drawn.
Computing Provenance using RPQs. Obtaining the provenance of a position in a solved,
provenance-labeled game can be succinctly expressed using regular-path queries (RPQs) [
De nition 9 (Move-Based Regular Path Queries). The expression MR(x) evaluates to the minimal subgraph G0 ✓ G rooted at x such that all paths
x !`1 x1 !`2 x2 · · · !`n xn in G, whose concatenated labels `1`2 · · · `n match regular expression R, also match in G0.
In this way, the parameter R speci es a path expression, but unlike an RPQ which returns a set of nodes, MR(x) returns a subgraph de nable by an RPQ R. Theorem 2 (Provenance via RPQs). The actual Pac(x) and potential Ppr(x) provenance of a position x can be computed using MR (where w denotes w pr|w sc):
Pac(x) := Ppr(x) := 8 >>< >>: 8 >>< >:>
Mw.(l.w)⇤ (x) if (x) = W M(l.w)⇤ (x) Md+ (x) if (x) = L if (x) = D Mwpr.(l.wpr)⇤ (x) if (x) = W M(l.wpr)⇤ (x) Md+ (x) if (x) = L if (x) = D
Finally, we note that MR-style expressions can be used to de ne additional (path-based) queries over a game graph (e.g., to check reachability between nodes, to nd blundering paths, or to only consider secondary provenance).
We brie y recall some basic de nitions of abstract argumentation frameworks [
De nition 10. An argumentation framework (AF) is a nite digraph GAF = (V, E) where the nodes V represent arguments and edges (x, y) 2 E ✓ V ⇥ V (denoted x ! y) represent attacks.
Within an AF, a set S of arguments attacks y if y is attacked by some argument x 2 S. De nition 11. Let GAF = (V, E). S ✓ V is con ict free if no two arguments in S attack each other. An argument x is acceptable for S if every argument y that attacks x is attacked by S (S is said to defend x). S is admissible if it is con ict free and each argument in S is acceptable with respect to S.
An AF can have many admissible sets, referred to as extensions. Di erent classes of extensions give rise to di erent extension semantics.
De nition 12. For GAF = (V, E), S ✓ V is strongly admissible if every argument in S is defended by some subset S0 ✓ S \ {x} such that S0 is also strongly admissible.
An AF can also have many strongly admissible sets, the largest of which is the unique
grounded extension [
Given an AF, we can consider its extensions as the “solutions" (under the given extension
semantics) for that AF. An alternative approach is to label the arguments according to their
acceptance status [
The standard grounded game (SGG) and the grounded discussion game (GDG) are alternative
gamebased proof procedures for determining whether an argument is in the grounded extension [
SGG and GDG Compared. One could argue that SGG is conceptually simpler than GDG since the latter introduces various move types ( , , , and ).
On the other hand, SGG is computationally more expensive, as “the number of steps needed in a winning strategy of the SGG can be exponential in relation to the in/out-size of the strongly admissible labeling that the SGG winning strategy is constructing” [11, p.297].
In the following, we propose the Skeptic’s Argumentation Game (SAG), which can be seen as a variant of the SGG (e.g., w.r.t. its conceptual simplicity) but without its exponential overhead. It combines the bene ts of both approaches while also following a traditional game-theoretic set-up. In a sense, SAG is not a new game but rather a new interpretation (for grounded AF semantics) of the classic win-move game described in Section 2.
(a) the WM-graph in Figure 1a is identical to the AF-graph in Figure 2a if we reverse the attack edges (i.e., replace them by attacked-by edges); and (b) the node values in Figure 1b and Figure 1c match those in Figure 2b and Figure 2c, respectively, see Theorem 1 (WM-AF Correspondence).
As suggested in Section 1, this correspondence (or duality) implies that the reverse of the attack graph (i.e., the attacked-by graph) can be understood as a 2-player (argumentation) game that is isomorphic to the standard WM game. This allows us to directly transfer the provenance results from Section 2 to the AF setting (e.g., see the example in Figure 2c). But what is this game? B F
A C D G
O E H
K L M N
B F
A C D G
O E H
K L M N
B.0 F.0 1 1 2 A.1 3 C.2 D.1 3 G.2 2 1 2
O.0 E.1 1 H.0
K.∞ ∞ L.∞ ∞
M.∞ ∞
N.∞ ∞ (a) An attack graph GAF (b) Grounded solution GAF . . .
(c) . . . with provenance (G⇤AF)
A Skeptic’s Perspective. Player I, the Skeptic, argues that a node x in AF is a defeated argument. To this end, the Skeptic claims that there exists an attacker y in the AF-graph which itself is accepted and y attacks x (or equivalently x is attacked-by y). This corresponds to Player I choosing one of the possible moves (from x) in the game. Player II, the Optimist, begs to di er and makes the counter claim that all attackers of x are defeated, including y. Example 4 (A Skeptic’s Win). Assume the Skeptic wants to demonstrate that node D is a defeated argument in Figure 2a. The best move in SAG is to move to node F (which attacks D) and claim that F is accepted and thus D is defeated. The Optimist could try and show that F itself is defeated (so the attack F ! D wouldn’t matter), alas there are no further moves to play: No argument in AF attacks F, so its acceptance has been established and the Skeptic has proven that D is indeed defeated.
Example 5 (An Optimist’s Win). Alternatively, if the Skeptic claims that C is defeated, there must exist an accepted attacker of C. Both possible SAG moves, i.e., to the attacker D and to the attacker E can be refuted by the Optimist: D is defeated (as just shown in Example 4) so its attack on C can be ignored. Argument E is similarly defeated (via the accepted attacker H). Since all attackers of C have been shown to be defeated, the Skeptic’s claim that C is defeated has been refuted and C must be accepted: A win for the Optimist (Player II).
Looking back at Example 4, had the Skeptic chosen the move from D to E (instead of to F), this would have been a blunder: the Skeptic aims to point to an accepted attacker of D but the potential attacker E is itself defeated, so this attack cannot be used to establish the defeat of D.
As shown for (generic) win-move games in Section 2.4, one can distinguish at least seven di erent kinds of edges, i.e., not all moves are created equal: winning, losing (i.e., delaying), and drawing moves are the only provenance edges that contribute to the value of a position x ( , , or ). In contrast, blunders are moves that are not considered part of the provenance of x, as they do not contribute to x’s value. 7/10/24,8:34PM b-1 (blunder) ∃ Node:
WON |!!| ≤ 2n+1 b-3 (blunder) b-2 (blunder) SAG: A New (Old) Impartial Game. The Skeptic’s Argumentation Game (SAG) introduced above (Examples 4 and 5) employs the standard machinery of games as de ned in Section 2. SAG therefore is such a classic impartial game4, only that moves are interpreted as attacked-by edges. Consequently, via the WM-AF correspondence, the de nitions of games, solutions, the AFP-based (backward induction) algorithm, length, actual and primary provenance, and the regular provenance structure all immediately apply to this “new” argumentation game as well. The Regular Structure of AF Provenance. Si mfile:/i/Ulsaers/rludaesch/Dropbox/Travel/2024-06-Germany-and-Vienna-TaPP/Readings/graph(1)p.svgh in Figure 3b to Figure 3a, the type gra summarizes the overall provenance structure of AFs with respect to argument values and attack fitley://Upsers/ludaeschT/Drohpboex/Trasvel/20v24-e06-nGermaany-anda-Viecnnka-TaPtP/yReapdinges/gsrapha.svgre divided into provenanc1e/1-relevant attacks (successful, failed, es. e tt undecided) and provenance-irrelevant attacks (three kinds of blunders). The successful attacks are further subdivided into primary and secondary attacks (as in Figure 3a). Figure 3b also shows the three edge types that cannot exist in a grounded labeling. For example, an argument would not be accepted if it were attacked by an accepted or an undecided argument. Similarly, an undecided argument x can never be attacked by an accepted argument y, otherwise x would be defeated rather than undecided.
Graph-based visualization can help to clarify the structural context of both games and argumentation frameworks, providing insight into why a node (position or argument) has a particular value. A direct result of the duality between games and AFs is that game provenance can be exploited within AF visualizations to organize arguments within attack graphs according to the role they play in the grounded labeling. Here we show one approach for exploiting this structure in which provenance edge types are used to generate AF graph layouts that are organized into 4Using the usual normal play rule, i.e., the player making the last move wins. 1/1 4/20/24,5:41PM
AF-animal-fdp.svg U
W V
Z
Q G T
C B A
S Y H
D
X F
E
M I
J K
N O L 4/20/24, 7:57 PM
J.∞ ∞ N.∞ ∞ ∞ M.∞ ∞ ∞ O.∞
I.1 L.0 1 1
K.0
AF-animal-layered.svg E.∞
F.4 5 S.3
4 D.1 “well-founded layers”: argument clusters that a1/1 re layered according to the order their values file://Users/ludaesch/Dropbox/Reviews/2024-04-COMMA/AF-animal-fdp.svg become known in the iterative (AFP-based) comfile:/ /Users/ludaesch/Dropbox/Reviews/2024-04-COMMA/AF-animal-ulayetrede.svgthe grounded labeling.
putation used to comp
Example 6 (Bench-Capon Animal Case-Law). Figure 4a shows the AF from [
A visualization of an AF using our layered approach is de ned by four heuristics: (i) Arguments and Attacks. Each argument and attack is decorated according to the template of Figure 3b, following the general style of Figure 2c. 1/1 (ii) Layout Direction. AFs are displayed according to a layout direction (w.r.t. attack edges), which is either vertical or horizontal. Vertical layouts can be bottom-to-top (as shown in Figure 4b) or top-to-bottom. Horizontal layouts can be left-to-right or right-to-left. (iii) Layered Arguments. All arguments with the same length, except for those that are (with a length of 1 ), are displayed at the same level in the graph. Each level is drawn orthogonal to the (either horizontal or vertical) layout direction. This means that arguments with length k are aligned horizontally for a vertical layout, and vertically for a horizontal layout. Levels are displayed in order according to their lengths, e.g., level k in a bottom-to-top layout will be below level k + 1, and so on. There are ve levels shown in Figure 4b: the top-most level contains F (with length 4), followed by a level containing S (with length 3), a level containing the arguments with length 2, a level containing the arguments with length 1, and the last level containing the arguments with length 0. (iv) Layered Edges. All attacks x ! y that are labeled as either primary succeeding or else failing (see Figure 3b) are required to be displayed in the layout direction (e.g., “up-thepage” in a bottom-to-top layout). These edges represent the attacks that are relevant in the explanation of an argument’s value, as opposed to irrelevant (blunder) attacks or secondary (successful) attacks discovered after an argument’s value has already been found in the backward induction (AFP-based) computation. Additional edges are drawn as appropriate for the graph, however, they do not impact the overall layering (i.e., they are not required to follow the same layout direction constraints).
Example 7. In Figure 4b, the successful attack of H on F is a primary edge, and thus, is required to be drawn in the upward direction in the (bottom-to-top) layout. However, the attack of F on B is not required to be drawn according to the layered edge constraint since F’s value was known prior to considering the attack in the AFP-based solution (i.e., the attack is a secondary edge). The attack of D on C is irrelevant (a blunder), and in this case is drawn horizontally, since both arguments are in the same layer (i.e., they have the same length).
Given an AF and its associated provenance labelings, the above heuristics can be directly
implemented using the DOT language of Graphviz [
We have explored the duality between the win-move rule PWM and the AF rule PAF under the
well-founded semantics, giving rise to solved two-player combinatorial games and grounded
AF labelings, respectively. A discussion game has been presented which, to the best of our
knowledge, has not been studied by the argumentation community until now: In the Skeptic’s
Argumentation Game (SAG), Player I, the Skeptic, aims to establish that an argument x is defeated,
while Player II, the Optimist, tries to prove the opponent wrong and show that x is accepted.
This reversal of roles (from the more common Proponent vs Opponent in other discussion games)
appears counter-intuitive at rst, but yields a number of important results. SAG is identical to a
classic/generic impartial game (only that moves are interpreted as attacked-by edges). Therefore,
concepts and results from game theory directly carry over to AFs, e.g., backward induction,
length of positions, and prior work on the provenance of games [
A new, ne-grained classi cation of attack types has been derived from the dual edge types
in our prior work on game provenance [
Finally, we have described an application of game provenance for AFs that leverages both edge types and node lengths to visualize the well-founded explanations of an argument’s value (acceptance status). By both coloring arguments and edges according to their acceptance status, and clustering argument nodes into layers according to when their values are discovered in a backward induction, the overall “ ow of acceptance and defeat” is emphasized. This approach suggests that the dependencies of arguments can be more easily discovered within an AF visualization (e.g., when compared to force-directed or other non-semantic layout approaches).
In future work, we plan to continue to explore the duality and deep connections between
winmove games (and game-theoretic approaches in general) and argumentation frameworks started
recently [