To appear in: Int Journal of Group Decision and Negotiation GDN2000 Keynote Paper1Automated Negotiation: Prospects, Methods and ChallengesN. R. Jennings1, P. Faratin2, A. R. Lomuscio3, S. Parsons4, C. Sierra5 and M. Wooldridge41Dept. of Electronics and Computer Science, University of Southampton,Southampton SO17 1BJ, [email protected]. of Electronic Engineering, Queen Mary and Westfield College,University of London, London E1 4NS, [email protected]. of Computing, Imperial College of Science, Technology and Medicine,London SW7 2BZ, [email protected]. of Computer Science, University of Liverpool,Liverpool L69 7ZF, UK.{s.d.parsons, m.j.wooldridge}@csc.liv.ac.uk5Artificial Intelligence Research Institute, Spanish Scientific Research Council,Campus UAB, 08193 Bellaterra, Barcelona, [email protected] appear in: Int Journal of Group Decision and Negotiation GDN2000 Keynote Paper21. IntroductionAn increasing number of computer systems are being viewed in terms of autonomous agents.There are two main drivers to this trend. Firstly, agents are being advocated as a next generationmodel for engineering complex, distributed systems [13], [44]. Secondly, agents are being usedas an overarching framework for bringing together the component AI subdisciplines that arenecessary to design and build intelligent entities [24], [32]. While there is still much debateabout the precise nature of agenthood, an increasing number of researchers find the followingcharacterisation useful [44]:an agent is an encapsulated computer system that is situated in some environmentand that is capable of flexible, autonomous action in that environment in order tomeet its design objectivesThere are a number of points about this definition that require elaboration. Agents are: (i)clearly identifiable problem solving entities with well-defined boundaries and interfaces; (ii)situated (embedded) in a particular environment—they receive inputs related to the state oftheir environment through sensors and they act on the environment through effectors; (iii)designed to fulfill a specific purpose—they have particular objectives (goals) to achieve; (iv)autonomous—they have control both over their internal state and over their own behaviour; (v)capable of exhibiting flexible problem solving behaviour in pursuit of their design objectives—they need to be both reactive (able to respond in a timely fashion to changes that occur in theirenvironment) and proactive (able to act in anticipation of future goals) [45].When adopting an agent-oriented view of computation, it is readily apparent that most problemsrequire or involve multiple agents: to represent the decentralised nature of the problem, the mul-tiple loci of control, the multiple perspectives and/or the competing interests [6]. Moreover,these agents will need to interact with one another, either to achieve their individual objectivesor to manage the dependencies that follow from being situated in a common environment [7],To appear in: Int Journal of Group Decision and Negotiation GDN2000 Keynote Paper3[14]. These interactions can vary from simple information interchanges, to requests for partic-ular actions to be performed and on to cooperation (working together to achieve a common ob-jective) and coordination (arranging for related activities to be performed in a coherent manner).However, perhaps the most fundamental and powerful mechanism for managing inter-agent de-pendencies at run-time is negotiation—the process by which a group of agents come to a mu-tually acceptable agreement on some matter. Negotiation underpins attempts to cooperate andcoordinate (both between artificial and human agents) and is required both when the agents areself interested and when they are cooperative. It is so central precisely because the agents areautonomous. For an agent to influence an acquaintance, the acquaintance needs to be convincedthat it should act in a particular way. The means of achieving this state are to make proposals,trade options, offer concessions, and (hopefully) come to a mutually acceptable agreement. Inshort, to negotiate.Given its ubiquity and importance in many different contexts, negotiation theory incorporates abroad range of phenomena and makes use of many different approaches (e.g. from AI, SocialPsychology and Game Theory). Despite this variety, however, automated negotiation researchcan be considered to deal with three broad topics (see [21] for a more detailed classificationscheme):• Negotiation Protocols: the set of rules that govern the interaction. This covers the per-missible types of participants (e.g. the negotiators and any relevant third parties), thenegotiation states (e.g. accepting bids, negotiation closed), the events that cause nego-tiation states to change (e.g. no more bidders, bid accepted) and the valid actions ofthe participants in particular states (e.g. which messages can be sent by whom, towhom, at what stage).To appear in: Int Journal of Group Decision and Negotiation GDN2000 Keynote Paper4• Negotiation Objects: the range of issues over which agreement must be reached. Atone extreme, the object may contain a single issue (such as price), while on the otherhand it may cover hundreds of issues (related to price, quality, timings, penalties,terms and conditions, etc.). Orthogonal to the agreement structure, and determined bythe negotiation protocol, is the issue of the types of operation that can be performedon agreements. In the simplest case, the structure and the contents of the agreementare fixed and participants can either accept or reject it (i.e. a take it or leave it offer).At the next level, participants have the flexibility to change the values of the issues inthe negotiation object (i.e. they can make counter-proposals to ensure the agreementbetter fits their negotiation objectives). Finally, participants might be allowed todynamically alter (by adding or removing issues) the structure of the negotiationobject (e.g. a car salesman may offer one year’s free insurance in order to clinch thedeal).• Agents’ Decision Making Models: the decision making apparatus the participantsemploy to act in line with the negotiation protocol in order to achieve their objectives.The sophistication of the model, as well as the range of decisions that have to bemade, are influenced by the protocol in place, by the nature of the negotiation object,and by the range of operations that can be