Ebook: Computational Models of Argument

Argumentation as a field of inquiry has been attracting an increasing number of researchers from different areas. One of the main shared goals among these researchers is the pursuit of solutions to the many research problems found in the Knowledge Representation and Reasoning area of Artificial Intelligence using strategies akin to the commonsense approach displayed by humans. Practical applications of the basic research results have been gaining attention in several areas including in particular the Autonomous Agents and Multiagent Systems community. By the beginning of this decade, the need for a forum where these advances could be discussed in a specialized manner was recognized by the members of the argumentation community, leading to the decision of establishing a biennial conference with focus on the computational aspects of argumentation.

In September 2006, the First Conference on Computational Models of Argument was hosted, with resounding success, by the University of Liverpool; a similar response followed in May 2008 when the Second Conference on Computational Models of Argument was held in France, hosted by the Institut de Recherche en Informatique de Toulouse (IRIT).

This volume contains the papers forming the program of the Third Conference on Computational Models of Argument held in Desenzano del Garda, Italy, from Sept. 8th to 10th, 2010. This time the responsibility of hosting the conference was assumed by the University of Brescia. The papers in the volume address topics ranging from formal models of argumentation and the relevant theoretical questions, through algorithms and computational complexity issues, to the use of argumentation in several application domains, thus providing an up-to-date view of this vital research field.

The success of a conference depends on the contributions of many people. The organizers wish to thank the Steering Committee of COMMA for all the help received. We are deeply grateful to the members of the Program Committee, and additional reviewers, for the hard work of evaluating the submitted papers. Their reports and discussions greatly facilitated the final decisions that led to the content of this book, which includes two invited papers by prof. Gerhard Brewka and prof. Douglas Walton, 35 full papers and 5 short papers selected from 67 submissions.

We would like to thank Giovanni Perbellini for his contribution to the work of the Local Organizing Committee, Laura Folli for designing the conference logo and Diego Beda, Loretta Bettari, Luca Mori for their help concerning the venue of the conference. Finally, we gratefully acknowledge financial support from the Municipality of Desenzano del Garda and Taylor & Francis Group.

July, 2010

Pietro Baroni (General Conference Chair), Federico Cerutti (Local Organization Co-chair), Massimiliano Giacomin (Local Organization Chair), Guillermo R. Simari (Programme Chair)

Carneades is a rather general framework for argumentation. Unlike many other approaches, Carneades captures a number of aspects, like proof burdens, proof standards etc., which are of central importance, in particular in legal argumentation.

In this paper we show how Carneades argument evaluation structures can be reconstructed as abstract dialectical frameworks (ADFs), a recently proposed generalization of Dung argumentation frameworks (AFs). This not only provides at least an indirect link between Carneades and AFs, it also allows us to handle arbitrary argument cycles, thus lifting a restriction of Carneades. At the same time it provides strong evidence for the usefulness of ADFs as analytical/semantical tools in argumentation.

Burden of proof has recently come to be a topic of interest in argumentation systems for artificial intelligence (Prakken and Sartor, 2006, 2007, 2009; Gordon and Walton, 2007, 2009), but so far the main work on the subject seems to be in that type of dialogue which has most intensively been investigated generally, namely persuasion dialogue. The most significant exception is probably deliberation dialogue, where some recent work has begun to tentatively investigate burden of proof in that setting. In this paper, I survey work on burden of proof in the artificial intelligence literature on argumentation, and offer some thoughts on how this work might be extended to the other types of dialogue recognized by Walton and Krabbe (1995) that so far do not appear to have been much investigated in this regard.

In this paper we define a recursive semantics for warrant in a general defeasible argumentation framework by formalizing a notion of collective (non-binary) conflict among arguments. This allows us to ensure direct and indirect consistency (in the sense of Caminada and Amgoud) without distinguishing between direct and indirect conflicts. Then, the general defeasible argumentation framework is extended by allowing to attach levels of preference to defeasible knowledge items and by providing a level-wise definition of warranted and blocked conclusions. Finally, we formalize the warrant recursive semantics for the particular framework of Possibilistic Defeasible Logic Programming, characterize the unique output program property and design an efficient algorithm for computing warranted conclusions in polynomial space.

Different proposals have been made in the literature for refining Dung's argumentation framework by preferences between arguments. The idea is to ignore an attack if the attacked argument is stronger than its attacker. Acceptability semantics are then applied on the remaining attacks. Unfortunately, these proposals may return some unintended results, in particular, when the attack relation is asymmetric.

In this paper, we propose a new approach in which preferences are taken into account at the semantics level. In case preferences are not available or do not conflict with the attacks, the extensions of the new semantics coincide with those of the basic ones. Besides, in our approach, the extensions (under a given semantics) are the maximal elements of a dominance relation on the powerset of the set of arguments. Throughout the paper, we focus on stable semantics. We provide a full characterization of its dominance relations; and we refine it with preferences.

When argumentation is conceived as a kind of process, typically a dialogue, for reasoning rationally with limited resources under conditions of incomplete and inconsistent information, arguers need heuristics for controlling the search for arguments to put foward, so as to move from stage to stage in the process in an efficient, goal-directed way. For this purpose, we have developed a formal model of abduction in argument evalution structures. An argument evaluation structure consists of the arguments of a stage, assumptions about audience and an assignment of proof standards to issues. A derivability relation is defined over argument evaluation structures for the literals ‘in’ a stage. Literals which are not derivable in a stage are ‘out’. Abduction is defined as a relation between an argument evaluation structure and sets of literals, called ‘positions’, which, when the assumptions are revised to include the literals of the position, would make a goal literal in or out, depending of the standpoint of the agent. Soundness, minimiality, consistency and completeness properties of the abduction relation are proven. A heuristic cost function estimating how difficult it is to find or construct arguments pro a literal in the domain can be used to order positions and literals within positions. We compare our work to abduction in propositional logic, in particular the Assumption-Based Truth Maintenance System (ATMS).

We consider the problem of counting (without explicitly enumerating) extensions prescribed by multiple-status semantics in abstract argumentation. Referring to Dung's traditional stable and preferred semantics and to the recently introduced resolution-based grounded semantics (GR*), we show that in general extension counting is computationally hard (actually #P-complete). We then identify non-trivial topological classes of argumentation frameworks where extension counting is tractable. In particular we show, by providing and analyzing the relevant algorithms, that in symmetric argumentation frameworks counting GR* extensions is tractable (but is still hard for stable and preferred estensions), while counting is tractable for all the considered semantics in tree-like argumentation frameworks.

This paper addresses the problem of revising a Dung-style argumentation framework by adding finitely many new arguments which may interact with old ones. We study the behavior of the extensions of the augmented argumentation frameworks, taking also into account possible changes of the underlying semantics (which may be interpreted as corresponding changes of proof standards). We show both possibility and impossibility results related to the problem of enforcing a desired set of arguments. Furthermore, we prove some monotonicity results for a special class of expansions with respect to the cardinality of the set of extensions and the justification state.

Legal reasoning is one of the most obvious application areas for computational models of argumentation as the exchange of arguments and counterarguments is the established means for making decisions in law. In this paper we employ Defeasible Logic Programming (DeLP) for representing legal cases and for giving decision-support, exemplary for private law. We give a formalization of legal provisions that can be used easily by judges for supporting their decision process and present a working system that resembles the decision-making in legal reasoning, in particular, with respect to the burden of proof.

In order to support the interchange of ideas and data between different projects and applications in the area of computational argumentation, a common ontology for computational argument, the Argument Interchange Format (AIF), has been devised. One of the criticisms levelled at the AIF has been that it does not take into account formal argumentation systems and their associated argumentation-theoretic semantics, which are part of the main focus of the field of computational argumentation. This paper aims to meet those criticisms by analysing the core AIF ontology in terms of the recently developed ASPIC argumentation framework.

In this paper, we consider two drawbacks of Cayrol and Lagasque-Schiex's meta-argumentation theory to model bipolar argumentation frameworks. We consider first the “lost of admissibility” in Dung's sense and second, the definition of notions of attack in the context of a support relation. We show how to prevent these drawbacks by introducing support meta-arguments. Like the model of Cayrol and Lagasque-Schiex, our formalization confirms the use of meta-argumentation to reuse Dung's properties. We do not take a stance towards the usefulness of a support relation among arguments, though we show that if one would like to introduce them, it can be done without extending Dung's theory. Finally, we show how to use meta-argumentation to instantiate an argumentation framework to represent defeasible support. In this model of support, the support relation itself can be attacked.

This paper reports progress in realizing human-agent argumentation, which we argue will be part of future Computer-Supported Collaborative Argumentation (CSCA) tools. With a particular interest in argument mapping, we present two investigations demonstrating how a particular agent-oriented language and architecture can augment CSCA: (i) the use of the IBIS formalism enabling Brahms agents to simulate argumentation, and (ii) the extension of the Compendium tool by integrating it with Brahms agents tasked with detecting related discourse elsewhere.

The aim of the paper is to propose a robust model of interpersonal argumentation (IP). The IP-arguments directly address participants of communication, i.e. they refer to speech acts rather than to propositional contents. Argumentation theory recognizes several IP-arguments, e.g. argument from position to know or ad hominem arguments. The model proposed in the paper enables to describe references to different types of speech acts – not only assertives, but also commissives and directives. The IP-arguments are assumed to be warranted by the component of authorizing an agent to perform a given speech act. Consequently, the wider class of IP-communication can be expressed in the extended model, such as e.g. the structure of generic ad hominem can be explicitly represented as the undercutter.

In the current paper, we re-examine the concept of stage semantics, which is one of the oldest semantics for abstract argumentation. Using a formal treatment of its properties, we explain how the intuition behind stage semantics differs from the intuition behind the admissibility based semantics that most scholars in argumentation theory are familiar with. We then provide a labelling-based algorithm for computing all stage extensions, based on earlier algorithms for computing all preferred, stable and semi-stable extensions.

Constrained argumentation frameworks (CAF) generalize Dung's frameworks by allowing additional constraints on arguments to be taken into account in the definition of acceptability of arguments. These constraints are expressed by means of a logical formula which is added to Dung's framework. The resulting system captures several other extensions of Dung's original system. To determine if a set of arguments is credulously inferred from a CAF, the notion of dialectical proof (alternating pros and cons arguments) is extended for Dung's frameworks in order to respect the additional constraint. The new constrained dialectical proofs are computed by using Answer Set Programming.

We propose an argumentation framework for modelling jury-based dispute resolution where the dispute parties present their arguments before a judge and a jury. While the judge as the arbiter of law determines the legal permissibility of the presented arguments the jurors as triers of facts determine their probable weights. Such a framework is based on two key components: classical argumentation frameworks containing legally permissible arguments and probabilistic spaces assigning probable weights to arguments. A juror's probability space is represented by a set of possible worlds coupled with a probabilistic measure computed by assumption-based argumentation framework using grounded semantics.

We give some design guidelines for argumentation systems. These guidelines are meant to indicate essential features of argumentation when used to support “practical reasoning”. We express the guidelines in terms of postulates. We use a notion of redundancy to provide a formal counterpart of these postulates. We study the satisfaction of these postulates in two existing argumentation frameworks: assumption-based argumentation and argumentation in classical logic.

Value-based argumentation frameworks (VAFs) have proven to be a useful development of Dung's seminal model of argumentation in providing a rational basis for distinguishing mutually incompatible yet individually acceptable sets of arguments. In classifying argument status within value-based frameworks two main decision problems arise: subjective acceptance (SBA) and objective acceptance (OBA). These problems have proven to be somewhat resistant to efficient algorithmic approaches (the general cases being NP–complete and coNP–complete) even when very severe limitations are placed on the structure of the supporting Dung-style framework. Although using the number of values (k) represented within a given vaf leads to fixed parameter tractable (FPT) methods, these are not entirely satisfactory: the rate of growth of the parameter function (k!) making such methods unacceptable in cases where k is moderately large, e.g. k ≥ 20. In this paper we consider an alternative approach to the development of practical algorithms in value-based argumentation. In particular cases this leads to polynomial (in |χ|) methods, i.e. irrespective of the value of k. More general examples are shown to be decidable in O(f(k)|χ|²) steps where f(k)=o(k!) resulting in worst-case run times that significantly improve upon enumerating all value orderings.

In abstract frameworks with varied strength attacks (AFV), arguments may attack each other with different strength. An admissible scenario is an admissible set of arguments fulfilling certain strength conditions about defences. In this work we analyze the computational complexity of some decision problems related to the quality of admissible scenarios: checking the property of being top-admissible and the property of being equilibrated. These problems are implying an exhaustive comparison between scenarios, and both of them are shown to be coNP-complete.

Most computational problems in the area of abstract argumentation are intractable, thus identifying tractable fragments and developing efficient algorithms for such fragments are important objectives towards practically efficient argumentation systems. One approach to tractability is to view abstract argumentation frameworks (AFs) as directed graphs and bound certain graph parameters. In particular, Dunne showed that many problems can be solved in linear time for AFs of bounded treewidth. In this paper we consider the graph-parameter clique-width, which is more general than treewidth. An additional advantage of clique-width over treewidth is that it applies well to directed graphs and takes the orientation of edges into account. We first give theoretical tractability results for AFs of bounded clique-width and then introduce dynamic-programming algorithms for credulous and skeptical reasoning.

Conflicts exist in multi-agent systems. Agents have different interests and desires. Agents also hold different beliefs and may make different assumptions. To resolve conflicts, agents need to better convey information between each other and facilitate fair negotiations that yield jointly agreeable outcomes. In this paper, we present a two-agent conflict resolution scheme developed under Assumption-Based Argumentation (ABA). Agents represent their beliefs and desires in ABA. Conflicts are resolved by merging conflicting arguments. We also discuss the notion of fairness and the use of argumentation dialogue in conflict resolution.

Abstract argumentation frameworks nowadays provide the most popular formalization of argumentation on a conceptual level. Numerous semantics for this paradigm have been proposed, whereby cf2 semantics has shown to nicely solve particular problems concernend with odd-length cycles in such frameworks. In order to compare different semantics not only on a theoretical basis, it is necessary to provide systems which implement them within a uniform platform. Answer-Set Programming (ASP) turned out to be a promising direction for this aim, since it not only allows for a concise representation of concepts inherent to argumentation semantics, but also offers sophisticated off-the-shelves solvers which can be used as core computation engines. In fact, many argumentation semantics have meanwhile been encoded within the ASP paradigm, but not all relevant semantics, among them cf2 semantics, have yet been considered. The contributions of this work are thus twofold. Due to the particular nature of cf2 semantics, we first provide an alternative characterization which, roughly speaking, avoids the recursive computation of sub-frameworks. Then, we provide the concrete ASP-encodings, which are incorporated within the ASPARTIX system, a platform which already implements a wide range of semantics for abstract argumentation.

This paper presents a technique with which instances of argument structures in the Carneades model can be given a probabilistic semantics by translating them into Bayesian networks. The propagation of argument applicability and statement acceptability can be expressed through conditional probability tables. This translation suggests a way to extend Carneades to improve its utility for decision support in the presence of uncertainty.