Introducing the Fourth International Competition on Computational Models of Argumentation

Abstract

Since 2015, the International Competition on Computational Models of Argumentation (ICCMA) has allowed to compare the di erent algorithms for solving some classical reasoning problems in the domain of (abstract) argumentation. In this paper, we describe the rules of the fourth ICCMA, that will be held in 2021. We introduce some minor modi cations regarding the existing tracks (i.e. reasoning with static and dynamic abstract argumentation). Also, for the rst time, we present a new track dedicated to structured argumentation, more precisely Assumption-based Argumentation.

Keywords

• argumentation solvers competition ICCMA

-

existing tracks (corresponding to reasoning with Dung's AFs, respectively in a static or dynamic way), while Section 4 introduces for the rst time structured argumentation at ICCMA, namely Assumption-based Argumentation. We describe the scoring rules of the di erent tracks in Section 5. Finally, Section 6 concludes the paper.

1. Background

1.1. Abstract Argumentation

An abstract argumentation framework (AF) [ 8 ] is a directed graph F = hA; Ri, where A is the set of arguments, and R A A is the attack relation. For a; b; c 2 A, we say that a attacks b if (a; b) 2 R. If in turn b attacks c, then a defends c against b. Similarly, a set S A attacks (respectively defends) an argument b if there is some a 2 S that attacks (respectively defends) b. For S A a set of arguments, S+ is the set of arguments that are attacked by S, formally S+ = fb 2 A j 9a 2 S s.t. (a; b) 2 Rg. The range of S is S = S [ S+.

Di erent semantics have been de ned for evaluating the acceptability of (sets of) arguments.

De nition 1. Given an AF F = hA; Ri, a set of arguments S A is con ict-free i 8a; b 2 S, (a; b) 62 R. A con ict-free set S is admissible i 8a 2 S, S defends a against all its attackers. Con ict-free and admissible sets are respectively denoted by CF(F ) and ADM(F ).

Now, we formally introduce the extension-based semantics. For S A,

S 2 CO(F ) i S 2 ADM(F ) and 8a 2 A that is defended by S, a 2 S;

S 2 PR(F ) i S is a -maximal admissible set;

S 2 ST(F ) i S is a con ict-free set that attacks each a 2 A n S;

S 2 SST(F ) i S 2 CO(F ) and there is no S2 2 CO(F ) s.t. S S 2 STG(F ) i S 2 CF(F ) and there is no S2 2 CF(F ) s.t. S S 2 ID(F ) i S 2 ADM(F ), S \PR(F ), and there is no S2 such that S2 2 ADM(F ) and S S2.

S2 ;

S2 ; \PR(F )

CO, PR, ST, SST, STG and ID stand (respectively) for the complete, preferred, stable [ 8 ], semi-stable [ 9 ], stage [ 10 ] and ideal [ 11 ] semantics. We refer the interested reader to [ 12 ] for more details about these semantics.

For 2 fCO; PR; ST; SST; STG; IDg a semantics, an argument a 2 A is credulously (respectively skeptically) accepted in F = hA; Ri with respect to i a 2 S for some (respectively each) S 2 (F ).

1.2. Assumption-based Argumentation

Now, let us introduce a particular framework for structured argumentation, namely Assumption-based Argumentation (ABA) [ 13 ]. ABA is one of the most popular structured argumentation frameworks, with applications in various domains, like e.g. information seeking and inquiry dialogues [ 14 ], decision making in a medical context [ 15 ], or explanation of automated decisions [ 16 ]. An ABA framework is a tuple F = hL; R; A; i, where: L is a set of symbols called the language; R is a set of rules of the form x0 x1; : : : ; xn, with xi 2 L for i 2 f0; : : : ; ng and n 0; A L is a non-empty set of particular symbols called assumptions; : A ! L is a total mapping that expresses a notion of contrariness. In a rule x0 x1; : : : ; xn, the left-hand part (x0) is called the head of the rule, while the right-hand part (x1; : : : ; xn) is called the body. A rule x0 with no body can be interpreted as x0 >.

A deduction for x 2 L supported by XL L and XR R is a ( nite) tree rooted in x, with nodes labeled by symbols in L or >, such that each leaf is either a symbol in XL or >, and for each internal node with label x0, its children are the elements x1; : : : ; xn of the body of some rule x0 x1; : : : ; xn 2 XR. An argument for the claim x 2 L supported by XA A (denoted by XA ` x) is a deduction for x supported by XA (and some XR R). An argument A1 ` x1 attacks an argument A2 ` x2 i x1 is the contrary of some assumption in A2.

Now, there are two equivalent ways of reasoning with an ABA framework: either the status of arguments is evaluated, or the status of assumptions. Here, we choose to consider the latter.

De nition 2. Given F = hL; R; A; i an ABA framework, a set of assumptions

A1 A attacks a set of assumptions A2 A i an argument supported by a subset

of A1 attacks an argument supported by a subset of A2. A set of assumptions defends an assumption a if it attacks each set of assumptions that attacks a. Then, given a set of assumptions XA A,

XA 2 CF(F ) i it does not attack itself;

XA 2 ADM(F ) i XA 2 CF(F ) and XA defends all its elements;

XA 2 CO(F ) i XA 2 ADM(F ) and 8a 2 A that is defended by XA,

a 2 XA;

XA 2 PR(F ) i XA is a -maximal admissible set;

S 2 ST(F ) i XA 2 CF(F ) and XA attacks each a 2 A n XA.

2. Abstract Argumentation Track

The rst track of the competition is concerned by static abstract argumentation. We introduce some minor changes in this track, compared to the previous editions.

The set of semantics remains the same, except for the grounded semantics, i.e. we consider the ones introduced in De nition 1: 2 fCO; PR; ST; SST; STG; IDg. The grounded semantics was removed since its low complexity makes it easily computable by most solvers for any problem. For each of them, we de ne one sub-track, that will be divided into several reasoning problems.

CE- : Given an AF F = hA; Ri, give the number of -extensions of F . SE- : Given an AF F = hA; Ri, give one -extension of F .

DC- : Given an AF F = hA; Ri and a 2 A an argument, is a credulously accepted in F ? DS- : Given an AF F = hA; Ri and a 2 A an argument, is a skeptically accepted in F ?

The main di erence for this track is the introduction of CE- instead of EE- : this is the counting of extensions, while the previous competitions considered the enumeration of the whole set of extensions. We made this choice because of the space complexity of the extension enumeration, which does not ensure solutions can be represented in practice, even for easy problems. CE- can be simply implemented from a EE- algorithm and is hard-enough to provide challenging tracks { counting the extensions is a #P -complete problem: given such an oracle, one can solve any decision problem which complexity is in the polynomial hierarchy using a polynomial time [ 17 ].

Let us also mention that only two problems are included in the ID track: since there is only one ideal extension for any AF, CE-ID is trivial, contrary to SE-ID, and DC-ID coincides with DS-ID.

The input le format (.apx or .tgf), the command line interface and the solver output will be similar to the ones from the previous edition of ICCMA.

3. Dynamic Argumentation Track

Argumentation dynamics has been considered for the rst time at ICCMA 2019. Recall that it consists in solving a sequence of (similar) tasks in a dynamic environment. For instance, a solver can be asked to determine whether the argument a is credulously accepted with respect to the stable semantics in a given AF F . Then, the same question is asked after the addition or removal of some attack or argument in the AF. Such an addition or removal is called an update of F .

We consider the three classical Dung's semantics [ 8 ] mentioned at De nition 1: 2 fCO; PR; STg, and the same problems as for the abstract argumentation track (CE- , SE- , DC- , DS- ). However, we slightly modify the input of the solvers. At the previous competition, the dynamic solvers were reading in a (.apx or .tgf) le the initial AF, and then in another le the whole set of updates. This method allows the solver to be tuned for the set of arguments that will be added. But it does not seem possible to know the whole set of arguments in advance, for some applications of argumentation (for instance, in automated negotiation, an agent may know some of the arguments of her opponents, but generally not all of them [ 2 ]).

In order to be suited to more realistic situations, for ICCMA 2021, the dynamic solvers will have a fully \online" behavior: after reading the initial AF in a le (similarly to the abstract argumentation track), the solver will wait for updates on the standard input. Each update will be provided to the solver only after it has printed the correct answer to the previous request (the same sequences of updates will be provided to all solvers). An empty line will be given to the solver to indicate that the computation is over. We plan to provide a software helping developers to deal with this new behavior before the submission deadline.

4. Structured Argumentation Track: ABA

For this rst introduction of structured argumentation to ICCMA, we will consider the same reasoning tasks as for the rst track (CE- , SE- , DC- and DS), or more precisely their assumption counterpart, for 2 fCO; PR; STg (see De nition 2).

The solvers input will be described in an adaptation of the ASPARTIX format that is used for the other tracks. For instance, we consider the ABA framework F = hL; R; A; i with L = fa; b; c; p; q; r; s; tg, R = f(p q; a); (q ); (r b; c)g, A = fa; b; cg and a = r, b = s, c = t. This example, borrowed from [ 13 ], can be represented as the following .apx le: rule(p,q,a). rule(q). rule(r,b,c). assum(a). assum(b). assum(c). cont(a,r). cont(b,s). cont(c,t).

For each line rule(...). in the le, the rst parameter corresponds to the head of the rule, and the other (optional) parameters correspond to the body. For instance, rule(p,q,a). represents the rule p q; a, and rule(q). corresponds to q . Assumptions and the contrariness mapping are represented, respectively, by assum(...). and cont(...). lines. Finally, the language does not need to be explicitly given, since it is simply the set of all the symbols that appear in the rules and assumptions.

5. Scoring rules

Now let us describe the scoring rules. For each sub-track, the solvers' ranking will be de ned as follows: in case of any wrong result, the solver is excluded of the sub-track; 1 for every correct answer in the runtime limit, the solver gets a score of 1; in case of timeout or non-parsable output, the solver gets a score of 0; in case of ties, the cumulated runtime over the instances that were correctly solved will be used.

With this method, we will de ne a ranking for each sub-track (recall that a sub-track is made of two or four reasoning tasks, all associated with the same semantics). This means that there will be twelve rankings in the competition: six rankings for the Abstract Argumentation Track; three rankings for the Dynamic Argumentation Track; three rankings for the Structured Argumentation Track.

In order to be ranked, a solver needs to participate to the full sub-track (i.e. the two or four reasoning tasks), however there is no requirement that a solver should participate to all the (sub-)tracks.

1A test phase will be conducted before the actual competition.

6. Conclusion

This paper describes the preliminary design of ICCMA 2021. In the next months, we will advertise the competition through a call for participation, as well as a call for benchmarks. The detailed technical requirements for the solvers will be communicated at this time. To help the participants to prepare their solver, we will also provide some material before the deadline for the submission (including preliminary benchmarks and the software dedicated to dynamic argumentation), and we will perform some tests on the submitted solver before the actual competition phase. This will allow to identify and correct minor bugs that might appear in the solvers. We refer the reader to the competition website for up-to-date information: http://argumentationcompetition.org/2021/

References

[1] Baron P , Gabbay DM , Giacomin M. Handbook of Formal Argumentation . College Publications; 2018 .

[2] Dimopoulos Y , Mailly JG , Moraitis P . Argumentation-based Negotiation with Incomplete Opponent Pro les . In: Proc. of AAMAS'19; 2019 . p. 1252 { 1260 .

[3] Amgoud L , Vesic S. On the Use of Argumentation for Multiple Criteria Decision Making . In: Proc. of IPMU'12; 2012 . p. 480 { 489 .

[4] Dvorak W , Dunne PE . Computational Problems in Formal Argumentation and their Complexity . In: Baroni P, Gabbay D , Giacomin M , van der Torre L, editors. Handbook of Formal Argumentation . College Publications; 2018 . p. 631 { 688 .

[5] Thimm M , Villata S. The rst international competition on computational models of argumentation: Results and analysis . Artif Intell . 2017 ; 252 : 267 { 294 .

[6] Gaggl SA , Linsbichler T , Maratea M , Woltran S . Design and results of the Second International Competition on Computational Models of Argumentation . Artif Intell . 2020 ; 279 .

[7] Bistarelli S , Kottho L , Santini F , Taticchi C . Containerisation and Dynamic Frameworks in ICCMA'19 . In: Proc. of SAFA'18; 2018 . p. 4 { 9 .

[8] Dung PM . On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games . Artif Intell . 1995 ; 77 ( 2 ): 321 { 358 .

[9] Caminada MWA , Carnielli WA , Dunne PE . Semi-stable semantics . J Log Comput . 2012 ; 22 ( 5 ): 1207 { 1254 .

[10] Verheij B. Two approaches to dialectical argumentation: admissible sets and argumentation stages . In: Proc.of NAIC'96; 1996 . p. 357 { 368 .

[11] Dung PM , Mancarella P , Toni F . Computing ideal sceptical argumentation . Artif Intell . 2007 ; 171 ( 10 -15): 642 { 674 .

[12] Baroni P , Caminada M , Giacomin M. Abstract Argumentation Frameworks and Their Semantics . In: Baroni P, Gabbay D , Giacomin M , van der Torre L, editors. Handbook of Formal Argumentation . College Publications; 2018 . p. 159 { 236 .

[13] Toni F. A tutorial on assumption-based argumentation . Argument & Computation . 2014 ; 5 ( 1 ): 89 { 117 .

[14] Fan X , Toni F . Agent Strategies for ABA-based Information-seeking and Inquiry Dialogues . In: Proc. of ECAI'12; 2012 . p. 324 { 329 .

[15] Fan X , Craven R , Singer R , Toni F , Williams M . Assumption-Based Argumentation for Decision-Making with Preferences: A Medical Case Study . In: Proc. of CLIMA XIV ; 2013 . p. 374 { 390 .

[16] Zhong Q , Fan X , Toni F , Luo X . Explaining Best Decisions via Argumentation . In: Proc. of ECSI'14; 2014 . p. 224 { 237 .

[17] Toda S. On the Computational Power of PP and +P . In: 30th Annual Symposium on Foundations of Computer Science , Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989 . IEEE Computer Society; 1989 . p. 514 { 519 .