ECS Intranet:
Automated Negotiation and Argumentation
Autonomous agents are being increasingly used in a wide range of industrial and commercial domains. These agents have a high degree of self determination -- they decide for themselves what, when and under what conditions their actions should be performed. In most cases, such agents need to interact with other autonomous agents to achieve their objectives (either because they do not have sufficient capabilities or resources to complete their problem solving alone or because there are interdependencies between the agents). The objectives of these interactions are to make other agents undertake a particular course of action (e.g. perform a particular service), modify a planned course of action (e.g. delay or bring forward a particular action so that there is no longer a conflict), or come to an agreement on a common course of action. Since the agents have no direct control over one another, they must persuade their acquaintances to act in particular ways (they cannot simply instruct them). The paradigm case of persuasion is negotiation : a process by which agents come to a mutually acceptable decision on some matter
Given its ubiquity and importance in many different contexts, negotiation theory covers a broad range of phenomena and encompasses multifarious approaches (e.g. from AI, Social Psychology and Game Theory). Despite this variety, however, automated negotiation research can be considered to deal with three broad topics:
- Negotiation Protocols: the set of rules that govern the interaction. This covers the permissible types of participants (e.g. the negotiators and any relevant third parties), the negotiation states (e.g. accepting bids, negotiation closed), the events that cause negotiation states to change (e.g. no more bidders, bid accepted) and the valid actions of the participants in particular states (e.g. which messages can be sent by whom, to whom, at what stage).
- Negotiation Objects: the range of issues over which agreement must be reached. At one extreme, the object may contain a single issue (such as price), while on the other hand it may cover hundreds of issues (related to price, quality, timings, penalties, terms and conditions, etc.). Orthogonal to the agreement structure, and determined by the negotiation protocol, is the issue of the types of operation that can be performed on it. In the simplest case, the structure and the contents of the agreement are 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 in the negotiation object (i.e. they can make counter-proposals to ensure the agreement better fits their negotiation objectives). Finally, participants might be allowed to dynamically extend the structure of the negotiation object (e.g. a car salesman may offer one year's free insurance in order to clinch the deal).
- Agents' Decision Making Models: the decision making apparatus the participants employ 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 be made, are influenced by the protocol in place, by the nature of the negotiation object, and by the range of operations that can be performed on it.
The relative importance of these three topics varies according to the negotiation and environmental context. Thus, in some circumstances the negotiation protocol is the dominant concern. For example, the system designer may determine that the negotiation is best organised using a particular form of auction (e.g. English, Dutch, Vickrey, First-Price Sealed Bid). This mechanism design choice constrains the types of operations that can be performed on the negotiation object (no counter-proposals or issue extensions) and prescribes the behaviour of the agents' decision making models (e.g. strategic behaviour is pointless and agents should simply bid up to their true reservation value). In other cases, however, the agent's decision making model is the dominant concern. Here, the protocol does not prescribe an agent's behaviour and there is scope for strategic reasoning to determine the best course of action. In such cases, the relative success of two agents is determined by the effectiveness of their reasoning model-the better the model, the greater the agent's reward.
