A formal approach to negotiating agents development

This paper presents a formal and executable approach to capture the behaviour of parties involved in a negotiation. A party is modeled as a negotiating agent composed of a communication module, a control module, a reasoning module, and a knowledge base. The control module is expressed as a statechart, and the reasoning module as a defeasible logic program. A strategy specification therefore consists of a statechart, a set of defeasible rules, and a set of initial facts. Such a specification can be dynamically plugged into an agent shell incorporating a statechart interpreter and a defeasible logic inference engine, in order to yield an agent capable of participating in a given type of negotiations. The choice of statecharts and defeasible logic with respect to other formalisms is justified against a set of desirable criteria, and their suitability is illustrated through concrete examples of bidding and multi-lateral bargaining scenarios.     

A theory of defeasible reasoning

Reasoning can lead not only to the adoption of beliefs, but also to the retraction of beliefs. In philosophy, this is described by saying that reasoning is defeasible. My ultimate objective is the construction of a general theory of reasoning and its implementation in an automated reasoner capable of both deductive and defeasible reasoning. the resulting system is named “OSCAR.” This article addresses some of the theoretical underpinnings of OSCAR. This article extends my earlier theory in two directions. First, it addresses the question of what the criteria of adequacy should be for a defeasible reasoner. Second, it extends the theory to accommodate reasons of varying strengths.     

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 modular translation from defeasible nets to defeasible logics

Abstract

The sceptical inheritance nets introduced in Horty et al. [Proceedings of AAAI-87 (1987):358-363] are translated into a version of Nute's defeasible logic. Moreover this translation is modular in the sense of Thomason and Horty [Non-Monotonic Reasoning. Springer-Verlag (1989):234]. Apart from the importance of relating two nonmonotonic reasoning formalisms, this result shows that the reasoning mechanisms underlying defeasible logic and defeasible nets are the same. Yet they were invented independently and set in totally different contexts. This is perhaps some evidence that the underlying nonmonotonic reasoning mechanism is mainly correct. We also observe that since defeasible logics can contain both absolute and defeasible rules, they provided a uniform setting for considering nets which contain both strict and defeasible arcs.     

Default Reasoning as Situated Monotonic Inference*

Since its inception, situation theory has been concerned with the situated nature of meaning and cognition, a theme which has also recently gained some prominence in Artificial Intelligence. Channel theory is a recently developed framework which builds on concepts introduced in situation theory, in an attempt to provide a general theory of information flow. In particular, the channel theoretic framework offers an account of fallible regularities, regularities which provide enough structure to an agent's environment to support efficient cognitive processing but which are limited in their reliability to specific circumstances. This paper describes how this framework can lead to a different perspective on defeasible reasoning: rather than being seen as reasoning with incomplete information, an agent makes use of a situated regularity, choosing to use the regularity that seems best suited (trading off reliability and simplicity) to the circumstances it happens to find itself in. We present a formal model for this task, based on the channel theoretic framework, and sketch how the model may be used as the basis for a methodology of defeasible situated reasoning, whereby agents reason with simple monotonic regularities but may revise their choice of regularity on learning more about their circumstances.     

Towards a Formal Account of Reasoning about Evidence: Argumentation Schemes and Generalisations

This paper studies the modelling of legal reasoning about evidence within general theories of defeasible reasoning and argumentation. In particular, Wigmore's method for charting evidence and its use by modern legal evidence scholars is studied in order to give a formal underpinning in terms of logics for defeasible argumentation. Two notions turn out to be crucial, viz. argumentation schemes and empirical generalisations.     

Self-defeating arguments

An argument is self-defeating when it contains defeaters for some of its own defeasible lines. It is shown that the obvious rules for defeat among arguments do not handle self-defeating arguments correctly. It turns out that they constitute a pervasive phenomenon that threatens to cripple defeasible reasoning, leading to almost all defeasible reasoning being defeated by unexpected interactions with self-defeating arguments. This leads to some important changes in the general theory of defeasible reasoning.     

An argumentation framework in default logic

This article presents a formal theory about nontrivial reasoning with inconsistent information, applicable, among other things, to defeasible reasoning. The theory, which is inspired by a formal analysis of legal argument, is based on the idea that inconsistency tolerant reasoning is more than revising an unstructural set of premises; rather it should be regarded as constructing and comparing arguments for incompatible conclusions. This point of view gives rise to two important observations, both pointing at some flaws of other theories. The first is that arguments should be compared as they are constructed, viz. step-by-step, while the second observation is that a knowledge representation language is needed with a defeasible conditional, since the material implication gives rise to arguments which are not constructed in actual reasoning. Accordingly, a nonmonotonic logic, default logic, is chosen as the formalism underlying the argumentation framework. The general structure of the framework allows for any standard for comparing pairs of arguments; in this study two such standards are investigated, based on specificity and on orderings of the premises.     

OSCAR: a general theory of rationality

Abstract

The enterprise is the construction of a general theory of rationality, and its implementation in an automated reasoning system named OSCAR. The paper describes a general architecture for rational thought. This includes both theoretical reasoning and practical reasoning, and builds in important interconnections between them. It is urged that a sophisticated reasoner must be an introspective reasoner, capable of monitoring its own reasoning and reasoning about it. An introspective reasoner is built on top of a non-introspective reasoner that represents the system's default reasoning strategies. The introspective reasoner engages in practical reasoning about reasoning in order to override these default strategies. The paper concludes with a discussion of some aspects of the default reasoner, including the manner in which reasoning is interest driven, and the structure of defeasible reasoning.     

Reasoning About Agent Types and the Hardest Logic Puzzle Ever

In this paper, we first propose a simple formal language to specify types of agents in terms of necessary conditions for their announcements. Based on this language, types of agents are treated as ‘first-class citizens’ and studied extensively in various dynamic epistemic frameworks which are suitable for reasoning about knowledge and agent types via announcements and questions. To demonstrate our approach, we discuss various versions of Smullyan’s Knights and Knaves puzzles, including the Hardest Logic Puzzle Ever (HLPE) proposed by Boolos (in Harv Rev Philos 6:62–65, 1996). In particular, we formalize HLPE and verify a classic solution to it. Moreover, we propose a spectrum of new puzzles based on HLPE by considering subjective (knowledge-based) agent types and relaxing the implicit epistemic assumptions in the original puzzle. The new puzzles are harder than the previously proposed ones in the literature, in the sense that they require deeper epistemic reasoning. Surprisingly, we also show that a version of HLPE in which the agents do not know the others’ types does not have a solution at all. Our formalism paves the way for studying these new puzzles using automatic model checking techniques.     

On a rule-based interpretation of default conditionals

In nonmonotonic reasoning, a default conditional α→β has most often been informally interpreted as a defeasible version of a classical conditional, usually the material conditional. There is however an alternative interpretation, in which a default is regarded essentially as a rule, leading from premises to conclusion. In this paper, we present a family of logics, based on this alternative interpretation. A general semantic framework under this rule-based interpretation is developed, and associated proof theories for a family of weak conditional logics is specified. Nonmonotonic inference is easily defined in these logics. Interestingly, the logics presented here are weaker than the commonly-accepted base conditional approach for defeasible reasoning. However, this approach resolves problems that have been associated with previous approaches.      

Defeasible reasoning: A discussion of some intuitions

In this article, we discuss some issues related to the intuitions of defeasible reasoning, in particular floating conclusions, reinstatement, and zombie paths. Defeasible logic serves as the formal basis for our analysis. We also make some comments on the comparison between defeasible logics and the well‐founded semantics of extended logic programs with priorities. © 2006 Wiley Periodicals, Inc. Int J Int Syst 21: 545–558, 2006.     

On the evaluation of argumentation formalisms

Argumentation theory has become an important topic in the field of AI. The basic idea is to construct arguments in favor and against a statement, to select the “acceptable” ones and, finally, to determine whether the original statement can be accepted or not. Several argumentation systems have been proposed in the literature. Some of them, the so-called rule-based systems, use a particular logical language with strict and defeasible rules. While these systems are useful in different domains (e.g. legal reasoning), they unfortunately lead to very unintuitive results, as is discussed in this paper. In order to avoid such anomalies, in this paper we are interested in defining principles, called rationality postulates, that can be used to judge the quality of a rule-based argumentation system. In particular, we define two important rationality postulates that should be satisfied: the consistency and the closure of the results returned by that system. We then provide a relatively easy way in which these rationality postulates can be warranted for a particular rule-based argumentation system developed within a European project on argumentation.     

Dialectical Argumentation with Argumentation Schemes: An Approach to Legal Logic

This paper describes an approach to legal logic based on the formal analysis of argumentation schemes. Argumentation schemes a notion borrowed from the .eld of argumentation theory - are a kind of generalized rules of inference, in the sense that they express that given certain premises a particular conclusion can be drawn. However, argumentation schemes need not concern strict, abstract, necessarily valid patterns of reasoning, but can be defeasible, concrete and contingently valid, i.e., valid in certain contexts or under certain circumstances. A method is presented to analyze argumentation schemes and it is shown how argumentation schemes can be embedded in a formal model of dialectical argumentation.     

A creative abduction approach to scientific and knowledge discovery

In this paper we explore the range of applicability of abductive reasoning for knowledge discovery. In particular, we discuss a novel form of abduction, called creative abduction, where new knowledge is generated in the process of explaining observed events, and demonstrate its relevance to knowledge discovery. The main contribution of this paper is twofold: First, we show that creative abduction can be used to infer a disposition explaining local temporal regularities. In the presence of multiple correlated regularities, this form abduction may significantly unify a given corpus of knowledge, corresponding to theory formation in scientific discovery. Second, we present a weaker form of creative abduction that infers a goal (e.g. interest) from simple ‘condition-effect’ rules called ‘transitions’. If multiple transitions are correlated, the weaker form of creative abduction can be used to identify, e.g. clusters of Web users, as done in Web usage mining. We will focus on the formal underpinnings of this new form of abduction that seems readily applicable to a wide range of practical knowledge discovery problems.     

Reflecting on Social Influence in Networks

In many social contexts, social influence seems to be inescapable: the behavior of others influences us to modify ours, and vice-versa. However, social psychology is full of examples of phenomena where individuals experience a discrepancy between their public behavior and their private opinion. This raises two central questions. First, how does an individual reason about the behavior of others and their private opinions in situations of social influence? And second, what are the laws of the resulting information dynamics? In this paper, we address these questions by introducing a formal framework for representing reasoning about an individual’s private opinions and public behavior under the dynamics of social influence in social networks. Moreover, we dig deeper into the involved information dynamics by modeling how individuals can learn about each other based on this reasoning. This compels us to introduce a new formal notion of reflective social influence. Finally, we initialize the work on proof theory and automated reasoning for our framework by introducing a sound and complete tableaux system for a fragment of our logic. Furthermore, this constitutes the first tableau system for the “Facebook logic” of J. Seligman, F. Liu, and P. Girard.     

An improved factor based approach to precedential constraint

In this article I argue for rule-based, non-monotonic theories of common law judicial reasoning and improve upon one such theory offered by Horty and Bench-Capon. The improvements reveal some of the interconnections between formal theories of judicial reasoning and traditional issues within jurisprudence regarding the notions of the ratio decidendi and obiter dicta. Though I do not purport to resolve the long-standing jurisprudential issues here, it is beneficial for theorists both of legal philosophy and formalizing legal reasoning to see where the two projects interact.     

Application of formal languages in polynomial transformations of instances between NP-complete problems

We propose the usage of formal languages for expressing instances of NP-complete problems for their application in polynomial transformations. The proposed approach, which consists of using formal language theory for polynomial transformations, is more robust, more practical, and faster to apply to real problems than the theory of polynomial transformations. In this paper we propose a methodology for transforming instances between NP-complete problems, which differs from Garey and Johnson’s. Unlike most transformations which are used for proving that a problem is NP-complete based on the NP-completeness of another problem, the proposed approach is intended for extrapolating some known characteristics, phenomena, or behaviors from a problem A to another problem B. This extrapolation could be useful for predicting the performance of an algorithm for solving B based on its known performance for problem A, or for taking an algorithm that solves A and adapting it to solve B.