Abstract
Agents are viewed as the next significant software abstraction, and it is expected they will become as ubiquitous as graphical user interfaces are today. Agents are specialized programs designed to provide services to their users. Multiagent systems have a key capability to reallocate tasks among the members, which may result in significant savings and improvements in many domains, such as resource allocation, scheduling, e-commerce, and so forth. In the near future, agents will roam the Internet, selling and buying information and services. These agents will evolve from their present day form - simple carriers of transactions - to efficient decision makers. It is envisaged that the decisionmaking processes and interactions between agents will be very fast (Kephart, 1998). The importance of automated negotiation systems is increasing with the emergence of new technologies supporting faster reasoning engines and mobile code. A central part of agent systems is a sophisticated reasoning engine that enables the agents to reallocate their tasks, optimize outcomes, and negotiate with other agents. The negotiation strategy used by the reasoning engine also requires high-level inter-agent communication protocols, and suitable collaboration strategies. Both of these sub-systems – a reasoning engine and a negotiation strategy - typically result in complicated agent designs and implementations that are difficult to maintain. Activities of a set of autonomous agents have to be coordinated. Some could be mobile agents, while others are static intelligent agents. We usually aim at decentralized coordination, which produces the desired outcomes with minimal communication. Many different types of contract protocols (cluster, swaps, and multiagent, as examples) and negotiation strategies are used. The evaluation of outcomes is often based on marginal cost (Sandholm, 1993) or game theory payoffs (Mass-Colell, 1995). Agents based on constraint technology use complex search algorithms to solve optimization problems arising from the agents’ interaction. In particular, coordination and negotiation strategies in the presence of incomplete knowledge are good candidates for constraint-based implementations.
TopSelected Negotiation And Reasoning Techniques
Negotiation space is determined by two components: negotiation protocol and negotiation strategy. The negotiation protocol defines the rules of behavior between the participants in terms of interactions, deals, bidding rules, temporal constraints and offers, as components of the protocol. Two agents must first agree on the negotiation protocol before any interaction starts.
The negotiation strategy is a specification of the sequence of actions the agent intends to make during the negotiation. Strategies should be compatible with the negotiation protocol. The focus of any negotiation strategy is to maximize outcomes within the rational boundaries of the environment. The classification of negotiation strategies is not an easy task since the negotiation strategy can be realized by any algorithm capable of evaluating outcomes, computing appropriate actions, and following the information exchange protocol.
The negotiation mechanism is the actual implementation of negotiation strategy and negotiation protocol. This field is evolving fast, with emergence of new agent platforms, wireless encounters and extended mobility.
Negotiation is a search process. The participants jointly search a multi-dimensional space (e.g., quantity, price, and delivery) in an attempt to find a single point in the space at which they reach mutual agreement and meet their objectives. The market mechanism is used for many-to-many coupling or interactions between participants. Auctions are more appropriate for one-to-many negotiations. The market mechanism often suffers from inability to efficiently scale down (Osborne, 1990) to smaller numbers of participants. On the other hand, one-to-many interactions are influenced by strategic considerations and involve integrative bargaining, where agents search for Paretto efficient agreements (tradeoffs).
Key Terms in this Chapter
Negotiation Strategy: Specification of the sequence of actions the agent intends to make during the negotiation.
Agent: A program designed to provide specialized and well-defined services. An agent can be static – executing on the computer where it was installed, or mobile – executing on computer nodes in a network.
This work was previously published in Encyclopedia of Information Science and Technology: edited by M. Khosrow-Pour, pp. 810-815, copyright 2005 by Information Science Reference, formerly known as Idea Group Reference (an imprint of IGI Global).
Genetic Algorithm: Class of algorithms used to find approximate solutions to difficult-to-solve problems, inspired and named after biological processes of inheritance, mutation, natural selection, and generic crossover. Genetic algorithms are a particular class of evolutionary algorithms.