![\includegraphics[width=1.4\textwidth]{nego-ana.eps}](img1.gif)
Katia P. Sycara Dajun Zeng
The Robotics Institute
Carnegie Mellon University, Pittsburgh, PA 15213
katia@cs.cmu.edu Dajun.Zeng@cs.cmu.edu
Negotiation is an ill-structured and complex process. Negotiating parties are driven to reach mutually beneficial deals through extensive information exchanges, offers and counter offers. Part of the reason why negotiation is notoriously hard to analyze formally can be attributed to the fact that under most circumstances the involved parties are neither strictly competitive nor completely cooperative. This leaves much room for parties that are negotiating to interact strategically--they are trying to outsmart each other; they are trying to exploit the weakness of their opposites' strategies; they are trying to influence the other parties' beliefs and actions to increase their own utility, etc. On the other hand, they do want to reach an agreement under given constraints (such as deadline constraints, or negotiation budget constraints). Otherwise, each involved party may be worse off and lose the potential benefits of collaboratively getting part of some needed resource or tasks done that cannot be achieved by any single party acting alone.
Since the term negotiation has been overloaded in many different contexts (e.g., linguists refer to dialogue to clarify a concept as ``negotiation of meaning''), we use the following figure to summarize our understanding of how the concept of negotiation has been articulated in the DAI community. In the subsequent paragraphs, we describe in more detail the taxonomy of negotiation shown in this figure. The figure also illustrates the relationships of various types of DAI work under the same umbrella of negotiation.
Some researchers equate negotiation to agent coordination[Lander and Lesser, 1993,Durfee and Lesser, 1989]. However, agent coordination is not only for conflict resolution or conflict avoidance, but also for the integration of problem solving capabilities and/or results[Davis, R. and Smith, 1983]. The most common usage of negotiation, however, presumes the presence of conflicts or discrepancies over some variables (such as resources, payoffs, etc.) shared among agents[Bond, A.H. and Gasser, 1988]. There are mainly two lines of work under conflict resolution: one focuses on the ``noncooperative'' aspect, the other on the ``cooperative'' aspect. Most of the current work on game theory explores the mathematical definitions and properties of strategic interactions among agents. This line of work is mainly concerned with the noncooperative side of agent interaction. Recent years have seen a trend in both the AI community and the Game Theory community to relax some of the rigid assumptions made in traditional game theory; this is motivated by the desire to provide computational mechanisms to enable intelligent negotiation support. We labeled this line of work under ``bounded rationality'' and placed it under the ``noncooperative'' work in sibling to to game theoretic models.
Much of DAI work falls into the category of Cooperative Distributed Problem Solving, including distributed resource allocation and optimization, conflict resolution in a cooperative environment, team work, etc. Researchers in this area typically use negotiation as a metaphor for interactions among collaborating agents that share certain views and objectvies which are of a global nature.
We argue that modeling and solving noncooperative negotiation problems is fundamentally different from cooperative negotiation problems. The key difference is that the underlying rationality principles or proper optimization criteria for noncooperative negotiation are ill defined for negotiation problems due to the conflicting nature of the negotiating parties' utilities. In effect, to a large extent the negotiation models have to do with how to define the goals or objectives of negotiation and why these objectives are proper. Only after these specific objective functions or rationality principles have been identified, optimization or search can come into play. Take an example of distributed scheduling. In distributed scheduling[Sycara, K., Roth, S., Sadeh, N. and Fox, 1991], there are multiple scheduling agents. Each of these agents has to find an optimal or near-optimal schedule for each area of the factory. Conflicts arise because resources/machines are shared among these agents. Nevertheless, there is a global optimization criterion, i.e., to optimize the performance of the whole factory (measured by possibly conflicting objectives such as minimizing tardiness, minimizing work-in-process inventory, etc.). Whether the optmization of the factory is solved by a centralized global scheduler or by a team of factory area schedulers is a distinction of problem solving methodology rather than a distinction of problem formulation. Typically, centralized/distributed scheduling (or any other problem) is formulated as constraint satisfaction or constrained optimization problems where the ``negotiation'' process is iterative constraint relaxation instead of a full fledged strategic interaction episode as expected in ``noncooperative'' negotiation scenarios.
Negotiation as phenomenon has been extensively discussed in game-theoretic, economic, and management science literatures for decades. Developing AI systems to provide intelligent negotiation support has been one of the major endeavors in the DAI community. Recent growing interest in autonomous interacting software agents and their potential application in areas such as electronic commerce has given increased importance to automated negotiation. In addition, using negotiation as a metaphor for generic agent coordination protocols is gaining popularity among researchers and practitioners.
Our research has been motivated by exploring many aspects of negotiation and in turn providing intelligent support for real world negotiation tasks (including both human-to-human and software agent-to-software agent/human negotiation) as well as using negotiation as agent coordination protocols. This extended abstract summarizes our previous work on negotiation and then describes some new directions that we believe would have important implications for future research on negotiation and DAI.
In reality, especially viewed from the noncooperative perspective of negotiation, the negotiation process incorporates intangibles such as the negotiators' skills and experience, the parties' values, beliefs, perceptions and behaviors[Sycara, 1990b]. What makes the problem even more complex is the dynamic nature of negotiations. The interaction of the participants during negotiations engenders changes in their goals, the ways they perceive the issues, their utilities associated with various outcomes and their reservation prices. These changes are necessary for achievement of an agreed upon settlement. Using persuasive arguments is a mechanism for a negotiator to influence the beliefs of another agent and hence influence the acceptability of an offer. Argumentation is an effective mechanism for influencing beliefs because of (a) the bounded rationality of computational agents, and (b) lack of full information in the negotiation process.
We have developed a domain independent model of noncoorperative negotiation that we illustrated in the domain of labor mediation. Our model has been implemented in a computer program, the PERSUADER, which resolves labor management disputes [Sycara, 1990a]. PERSUADER enables agents to negotiation and pursue deals to maximize their respective individual utility. The system has the additional mechanisms for automated generation of persuasive arguments. Persuasive argumentation is used in the negotiation process in two ways: (a) when negotiation reaches impasse, and (b) to improve the quality of the current deal.
Thus, besides the needed capability to seek deals that maximize an agent's individual utility, the agent needs the ability to (a) represent and maintain belief models, (b) reason about other agents' beliefs, and (c) influence other agents' beliefs and behavior1([Sycara, 1991]). Persuasive argumentation lies at the heart of bounded rationality negotiation. It is the process used to cohere the behavior of the parties and guide the process toward solution convergence. In a nutshell, the argumentation process can be described as follows: an agent reasons about another agent using is own model of that other agent, finds as many ways as the model will allow to affect the other agent's outcomes (behavior), and uses them selectively to influence the other agent.
In PERSUADER, construction of arguments is performed using integration of Case-Based Reasoning, graph search and approximate estimation of agents' utilities[Sycara, 1989]. The PERSUADER plans iteratively by interacting with the agents, using their feedback in refining and repairing deals, and in generating persuasive arguments.
In [Kraus et al., 1993,Kraus et al., 1998], we developed a formal logic that forms a basis for the development of a formal axiomatization system for argumentation. This logical model of the mental states of the agents is based on a representation of their beliefs, desires, intentions and goals. Argumentation is explicitly represented in logic terms as an iterative process of exchanges among agents to persuade each other and bring about a change in intentions. We have also identified a set of commonly used argumentation generation strategies, such as ``Promise of a future reward'', ``Appeal to past promise'', ``Appeal to Self Interest'', etc., and provided formal specifications for these strategies. This formal work enables the construction of automated negotiation agents that can take full advantage of logical reasoning mechanisms and also makes it possible to verify systematically whether the agents built upon this logic are ensured to demonstrate certain desirable behaviors (or to avoid certain undesirable behaviors).
Most research on multiagent systems has considered loosely coupled agents that coordinate their actions for mutual benefit. In most of these environments, agent interaction occurs only when one agent has data, facts, views, and solutions that are of interest to other agents, or when agents need to resolve their conflicts. In other words, coordination activity, although essential, does not constitute a substantial part of an agent's effort to achieve its goal. In [Liu and Sycara, 1995], we consider an environment where agents' tasks are tightly coupled in the sense that (1) there are only enabling relationships among subtasks and each task usually consists of more than two subtasks, thus creating cascading effects; (2) subtasks are distributed among agents and enabling relationships among agents are of multi-directions, e.g., for task1, A * B * C * D ; for task2, B * D * C * A, etc., where A, B, C, D are agents, and * represents an enabling relationship, thus creating complex cause-effect relationships among agents; (3) the objective function is related to task completion time only and can not be broken down into "quality" function of subtasks, in other words, agents have no local utility function to guide their decisions. Therefore, agents need to coordinate their actions constantly and extensively in order to both complete their tasks and improve system performance. The multiagent system also needs to operate in real time that involves both scheduling and task execution. The characteristics of the environment require substantial coordination among agents, but exclude time-consuming, elaborate coordination activities.
For this real-time multi-agent negotiation task, we present an approach that consists of a standard operating procedure and a look-ahead coordination[Liu and Sycara, 1997]. The standard operating procedure regulates task coupling and minimizes communication. The look-ahead coordination enhances the agents' local visibility and provides indicative information for decision adjustment. The goal of our approach is to prune decision myopia while maintaining system responsiveness in real-time, dynamic environments. Experimental results in job shop scheduling problems show that (1) the look-ahead coordination significantly enhances the performance of the standard operating procedure in solution quality, (2) the approach is capable of producing solutions of very high quality in a real-time environment.
Meeting scheduling as a representative multi-agent negotiation task has been examined rather extensively in the DAI literature. In [Liu and Sycara, 1994], we present an approach based on explicit modeling and communicating of constraints and preferences among the computational agents working for meeting attendees. These agents are capable of negotiating and relaxing their constraints in order to find and reach agreements on schedules with high joint utility. One of the most important aspects of this approach is that agents can react and revise the schedule in response to dynamic changes which are the major reason why meeting scheduling is nontrivial.
In [Garrido and Sycara, 1996], we view meeting scheduling as a distributed task where each agent knows its user's preferences and calendar availability in order to act on behalf of its user. Each potential attendee takes into account his/her own meeting preferences and calendar availability. Again, we address the problems associated with dynamic changes in the environments--it is almost always the case that each attendee has some uncertain and incomplete knowledge about the preferences and calendar of the other attendees; in fact, people usually try to keep their calendar and preference information private. During the meeting scheduling process, all attendees have to consider the main group goal (i.e. to schedule a meeting) as well as their individual goals (i.e. to satisfy their individual preferences).
We experimentally explore how some of meeting scheduling parameters affect the meeting scheduling efficiency and quality. One of our major goals is to observe how the calendar and preference privacy issues affect the efficiency and the joint quality of the meeting under different experimental scenarios. The results show that the meeting scheduling performance is stable when agents try to keep their calendar and preference information private. The lessons we learned from this study can be potentially useful for researchers who are building distributed systems with truly autonomous and independent agents in other domains where no agent plays a fixed role as a control agent.
Recent growing interest in autonomous interacting software agents and their potential application in areas such as electronic commerce has given increased importance to automated negotiation. Much DAI and game-theoretic research deals with coordination and negotiation issues by giving pre-computed solutions to specific problems. There has been much research reported on developing theoretical models in which learning plays an eminent role, especially in the area of adaptive dynamics of games. However, to build autonomous agents that improve their negotiation competence based on learning from their interactions with other agents is still an emerging area.
We are developing autonomous agents capable of reasoning based on experience and improving their negotiation behavior incrementally. Learning in negotiation is closely coupled with the issue of how to model the overall negotiation process, i.e., what negotiation protocols are adopted. Standard game-theoretic models tend to focus on outcomes of negotiation in contrast to the negotiation process itself. DAI research emphasizes special protocols articulating compromises while trying to minimize the potential interactions or communications of the involved agents. Since we are motivated by a different set of research issues, such as including effective learning mechanisms in the negotiation process, we adopt a different modeling framework, i.e., a sequential decision making paradigm.
In [Zeng and Sycara, 1998], we present such a sequential decision making model, called BAZAAR, which is able to learn. We address multi-agent learning issues in BAZAAR by explicitly modeling beliefs about the negotiation environment and the participating agents under a probabilistic framework using a Bayesian learning representation and updating mechanism. Both theoretical analysis and initial experimental results in a simple bargaining scenario show that learning is indeed beneficial in the sequential negotiation model.
Our early work has explored various aspects of negotiation process including argumentation generation and formalization, adaptivity and learning in negotiation, and real-time agent coordination based on negotiation paradigm.
With the explosive growth of internet activity, there will be an increasing reliance on intelligent software agents for electronic commerce and information retrieval. In fact, it will make increasing economic sense to have autonomous, specialized, self-interested agents that negotiate with each other to accomplish tasks.
In such automated negotiation systems, an important problem is the valuation of potential contracts between agents. Agents need to value contracts in order to select the most profitable one from several competing offers. This problem has not received rigorous treatment in the intelligent agent community. In [Sycara, 1997], we have proposed a novel approach to valuing contracts that exploits parallels with financial options, for which there is a well-established, elegant mathematical pricing theory. Both contracts and options have payoffs that depend on uncertain future events. Contracts with decommitment features can be viewed as American options, which by definition can be exercised at any time before expiration. There are some aspects of contracts that have no analogues in financial options. These include contracts with quality guarantees, and sub-contracting. We are currently working on extending option pricing theory in interesting ways to value such contracts. The results of our research should be applicable to contracts between agents as well as ``real-world'' contracts. We will experimentally and analytically study the role of our valuation methods as economic mechanisms, and characterize their effect on global system behavior.
On the practical side, electronic commerce and the vast amounts of real-time information available are reshaping the way enterprises conduct business. We are developing a new computational infrastructure and models that are needed for a business to make better decisions through effective use of this information base. One of the key issues is how to deal with the inherent multi-issue and dynamic nature of the multi-agent decision making in the electronic marketplace. We are developing a system called MINTEC (Multi-Issue Negotiation Tool for Electronic Commerce)[Zeng and Sycara, 1999] that provides efficient tradeoffs along different dimensions of evaluation criteria and offers real-time decision support.