Reasoning about preferences in argumentation frameworks

The abstract nature of Dung's seminal theory of argumentation accounts for its widespread application as a general framework for various species of non-monotonic reasoning, and, more generally, reasoning in the presence of conflict. A Dung argumentation framework is instantiated by arguments and a binary conflict based attack relation, defined by some underlying logical theory. The justified arguments under different extensional semantics are then evaluated, and the claims of these arguments define the inferences of the underlying theory. To determine a unique set of justified arguments often requires a preference relation on arguments to determine the success of attacks between arguments. However, preference information is often itself defeasible, conflicting and so subject to argumentation. Hence, in this paper we extend Dung's theory to accommodate arguments that claim preferences between other arguments, thus incorporating meta-level argumentation based reasoning about preferences in the object level. We then define and study application of the full range of Dung's extensional semantics to the extended framework, and study special classes of the extended framework. The extended theory preserves the abstract nature of Dung's approach, thus aiming at a general framework for non-monotonic formalisms that accommodate defeasible reasoning about as well as with preference information. We illustrate by formalising argument based logic programming with defeasible priorities in the extended theory.     

A logic of argumentation for specification and verification of abstract argumentation frameworks

In this paper, we propose a logic of argumentation for the specification and verification (LA4SV) of requirements on Dung??s abstract argumentation frameworks. We distinguish three kinds of decision problems for argumentation verification, called extension verification, framework verification, and specification verification respectively. For example, given a political requirement like ??if the argument to increase taxes is accepted, then the argument to increase services must be accepted too,?? we can either verify an extension of acceptable arguments, or all extensions of an argumentation framework, or all extensions of all argumentation frameworks satisfying a framework specification. We introduce the logic of argumentation verification to specify such requirements, and we represent the three verification problems of argumentation as model checking and theorem proving properties of the logic. Moreover, we recast the logic of argumentation verification in a modal framework, in order to express multiple extensions, and properties like transitivity and reflexivity of the attack relation. Finally, we introduce a logic of meta-argumentation where abstract argumentation is used to reason about abstract argumentation itself. We define the logic of meta-argumentation using the fibring methodology in such a way to represent attack relations not only among arguments but also among attacks. We show how to use this logic to verify the requirements of argumentation frameworks where higher-order attacks are allowed [A preliminary version of the logic of argumentation compliance was called the logic of abstract argumentation?(2005).]     

Computing ideal sceptical argumentation

We present two dialectic procedures for the sceptical ideal semantics for argumentation. The first procedure is defined in terms of dispute trees, for abstract argumentation frameworks. The second procedure is defined in dialectical terms, for assumption-based argumentation frameworks. The procedures are adapted from (variants of) corresponding procedures for computing the credulous admissible semantics for assumption-based argumentation, proposed in [P.M. Dung, R.A. Kowalski, F. Toni, Dialectic proof procedures for assumption-based, admissible argumentation, Artificial Intelligence 170 (2006) 114–159]. We prove that the first procedure is sound and complete, and the second procedure is sound in general and complete for a special but natural class of assumption-based argumentation frameworks, that we refer to as p-acyclic. We also prove that in the case of p-acyclic assumption-based argumentation frameworks (a variant of) the procedure of [P.M. Dung, R.A. Kowalski, F. Toni, Dialectic proof procedures for assumption-based, admissible argumentation, Artificial Intelligence 170 (2006) 114–159] for the admissible semantics is complete. Finally, we present a variant of the procedure of [P.M. Dung, R.A. Kowalski, F. Toni, Dialectic proof procedures for assumption-based, admissible argumentation, Artificial Intelligence 170 (2006) 114–159] that is sound for the sceptical grounded semantics.     

Characterizing strong equivalence for argumentation frameworks

Since argumentation is an inherently dynamic process, it is of great importance to understand the effect of incorporating new information into given argumentation frameworks. In this work, we address this issue by analyzing equivalence between argumentation frameworks under the assumption that the frameworks in question are incomplete, i.e. further information might be added later to both frameworks simultaneously. In other words, instead of the standard notion of equivalence (which holds between two frameworks, if they possess the same extensions), we require here that frameworks F and G are also equivalent when conjoined with any further framework H. Due to the nonmonotonicity of argumentation semantics, this concept is different to (but obviously implies) the standard notion of equivalence. We thus call our new notion strong equivalence and study how strong equivalence can be decided with respect to the most important semantics for abstract argumentation frameworks. We also consider variants of strong equivalence in which we define equivalence with respect to the sets of arguments credulously (or skeptically) accepted, and restrict strong equivalence to augmentations H where no new arguments are raised.     

Modelling defeasible and prioritized support in bipolar argumentation

Cayrol and Lagasquie-Schiex introduce bipolar argumentation frameworks by introducing a second relation on the arguments for representing the support among them. The main drawback of their approach is that they cannot encode defeasible support, for instance they cannot model an attack towards a support relation. In this paper, we introduce a way to model defeasible support in bipolar argumentation frameworks. We use the methodology of meta-argumentation in which Dung??s theory is used to reason about itself. Dung??s well-known admissibility semantics can be used on this meta-argumentation framework to compute the acceptable arguments, and all properties of Dung??s classical theory are preserved. Moreover, we show how different contexts can lead to the alternative strengthening of the support relation over the attack relation, and converse. Finally, we present two applications of our methodology for modeling support, the case of arguments provided with an internal structure and the case of abstract dialectical frameworks.     

分级论辩系统的逻辑研究

近年来,形式论证已逐渐成为人工智能领域的研究热点之一。自Dung于1995年提出抽象辩论框架起,学术界普遍认为论辩的核心任务是在各种基于外延的语义下对论点集进行评估,以确定其辩护状态。分级论辩系统(Graded Argumentation System,GAS)是对经典Dung型论辩系统(Dung-style Argumentation System,DAS)的推广,通过一般化DAS语义的两个核心性质,即无冲突性和可接受性,来提供更细化的论点状态概念。当前的论辩系统语义等效性研究主要集中在框架和论点层次上,可为其结构约简提供有力的保证。针对两个不同分级论辩系统中论点的语义等效问题,首先运用分级模态逻辑(Graded Modal Logic,GML)形式化分级论辩系统的片段,然后建立并证明了分级论辩系统基于外延的语义和GML公式之间的一一对应关系,最后定义分级互模拟关系并证明其蕴含分级论辩系统的4个重要的语义等价性。     

Minimal hypotheses: extension-based semantics to argumentation

The emptiness problem of the preferred semantics and the non-existence problem of the stable semantics are well recognized for argumentation frameworks. In this paper, we introduce two strong semantics, named s-preferred semantics and s-stable semantics, to guarantee the non-emptiness of the preferred extensions and the existence of the stable extensions respectively. Our semantics are defined by two concepts of extensions of argumentation frameworks, namely s-preferred extension and s-stable extension. Each is constructed in a similar way to the original semantics. The novelty of our semantics is that an extension of an argumentation framework is considered as a pair of sets of arguments, in which the second element of an extension is viewed as a kind of hypotheses that should be minimized. The s-preferred semantics not only solves the emptiness problem of the preferred semantics, but also coincides with the preferred semantics when nonempty preferred extensions exist. Meanwhile, the s-stable semantics ensures the existence of extensions, and coincides with the stable semantics when the stable extensions exist as well. The relations among various semantics for argumentation frameworks are discussed.     

Dynamics of argumentation systems: A division-based method

The changing of arguments and their attack relation is an intrinsic property of a variety of argumentation systems. So, it is very important to efficiently figure out how the status of arguments in a system evolves when the system is updated. However, unlike other areas of argumentation that have been deeply explored, such as argumentation semantics, proof theories, and algorithms, etc., dynamics of argumentation systems has been comparatively neglected. In this paper, we formulate a general theory (called a division-based method) to cope with this problem based on a new concept: the division of an argumentation framework. When an argumentation framework is updated, it is divided into three parts: an unaffected, an affected, and a conditioning part. The status of arguments in the unaffected sub-framework remains unchanged, while the status of the affected arguments is computed in a special argumentation framework (called a conditioned argumentation framework, or briefly CAF) that is composed of an affected part and a conditioning part. We have proved that under a certain semantics that satisfies the directionality criterion (complete, preferred, ideal, or grounded semantics), the extensions of the updated framework are equal to the result of a combination of the extensions of an unaffected sub-framework and sets of the extensions of a set of assigned CAFs. Due to the efficiency of the division-based method, it is expected to be very useful in various kinds of argumentation systems where arguments and attacks are dynamics.     

Local Logics, Non-Monotonicity and Defeasible Argumentation

In this paper we present an embedding of abstract argumentation systems into the framework of Barwise and Seligman’s logic of information flow. We show that, taking P.M. Dung’s characterization of argument systems, a local logic over states of a deliberation may be constructed. In this structure, the key feature of non-monotonicity of commonsense reasoning obtains as the transition from one local logic to another, due to a change in certain background conditions. Each of Dung’s extensions of argument systems leads to a corresponding ordering of background conditions. The relations among extensions becomes a relation among partial orderings of background conditions. This introduces a conceptual innovation in Barwise and Seligman’s representation of commonsense reasoning.     

Reconstructing Popov v. Hayashi in a framework for argumentation with structured arguments and Dungean semantics

In this article the argumentation structure of the court??s decision in the Popov v. Hayashi case is formalised in Prakken??s (Argument Comput 1:93?C124; 2010) abstract framework for argument-based inference with structured arguments. In this framework, arguments are inference trees formed by applying two kinds of inference rules, strict and defeasible rules. Arguments can be attacked in three ways: attacking a premise, attacking a conclusion and attacking an inference. To resolve such conflicts, preferences may be used, which leads to three corresponding kinds of defeat, after which Dung??s (Artif Intell 77:321?C357; 1995) abstract acceptability semantics can be used to evaluate the arguments. In the present paper the abstract framework is instantiated with strict inference rules corresponding to first-order logic and with defeasible inference rules for defeasible modus ponens and various argument schemes. The main techniques used in the formal reconstruction of the case are rule-exception structures and arguments about rule validity. Arguments about socio-legal values and the use of precedent cases are reduced to arguments about rule validity. The tree structure of arguments, with explicit subargument relations between arguments, is used to capture the dependency relations between the elements of the court??s decision.     

Matching couples with Scarf’s algorithm

In a seminal paper Phan Minh Dung (Artif. Intell. 77(2), 321–357, 1995) developed the theory of abstract argumentation frameworks (AFs), which has remained a pivotal point of reference for research in AI and argumentation ever since. This paper assesses the merits of Dung’s theory from an epistemological point of view. It argues that, despite its prominence in AI, the theory of AFs is epistemologically flawed. More specifically, abstract AFs don’t provide a normatively adequate model for the evaluation of rational, multi-proponent controversy. Different interpretations of Dung’s theory may be distinguished. Dung’s intended interpretation collides with basic principles of rational judgement suspension. The currently prevailing knowledge base interpretation ignores relevant arguments when assessing proponent positions in a debate. It is finally suggested that abstract AFs be better understood as a paraconsistent logic, rather than a theory of real argumentation.     

Algorithms and complexity results for persuasive argumentation

The study of arguments as abstract entities and their interaction as introduced by Dung (1995) [1] has become one of the most active research branches within Artificial Intelligence and Reasoning. A main issue for abstract argumentation systems is the selection of acceptable sets of arguments. Value-based argumentation, as introduced by Bench-Capon (2003) [8], extends Dung?s framework. It takes into account the relative strength of arguments with respect to some ranking representing an audience: an argument is subjectively accepted if it is accepted with respect to some audience, it is objectively accepted if it is accepted with respect to all audiences.Deciding whether an argument is subjectively or objectively accepted, respectively, are computationally intractable problems. In fact, the problems remain intractable under structural restrictions that render the main computational problems for non-value-based argumentation systems tractable. In this paper we identify nontrivial classes of value-based argumentation systems for which the acceptance problems are polynomial-time tractable. The classes are defined by means of structural restrictions in terms of the underlying graphical structure of the value-based system. Furthermore we show that the acceptance problems are intractable for two classes of value-based systems that where conjectured to be tractable by Dunne (2007) [12].     

meSAT: multiple encodings of CSP to SAT

One approach for solving Constraint Satisfaction Problems (CSP) (and related Constraint Optimization Problems (COP)) involving integer and Boolean variables is reduction to propositional satisfiability problem (SAT). A number of encodings (e.g., direct, log, support, order) for this purpose exist as well as specific encodings for some constraints that are often encountered (e.g., cardinality constraints, global constraints). However, there is no single encoding that performs well on all classes of problems and there is a need for a system that supports multiple encodings. We present a system that translates specifications of finite linear CSP problems into SAT instances using several well-known encodings, and their combinations. We also present a methodology for selecting a suitable encoding based on simple syntactic features of the input CSP instance. Thorough evaluation has been performed on large publicly available corpora and our encoding selection method improves upon the efficiency of existing encodings and state-of-the-art tools used in comparison.     

基于动态规划的优先语义扩充求解算法

抽象辩论框架中的优先语义是判断争议可接受程度的最重要语义。现有优先扩充求解方法多用标记映射求解,依赖于标记的定义、转换规则、相邻争议的标记。算法每次迭代会产生一个新的抽象辩论框架导致时间、空间复杂度较高。提出一种基于动态规划的优先扩充算法,在动态规划中加入争议可接受性判断,求出辩论框架中极大可容许集得到优先扩充。在基于随机抽象辩论框架与ICCMA提供的数据集进行实验,同Heureka、ArgSemSAT等算法进行对比。结果表明,求解相同数量的优先扩充,算法耗时较少,时间、空间复杂度有所降低。     

A new approach for preference-based argumentation frameworks

Dung’s argumentation framework consists of a set of arguments and an attack relation among them. Arguments are evaluated and acceptable sets of them, called extensions, are computed using a given semantics. Each extension represents a coherent position. In the literature, several proposals have extended this framework in order to take into account the strength of arguments. The basic idea is to ignore an attack if the attacked argument is stronger than (or preferred to) its attacker. Semantics are then applied using only the remaining attacks. In this paper, we show that those proposals behave correctly when the attack relation is symmetric. However, when it is asymmetric, conflicting extensions may be computed leading to unintended conclusions. We propose an approach that guarantees conflict-free extensions. This approach presents two novelties: the first one is that it takes into account preferences at the semantics level rather than the attack level. The idea is to extend existing semantics with preferences. 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. The second novelty of our approach is that a semantics is defined as a dominance relation on the powerset of the set of arguments. The extensions (under a semantics) are the maximal elements of the dominance relation. Such an approach makes it possible not only to compute the extensions of a framework but also to compare its non-extensions. We start by proposing three dominance relations that generalize respectively stable, preferred and grounded semantics with preferences. Then, we focus on stable semantics and provide full characterizations of its dominance relations and those of its generalized versions. Complexity results are provided. Finally, we show that an instance of the proposed framework retrieves the preferred sub-theories which were proposed in the context of handling inconsistency in weighted knowledge bases.     

Argument-based agreements in agent societies

In this paper, we present an abstract argumentation framework for the support of agreement processes in agent societies. It takes into account arguments, attacks among them, and the social context of the agents that put forward arguments. Then, we define the semantics of the framework, providing a mechanism to evaluate arguments in view of other arguments posed in the argumentation process. We also provide a translation of the framework into a neural network that computes the set of acceptable arguments and can be tuned to give more or less importance to argument attacks. Finally, the framework is illustrated with an example in a real domain of a water-rights transfer market.     

Using arguments for making and explaining decisions

Arguments play two different roles in day life decisions, as well as in the discussion of more crucial issues. Namely, they help to select one or several alternatives, or to explain and justify an already adopted choice.This paper proposes the first general and abstract argument-based framework for decision making. This framework follows two main steps. At the first step, arguments for beliefs and arguments for options are built and evaluated using classical acceptability semantics. At the second step, pairs of options are compared using decision principles. Decision principles are based on the accepted arguments supporting the options. Three classes of decision principles are distinguished: unipolar, bipolar or non-polar principles depending on whether i) only arguments pros or only arguments cons, or ii) both types, or iii) an aggregation of them into a meta-argument are used. The abstract model is then instantiated by expressing formally the mental states (beliefs and preferences) of a decision maker. In the proposed framework, information is given in the form of a stratified set of beliefs. The bipolar nature of preferences is emphasized by making an explicit distinction between prioritized goals to be pursued, and prioritized rejections that are stumbling blocks to be avoided. A typology that identifies four types of argument is proposed. Indeed, each decision is supported by arguments emphasizing its positive consequences in terms of goals certainly satisfied and rejections certainly avoided. A decision can also be attacked by arguments emphasizing its negative consequences in terms of certainly missed goals, or rejections certainly led to by that decision. Finally, this paper articulates the optimistic and pessimistic decision criteria defined in qualitative decision making under uncertainty, in terms of an argumentation process. Similarly, different decision principles identified in multiple criteria decision making are restated in our argumentation-based framework.     

On the equivalence of semantics for normal logic programs

Despite the frequent comment that there is no general agreement on the semantics of logic programs, this paper shows that a number of independently proposed extensions to the stable model semantics coincide: the regular model semantics proposed by You and Yuan, the partial stable model semantics by Saccà and Zaniolo, the preferential semantics by Dung, and a stronger version of the stable class semantics by Baral and Subrahmanian. We show that these equivalent semantics can be characterized simply as selecting a particular kind of stable classes, called normal alternating fixpoints. In addition, we indicate that almost all of the previously proposed semantic frameworks coincide with that of normal alternating fixpoints. Due to its simplicity and naturalness, the framework of normal alternating fixpoints offers great potential in the study of the semantics for various nonmonotonic systems.     

TOWARD A COMPUTATIONAL ANALYSIS OF PROBABILISTIC ARGUMENTATION FRAMEWORKS

In this article we analyze probabilistic argumentation frameworks (PAFs), defined as an extension of Dung abstract argumentation frameworks in which each argument n is asserted with a probability p_n. The debate around PAFs has so far centered on their theoretical definition and basic properties. This work contributes to their computational analysis by proposing a first recursive algorithm to compute the probability of acceptance of each argument under grounded and preferred semantics and by studying the behavior of PAFs with respect to reinstatement, cycles, and changes in argument structure. The computational tools proposed may provide strategic information for agents selecting the next step in an open argumentation process and they represent a contribution in the debate about gradualism in abstract argumentation.     

The behavioural semantics of Event-B refinement

Event-B provides a flexible framework for stepwise system development via refinement. The framework supports steps for (a) refining events (one-by-one), (b) splitting events (one-by-many), and (c) introducing new events. In each of the steps events can be indicated as convergent (to be made internal) or anticipated (treatment deferred to a later refinement step). All such steps are accompanied with precise proof obligations. However, no behavioural semantics has been provided to validate the proof obligations, and no formal justification has previously been given for the application of these rules in a refinement chain. Behavioural semantics expresses a clear relationship between the first and last machines in a refinement chain. The framework we present provides a coherent justification for Abrial’s approach to refinement in Event-B, and its generalisation to interface extension: adding events to the interface. In this paper, we give a behavioural semantics for Event-B refinement, with a treatment for the first time of splitting events and of anticipated events, adding to the well-understood treatment of convergent events. To this end, we define a CSP semantics for Event-B and show how the different forms of Event-B refinement can be captured as CSP refinement. It turns out that the appropriate CSP refinement relationship is influenced by the particular Event-B development strategy taken. We present two such strategies, one allowing, the other disallowing interface extensions.