Editorial Boards and Programme Committees
Complexity of Dialogue and Argumentation
I have been involved with this field working mainly with Trevor Bench-Capon since May 2001. Argument Systems were first formalised in the mid 1980s as a mechanism for modelling reasoning (including concepts of acceptability and defeasibilty of a proposition) with particular applications to the non-classical Logics which have been applied in Artificial Intelligence work. Within this formalism several researchers advanced various concepts of `Dialogue Game' with which to investigate models of reasoning processes. At present one research paper has been submitted that presents proofs of intractability for decision problems related to the two most commonly used concepts of acceptability. Two further papers are in development. The first of these introduces formal ideas concerning dispute complexity - an aspect of dialogue games that has been largely overlooked in earlier work - and establishes that one game approach is provably `weak' in the sense that it corresponds to a simple propositional proof system (the cut-free Sequent Calculus). In consequence this game can take significantly many rounds to establish the validity of quite simple argument positions.
The article Wooldridge and Dunne (2004) formulates a model of `qualitative coalitional games' (QCGs) and characterises the computational complexity of a number of decision problesm within it. Current work stemming from this includes investigation of concepts of `goal preferences', modelling of so-called `coalitional resource games' which can be viewed as a special class of QCG; and approaches to relating game properties described by propositional logic formulae in via modal logics.
Contract and resource allocation mechanisms
Work in this area has considered both complexity questions relating to the existence of particular types of negotiation plans, (Dunne, Wooldridge and Laurence, 2003; revised article currently in submission); as well as combinatorial results concerning the worst-case lengths of such plans when these can be formulated. An important result of this work is the article Dunne (2004)
I have been working in this field with Prof. M. Wooldridge since June 2000. The model and results presented in Wooldridge(2000) have been extensively developed leading to a paper (currently in submission) which completely characterises the complexity status of single goal achievement and maintenance problems for various combinations of agent and enviroment representations. Subsequent work has involved classifying the complexity of agent design tasks in which the task is encoded as an arbitrary propositional formula - single goal problems being a special case of this - and in properties of agent design tasks specified using quantified formulae. Developing a more extensive formalism and study of its algorithmic properties form part of the research on EPSRC Grant GR/R60836/01 commencing January 2002. This aims to address issues other than existence questions, e.g. verification and synthesis of agents.
Complexity Theory of Boolean Functions