The Skeptic’s Argumentation Game or: Well-Founded Explanations for Mere Mortals

The Skeptic’s Argumentation Game or: Well-Founded Explanations for Mere Mortals pp 104-118 by Shawn Bowers, Yilin Xia, Bertram Ludäscher

Preasented at: SAFA 2024: Systems and Algorithms for Formal Argumentation 2024

Proceedings of the Fifth International Workshop on Systems and Algorithms for Formal Argumentation, co-located with 10th International Conference on Computational Models of Argument (COMMA 2024). Hagen, Germany, September 17th, 2024.

1. 1
The Skeptic’s Argumentation Game or:
Well-Founded Explanations for Mere Mortals
Shawn Bowers2 Yilin Xia1 Bertram Ludäscher1
1 School of Information Sciences, University of Illinois, Urbana-Champaign, IL, USA
2 Department of Computer Science, Gonzaga University, WA, USA
[email protected]
{ludaesch,yilinx2}@illinois.edu

2. Outline
1.Pop Quiz: What’s this??
2.Lost Family Connec/ons & WM-AF Duality
3.Solving Games (& Provenance Structure)
4.The SkepAc’s ArgumentaAon Game (SAG)
5.Visualiza/on as Explana/on
6.Summary & Future Work
2

3. Pop Quiz: What’s in this query?
Q(X) :- E(X,Y), not Q(Y).
•Declarative semantics?
•Positive
•Stratified
•Unique three-valued well-founded model: M
•Set of stable models (answer sets) S1, …, Sn (n ≥ 0)
3

4. Pop Quiz: What about these?
•Q(X) :- E(X,Y), not Q(Y). (PQ)
•Win(X) :- Move(X,Y), not Win(Y). (PWM)
•Defeated(X) :- Attacks(Y,X), Accepted(Y). (PAF2)
Accepted(X) :- not Defeated(X).
•Defeated(X) :- Attacks(Y,X), not Defeated(Y). (PAF1)
•Defeated(X) :- Attacked_By(X,Y), not Defeated(Y).(PAF’)
4Correspondence (Duality): Q(X) ~ Win(X) ~ Defeated(X)

5. Win-Move ~ AF Correspondence (Duality)
5
If the grounded labeling of a AF graph is equivalent to a WM game – what is this game??

6. 6
Solving the Example

7. Solving the Example: State [0]
7

8. Solving the Example: State [1]
8

9. Solving the Example: State [2]
9

10. Solving the Example: State [3]
10
No news (change) is good news! => we reached a
fixpoint!=> The remaining nodes are
drawn

11. Solving the Example: State [4]
11
win(X) :- move(X,Y), not
win(Y).
One rule
… and one (well-
founded)
semanAcs … to
rule them all!

12. Solved Games, Length(X) and Provenance(X)
12

13. Aside: Solving Games ~ Grounded Labeling
Algorithm (~ Alternating Fixpoint Procedure, van Gelder)
13
[17] S. Bowers, Y. Xia, B. Ludäscher, On the Structure of Game Provenance and its Applica<ons, Intl. Workshop on the
Theory and Prac5ce of Provenance (TaPP), 2024. … also [First-Order Provenance Games 2013] .. [Van Gelder 1990’s]

14. Aside: Compu4ng WFS with Datalog/DLV/Clingo
•How do you compute the well-founded semanAcs with a Datalog/ASP
system?
•… should be easy …
•But what about other informaAon? Especially the length of a node?
14

15. Aside: Statelog
a declarative
solution …
A locally/state-stra,fied
program will do …
15
… note how this
Alternating Fixpoint
Computation (AFP)
corresponds to the
backward induction
known e.g. from chess
(end games) and yields
the length of positions ~
min-max numbering of
strongly admissible sets

16. Provenance: All edges are equal, but some edges are more equal …
16

17. Refining Provenance Edge Types
•Not all nodes are created equal
=> Red, Green, Yellow node labels
•Not all edges are created equal
=> winning, losing, drawing, “bad”
edge labels
•Not even all winning and bad edges
are created equal!
=> e.g. primary, secondary winning
17

18. Regular Provenance Structure (Explana6ons)
Provenance via Regular Path Queries (RPQs):
•prov(X,won,!) :- path(X, winning(.delaying.winning)*, !).
•prov(X,lost,!) :- path(X, (delaying.winning)*, !).
•prov(X,drawn,!) :- path(X, (drawing)+, !).
18
•Ques/on:
•What’s the provenance of a node value?
•Answer:
•Solve the game (WM or AF) and look!
=> Provenance/Explana/ons for free!a.1
b.0
1
c.4
5
o.0
1
f.0
j.0
d.1
1
h.2
3
e.3
g.2

3
i.1
2
2
4
3
m.∞
2
k.∞
l.∞
∞
n.∞
∞
∞
∞
1

19. The Skep4c’s Argumenta4on Game (SAG)
•A round with two moves: (X) –Player-I à (Y) –Player-II à (Z)
•Player-I (Skep;c): Argument X is defeated!
Defeated(X) :- Attacked_By(X,Y), not Defeated(Y)

•Player-II (Op;mist): No X isn’t defeated: X is accepted! Here’s my next move:
•You claim that X is a?acked by Y which is accepted (not defeated). I prove you wrong!
•I show you that Y itself is defeated by moving to an accepted a?acker Z of Y (… so your
“rule firing” wasn’t jusLfied)
19

20. The Duality
WM~AF via SAG
Figure 1 (Win-Move):
(a)Move graph
(b)Solved Game
(c)... with Provenance
Figure 2 (AF):
(a)A8ack graph
(b)Grounded SoluHon
(c)... with Provenance
20

21. All edges are equal, but some edges are more equal …
21

22. Example: Animal Case Law as an Abstract AF
22

23. Layered VisualizaJon: Rank by Length
23
4/20/24, 5:41 PM AF-animal-fdp.svg
file:///Users/ludaesch/Dropbox/Reviews/2024-04-COMMA/AF-animal-fdp.svg 1/1
A
B
C
E
F
V
W
Y
T
U
D
Q
Z
X
S
I
M
H
G
J
K
L
O
N
[12] T. Bench-Capon, Representa/on of Case Law as an
Argumenta/on Framework, in: JURIX Conf. on Legal
Knowledge and Informa6on Systems, 2002, pp. 103–112.
4/20/24, 7:57 PM AF-animal-layered.svg
file:///Users/ludaesch/Dropbox/Reviews/2024-04-COMMA/AF-animal-layered.svg 1/1
B.1
A.2
2  
T.2
2  
F.4
5
E.∞
C.1D.1
S.3
4
G.1 H.1
2  
I.1
J.∞
O.∞
U.1
2  
3
K.0
1
L.0
1
Q.0
11
1
V.0
1
1
W.0
1
X.0
1
Y.0
1
Z.0
1
M.∞
∞
∞
N.∞
∞
∞
∞
[14] Y. Xia, D. Odekerken, S. Bowers, B. Ludäscher, Layered
Visualization of Argumentation Frameworks, COMMA Demo, 2024.

24. Related: Demo Time (Thursday)
h"ps://pyarg.npai.science.uu.nl/

25. 25

26. 26

27. Summary and Contribu4ons
•The Skeptic’s Argumentation Game (SAG) ~ classic WM Game => transfer &
(independently) rediscover well-established results from AF (robust notions)
•Example: min-max numbering of arguments (strongly admissible sets [11])
=> Length of a position
=> Explain why an argument is IN, OUT, or UNDEC in the grounded labeling
=> Alternative approach for explaining the acceptance status of arguments
•Layered visualization approachè Demo on Thursday (Daphne Odekerken’s PyArg)
•Future Work: Comparing SAG more deeply with other Discussion Games
•... and Join the Family Reunion between Game-Theory ó LP ó AF ó DB-Theory!
27

28. End of the Road
Some more History and Details ahead

29. A quesJon from the “DB-Theory Bible” [AHV95]
29
Well-founded (WF-)Datalog queries
have 3-valued models in general.
Ques,on: Can every query Q in WF-Datalog-3 be
rewri;en into an equivalent Q’ in WF-Datalog-2?
Þ Total WF-Datalog-2
=?= ParCal WF-Datalog-3?
Example:
Can we detected draws for GAME?
win(X) :- move(X,Y), not win(Y).

30. … answering the quesJon! [FKL-ICDT’97]
30
All you need is GAME! (i.e., the win-move / GAME query)
Games can be reduced to draw-free Games .. by playing a new game!

31. What is the provenance of
a solved game?
or
What is needed to determine the value of a posi3on?
[17] S. Bowers, Y. Xia, B. Ludäscher, On the Structure of Game Provenance and its Applica8ons, TaPP, 2024.

32. a
b c o
f
j
d
h
e
g
i
m
k
l
n Game
Provenance of d
•Value of posiAon d only depends on possible
future posiGons, i.e. reachable from d
•... but excluding “bad moves”
•… and primarily on min (max) moves.
32a
b c o
f
j
d
h
e
g
i
m
k
l
n a
b c o
f
j
d
h
e
g
i
m
k
l
n a
b c o
f.0
j
d.1
1
h.2
3
e
g.2

3
i
m
k
l
n [17] S. Bowers, Y. Xia, B. Ludäscher, On the Structure of Game Provenance and its Applica8ons, TaPP, 2024.

33. 33a
b c o
f
j
d
h
e
g
i
m
k
l
n a
b c o
f
j
d
h
e
g
i
m
k
l
n a
b c o
f.0
j
d.1
1
h.2
3
e
g.2

3
i
m
k
l
n
Provenance of d
Poten&al
provenance
Actual
provenance
Primary (minimal)
provenance
[17] S. Bowers, Y. Xia, B. Ludäscher, On the Structure of Game Provenance and its Applica8ons, TaPP, 2024.

34. 34a
b c.4 o
f.0
j.0
d.1
1
h.2
3
e.3
g.2

3
i.1
2
2
4
3
m
k
l
n
1
Provenance of c
•For lost nodes (e.g. c), we consider all
outgoing edges part of the primary
provenance …
•… b/c all outgoing moves are losing
(delaying),
•… and the jus?fica?on for any
preceding winning posi?on (e.g. a)
needs to consider all possible
responses (here: moves from c)
[17] S. Bowers, Y. Xia, B. Ludäscher, On the Structure of Game Provenance and its Applica8ons, TaPP, 2024.