pygarg: A Python engine for argumentation

1.Introduction

Abstract argumentation [11] provides a simple framework for representing conflicting pieces of information and deducing which of them can be accepted. In his seminal paper, Dung shows how it can be used to represent problems such as non-monotonic reasoning or stable marriage problems. Recent works show various other applications like fair allocation of resources [20] or explainability of (black box) classification models [1]. Despite the generally high complexity of argumentation reasoning [13], recent advancements in SAT-based solving techniques for argumentation [18] have permitted to handle harder instances and problems, as can be seen from the results of the International Competition on Computational Models of Argumentation (ICCMA) [15]. However, from a practical point of view, the solvers participating to the competition tend to focus on the problems that are part of the competition track. This means, for instance, that most of the solvers that participated to the last editions of ICCMA (in 2021 and 2023) may not solve the extension enumeration task. If a user requires several types of reasoning tasks, he may need to use different argumentation solvers in the same project, which may increase the difficulty especially for non-expert programmers. This may make it difficult for some part of the community to actually implement and test their ideas. This is why we propose pygarg, a Python implementation of the SAT-based algorithms initially proposed in CoQuiAAS [18],11 the solver that won the first edition of ICCMA in 2015.22 While pygarg can be used with a command-line interface inspired by the ICCMA requirements, it is also easy to incorporate it as a third-party library in any Python script. So, anyone in need of solving problems for abstract argumentation can use pygarg for problems such as deciding the (credulous or skeptical) acceptability of an argument, computing one or all the extensions, or counting the extensions, for Dung’s semantics [11], the semi-stable [8] and ideal semantics [12], with a single tool.

Section 2 recalls basic notions of abstract argumentation. Section 3 describes the design of pygarg, and how to use it either as a command-line tool or in one’s own script. Section 4 concludes the paper.

2.Background notions

We start with a reminder of basic notions of abstract argumentation.

Dung does not assume the finiteness of the set of arguments, however it is the case for our implementation. Notice that the set of argument can be empty. We say that a∈A (respectively S⊆A) attacks b∈A when (a,b)∈R (respectively some a∈S attacks b). Then, a set of arguments S defends an argument a if S attacks all the arguments attacking a. Classical reasoning with AFs is based on the notion of extensions, i.e. sets of jointly acceptable arguments. An extension must usually satisfy two basic properties: S⊆A is conflict-free if ∀a,b∈S, (a,b)∉R; and S⊆A is self-defending if S defends all its elements. A set satisfying both these properties is admissible. We write cf(F) and ad(F) for the sets of conflict-free and admissible sets of F. Then, classical Dung’s semantics [11] are defined as follows.

We use co(F), pr(F), st(F) and gr(F) for these sets of extensions. It is well-known [11] that |gr(F)|=1 for any AF, that st(F)⊆pr(F), and preferred extensions also correspond to ⊆-maximal complete extensions. Finally, from all the semantics studied in this paper, only the stable semantics may collapse, i.e. for any σ≠st, σ(F)≠∅ for any AF. From the preferred semantics, one can define a “more skeptical” semantics as follows.

We write id(F) the set of ideal extensions of an AF. Similarly to the grounded semantics, the ideal extension is unique for any AF. Finally, we also focus on one last semantics, based on the notion of range. Given an AF F=⟨A,R⟩ and a∈A, we write a+={b∈A|(a,b)∈R} the set of arguments attacked by a. We generalize it to sets, with S+=⋃a∈Sa+ for the set of arguments attacked by S. The range of S is S⊕=S∪S+, i.e. the set of arguments which are either members of S or attacked by S.

We write sst(F) for the semi-stable extensions. Notice that st(F)⊆sst(F), and if st(F)≠∅ then both semantics coincide, but sst(F)≠∅ even when there is no stable extension.

Fig. 1.

An example of AF F.

Reasoning with these semantics is generally hard, with complexity up to the second level of the polynomial hierarchy, depending on the semantics and the exact decision problem [13]. However, various implementations based on SAT solvers have been proposed for reasoning with abstract argumentation, mainly based on the logical encoding by Besnard and Doutre [3]. Describing in details these algorithms is out of the scope of this paper, but we refer the interested reader to [18], since our work is essentially a Python implementation of the SAT-based approach from CoQuiAAS.

3.Describing pygarg

pygarg is an open-source software,33 implemented in Python, relying on PySAT [16] for performing calls to SAT solvers. In this section, we describe how pygarg can be used, either as a command-line tool, or as a library integrated to another Python code.

3.1.Using pygarg as a command-line tool

The source code of pygarg is based on five Python files:

• __main__.py (in the main package) provides the command-line interface of the software,

• in the dung package,

  • ∗ apx_parser.py provides tools for parsing an APX file [14] (as used notably in ICCMA 2015, 2017, 2019 and 2021) into an argumentation framework usable by the solvers,

  • ∗ dimacs_parser.py provides tools for parsing a Dimacs file [17] (as used in ICCMA 2023) into an argumentation framework usable by the solvers,

  • ∗ encoding.py provides the tools used to translate argumentation problems into SAT solving,

  • ∗ solver.py provides the functions for solving argumentation reasoning tasks.

Using the __main__.py file, one can use a command-line interface reminiscent of the ICCMA requirements, which is described in details in the README file of the software. In summary, one can use the command-line options:

• -p PROBLEM to define the problem to be solved, with PROBLEM being XX-YY where XX is one of DC, DS, SE, EE, CE (for credulous acceptability, skeptical acceptability, computing some extension, enumerating extensions and counting extensions) and YY must be one of CF, AD, ST, CO, PR, GR, ID, SST corresponding to σ∈{cf,ad,st,co,pr,gr,id,sst},

• -fo FORMAT to define the format of the input file describing an AF, which must be equal to apx or dimacs,

• -f FILENAME to specify the path to the input file,

• -a ARGNAME to specify the name of the argument to be checked (for DC and DS problems).

The output of these commands follows the requirements of ICCMA 2023. This means that (when possible), an extension is provided as a witness for the (non-)acceptability of an argument, in a line starting with w. The same syntax is used for providing one (or each) extension of the AF. For instance, if test.apx corresponds to the AF from Fig. 1, we obtain the result presented at Fig. 2.

Fig. 2.

Enumerating extensions with pygarg on the command-line.

In case there is an empty extension, a line with only w will be printed.

3.2.Using pygarg in another Python program

Now we focus on how to use pygarg in one’s own Python code. The data structures used to represent an AF are simply a list of strings (representing the arguments names), and a list of lists of strings (representing the attacks). For instance, the AF from Fig. 1 corresponds to the structure from Listing 1.

Listing 1.

Python data structure for the sets of arguments and attacks.

Instead of manually constructing the list of arguments and attacks, one can use the parse(filename) function provided in both apx_parser.py and dimacs_parser.py. For instance, Listing 2 shows how to parse an apx file.

Listing 2.

Parsing a text file with pygarg.

Then, one needs to focus on some functions provided in the file solver.py:

• credulous_acceptability(args, atts, argname, sem) determines whether the argument argname is credulously accepted under the semantics sem,

• skeptical_acceptability(args, atts, argname, sem) determines whether the argument argname is skeptically accepted under the semantics sem,

• compute_some_extension(args, atts, sem) computes one sem-extension,

• extension_enumeration(args, atts, sem) enumerates all the sem-extensions,

• extension_counting(args, atts, sem) counts the number of sem-extensions.

In these functions, the sem argument must be a string describing the semantics, using the same conventions as the command-line interface (for instance, the complete semantics is described by "CO").

Example 2.

Continuing the previous example, Fig. 3 shows how we enumerate the extensions of the AF from Fig. 1, for the semantics σ∈{co,pr,gr,st,sst,id}. The result is shown in Fig. 4.

Fig. 3.

Enumerating extensions with pygarg imported in one’s own code.

Fig. 4.

Result of running the extension enumeration.

4.Discussion

As far as we know, the most similar implementation of reasoning tasks for abstract argumentation is PyArg [6,22]. However, the focus of PyArg is not on efficient algorithms, but rather on its graphical interface44 and various other advanced features like computing explanations of acceptability or structured argumentation, which are not included in the current version of pygarg. For this reason, the algorithms included in this platform are more “naive” (for instance they are not based on SAT solving techniques), and thus they do not scale up as well as SAT-based algorithms. This is not a major problem for the purpose of PyArg, which is visualisation (and one can assume that users interested in visualising graphs do not use large graphs with dozens or hundreds of arguments). An empirical evaluation [21] shows that pygarg clearly outperforms PyArg for all tasks except the ones related to the (polynomially computable) grounded semantics.

For future work, we envision various possible directions. A first one would be to replace “naive” SAT-based algorithms by more efficient ones when possible (for instance, the current implementation of skeptical acceptability under the preferred semantics and reasoning with the ideal semantics is based on the enumeration of preferred extensions, but it could benefit from the techniques proposed by [24]). We are also interested in implementing algorithms for other semantics (like the stage semantics [25], or the more challenging semantics based on weak admissibility [2]), or other problems (like verifying if a set of arguments is an extension). Still in line with recent ICCMA competitions, we would like to incorporate techniques for dynamic re-computation of extensions when an AF evolves [4], or approximation algorithms (in the spirit of [10]). Other problems related to extension-based semantics could be added, like counting the number of extensions (not) containing a given argument. The labelling-based [7] counterpart of the problems already implemented could also be added. Finally, more long term projects include the integration of gradual and ranking-based semantics [5], as well as more general argumentation frameworks like Bipolar AFs [9], Strength-based AFs [23] or Incomplete AFs [19].