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

ludaesch 49 views 34 slides Sep 18, 2024
Slide 1
Slide 1 of 34
Slide 1
1
Slide 2
2
Slide 3
3
Slide 4
4
Slide 5
5
Slide 6
6
Slide 7
7
Slide 8
8
Slide 9
9
Slide 10
10
Slide 11
11
Slide 12
12
Slide 13
13
Slide 14
14
Slide 15
15
Slide 16
16
Slide 17
17
Slide 18
18
Slide 19
19
Slide 20
20
Slide 21
21
Slide 22
22
Slide 23
23
Slide 24
24
Slide 25
25
Slide 26
26
Slide 27
27
Slide 28
28
Slide 29
29
Slide 30
30
Slide 31
31
Slide 32
32
Slide 33
33
Slide 34
34

About This Presentation

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 F...


Slide Content

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

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

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

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)

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
Solving the Example

Solving the Example: State [0]
7

Solving the Example: State [1]
8

Solving the Example: State [2]
9

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

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!

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

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]

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

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

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

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

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

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

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

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

Example: Animal Case Law as an Abstract AF
22

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.

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

25

26

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

End of the Road
Some more History and Details ahead

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).

… 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!

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.

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.

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.

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.