Jonathan Wilkenfeld

University of Maryland, College Park
Department of Government and Politics
College Park, MD

E-mail: jwilkenf@bss2.umd.edu

Negotiation and Cooperation in Multi-Agent Environments

National Science Foundation
Grant No. IRI-9423967


Principal Investigators:

Prof. Jonathan Wilkenfeld
Department of Government and Politics
University of Maryland at College Park

Prof. Sarit Kraus
Institute for Advanced Computer Studies
University of Maryland at College Park


As the research in intelligent systems has progressed steadily over the past decade, it has become increasingly clear that there are classes of complex problems which cannot be solved by a single system in isolation; they require several systems to work together interactively in a cooperative framework. Furthermore, there are heterogeneous intelligent systems that were built in isolation, and their cooperation is necessary to achieve a new common goal. In situations where multiple agents are acting on different goals in the same environment, cooperation may be beneficial to all agents.

This project involves the use of a strategic-negotiation model to achieve inter-agent cooperation [3,4,6]. During the strategic-negotiations agents communicate their respective desires and compromise to reach mutually beneficial agreements. The model provides a unified solution to a wide range of problems, and thus is appropriate for agents acting in dynamic real-world domains. Our research applies the model in three such domains: large databases, intelligent software agents, and human-computer negotiations.

Strategic-negotiation is a process that may include several iterations of offers and counter offers. A major consideration in this domain has been to reduce overhead costs resulting from planning and negotiation time. This research examines resource allocation and task distribution problems among autonomous agents. The objective is the development of an automated agent capable of efficient cooperation with other agents in its environment.

In our strategic model there are N agents. Each agent is self motivated and tries to maximize its own utility function. In each period t of the negotiations, if the negotiation has not terminated earlier, an agent whose turn it is to make an offer at time t, will suggest a possible agreement (with respect to the specific negotiation issue), and each of the other agents may either accept the offer, or reject it, or opt out of the negotiation. If an offer is accepted by all the agents, then the negotiation ends, and this offer is implemented. If at least one of the agents opts out of the negotiation, then the negotiation ends and a conflictual outcome results. If no agent has chosen 'Opt,' but at least one of the agents has rejected the offer, the negotiation proceeds to period t+1, and the next agent makes a counter-offer, the other agents respond, and so on. We present below some of our recent results in applying the strategic model and other approaches to different multi-agent environments.

Data allocation in multi-server environments
We have used the strategic model for data allocation in multi-server environments [18]. In such situations, there is a set of several (more than two) information servers which are connected by a communication network. Each server is located in a different geographical area and receives queries from clients in its area. In response to a client's query, a server sends back information stored locally or information stored in another server, which it retrieves from that server. A specific example of such a distributed knowledge system is the Data and Information System component of the Earth Observing System (EOSDIS) of NASA. It is a distributed system which supports the archiving and distribution of data at multiple and independent data centers. The information is clustered in datasets (A dataset corresponds to a cluster in information retrieval, and to a file in the file allocation problem.)

When a set of new datasets arrives, each new dataset has to be allocated to one of the servers by mutual agreement among all of them. However, each server has its own interests and wants to maximize its own utility, and thus the servers may be in conflict concerning where to locate the new datasets. Furthermore, the servers have no common interest and no central controller which can be used to resolve such conflicts. We propose that these conflicts will be resolved via negotiations. The model considers situations characterized by complete, as well as incomplete, information. Using this negotiation mechanism, the servers have simple and stable negotiation strategies that result in efficient agreements without delays. We provide heuristics for finding the details of the strategies which depend on the specific settings of the environment and which can't be provided to the agents in advance, and demonstrate the quality of the heuristics, using simulations. We have proved that our methods yield better results than the static allocation policy currently used for data allocation for servers in distributed systems.

Sharing Resources Through Negotiation
We also applied the strategic model of negotiation to enable self-motivated, rational agents to share resources [20]. According to the utilitarian paradigm, an autonomous intelligent agent's interactions with the environment should be guided by the principle of expected utility maximization. We apply this paradigm and develop a rigorous formalization of the agent's utility function. Using our negotiation mechanism, autonomous agents have simple and stable negotiation strategies that result in efficient agreements without delays.

The algorithm is implemented in a multi-agent framework, MINUET, that provides the infrastructure required for communication and cooperation. Simulation results show that our mechanism performs as well as a centralized scheduler, is more flexible, and also has the property of balancing the use of resources.

Other cooperation mechanisms
Even though negotiation is beneficial in different settings, as was demonstrated above, there are situations where negotiation is not the best techniques for reaching cooperation. For example, in the information server environments described above, when a server is concerned about the data stored locally, but does not have preferences concerning the exact storage location of data stored in remote servers we propose to use a bidding mechanism [19]. Again, we considered situations of complete, as well as incomplete, information, and formally proved that our method is stable and yields honest bids. In the case of complete information, we also proved that the results obtained by the bidding approach are always better than the results obtained by the static allocation policy currently used for data allocation for servers in distributed systems. In the case of incomplete information, we demonstrated, using simulations, that the quality of the bidding mechanism is, on the average, better than that of the static policy.

Another important way for autonomous agents to execute tasks and to maximize payoffs is to share resources and cooperate on task execution by creating coalitions of agents [5,7,9,10,12,17]. The formation of coalitions for executing tasks is useful both in Multi-Agent Systems (MA) and Distributed Problem Solving (DPS) environments. However, in DPS, there is usually no need to motivate the individual agent to join a coalition. The agents can be built to try to maximize the overall performance of the system. In Multi-agent environments, an agent will join a coalition only if it gains more if it joins the coalition than it could gain previously, and, therefore, methods for the division of the coalition's joint utility are very important. This difference in coalition formation in DPS and MA environments required the development of two different models. In the first model [5,7,10,17] we apply game theory techniques for coalition formation in MA. In the second model [9,12], we apply Operations Research methods for team formation in DPS environments.

Computer assisted negotiation
The strategic model of negotiation also serves as the basis for a Decision Support System designed to enhance the ability of crisis negotiators to reach mutually beneficial outcomes [8,13]. A series of experiments have been conducted, designed to identify the crisis conditions and the types of decision makers most likely to benefit from such a DSS. In addition, a second research track has used the negotiation DSS to study the impact of cognitive complexity of decision makers on their behavior in crisis negotiation situations and on the outcome they attain [14,15]. In particular, we have been interested in the issue of whether wide disparities in the cognitive levels of crisis adversaries are likely to adversely affect their ability to achieve utility maximization.


PROJECT PUBLICATIONS
  1. S. Kraus. An Overview of Incentive Contracting. Artificial Intelligence journal, 83(2):297-346, 1996.

  2. B. Grosz and S. Kraus. Collaborative Plans for Complex Group Action. Artificial Intelligence journal, 86(2):269-357, 1996.

  3. S. Kraus. Beliefs, Time and Incomplete Information in Multiple Encounter Negotiations Among Autonomous Agents. Annals of Mathematics and Artificial Intelligence, (in press).

  4. S. Kraus. Negotiation and Cooperation in Multi-Agent Environments, Artificial Intelligence Journal, (accepted for publication).

  5. O. Shehory and S. Kraus. Coalition Formation among Autonomous Agents: Strategies and Complexity, in C. Castelfranchi and J.P. Muller, editors, From Reactions to Cognition, Lecture Notes in Artificial Intelligence, 957, Springer Verlag Publishers, 1995, pp. 57-72.

  6. S. Kraus and J. Wilkenfeld, Issues in the Development of Automated Negotiators in Multi-Agent Environments, in G. M. Olson, J.B. Smith and T.W. Malone, editors, Coordination Theory and Collaboration Technology, (to appear).

  7. O. Shehory and S. Kraus. A Kernel-oriented model for autonomous-agent coalition-formation in general environments, in C. Zhang and D. Lukose, editors, Distributed Artificial Intelligence --Architecture and Modeling, Springer-Verlag, 1996, pp. 31-45.

  8. J. Wilkenfeld, S. Kraus and K. Holley. The use of decision support systems in crisis negotiation, in A. Kent and J. G. Williams, editors, Encyclopedia of Microcomputers, Marcel Dekker, New York (to appear, 1998).

  9. O. Shehory and S. Kraus. Task Allocation via Coalition Formation Among Autonomous Agents, Proc. of IJCAI95, pp. 655--661, August, Montreal, Canada, 1995.

  10. O. Shehory and S. Kraus. A Kernel-Oriented Model for Coalition-Formation in General Environments: Implementation and Results Proc. of AAAI96, August, 1996, pp. 134-140.

  11. O. Shehory and S. Kraus. Emergent cooperative goal-satisfaction in large scale automated-agent systems, Proceedings of ECAI-96, August, 1996, pp. 544--548.

  12. O. Shehory and S. Kraus. Formation of overlapping coalitions for precedence-ordered task-execution among autonomous agents, Proc. of the Second International Conference on Multiagent Systems (ICMAS), 1996, pp. 330-337.

  13. J. Wilkenfeld, S. Kraus and K. Holley, The Negotiation Training Model, Proceedings of the International Simulation and Gaming Association Annual Meeting, 1995, Diputacion Provincial de Valencia, Spain.

  14. J. Wilkenfeld, S. Kraus, T. E. Santmire, K. Holley and T. E. Santmire. Cognitive Structure and Crisis Decision Making, 37th Annual Meeting of the International Studies Association, 1996, San Diego CA.

  15. J. Wilkenfeld, S. Kraus, T. E. Santmire, K. Holley and T. E. Santmire. Cognitive Complexity and Crisis Decision Making. (submitted)

  16. O. Shehory and S. Kraus. Emergent cooperative goal-satisfaction in large scale automated-agent systems. ( submitted)

  17. O. Shehory and S. Kraus. Feasible Formation of Stable Coalitions among Autonomous Agents in General Environments. (submitted)

  18. R. Schwartz and S. Kraus. Negotiation On Data Allocation in, Multi-Agent Environments. (submitted)

  19. R. Schwartz and S. Kraus. Bidding Mechanisms for Data Allocation in Multi-Agent Environments. (submitted).

  20. O. Schechter and S, Kraus. Sharing Resources Through Negotiation in Multi-Agent Environments. (submitted)

  21. O. Shehory and S. Kraus. Cooperative goal-satisfaction under uncertainty in discrete large-scale agent-systems. (submitted)


Return to ITO Workshop Abstracts Return to ITO Workshop Home Page