Department of Electrical Engineering and Computer Science

University of Michigan, Ann Arbor MI 48109

durfee@umich.edu

In many respects, negotiation can be viewed as a distributed search process: given a mutual concern (a resource to allocate, a design specification for an artifact, a plan to jointly carry out), agents search through the space of alternative ways of settling the concern. The details of what agents are mutually concerned about will vary from domain to domain, and the settlement processes that make sense depend on the concerns, on the agents, and on the environment in which the agents are operating. Still, we can identify general classes of such processes for settling concerns (see also Gasser's view of coordination frameworks as patterns of settled and unsettled problems [Gasser 1989] around which agents can organize their activities). The emphasis of this paper (and the workshop in which it appears) is the class of processes loosely called "negotiation." For the purposes of this paper, we will consider negotiation as the process by which one or more agents use what they know about each other to reach an acceptable settlement of their mutual concerns.

In many practical application domains, the space of alternative settlements can be extremely large. Hence, the negotiation process often must exploit structure in the space, or must employ heuristics, to avoid portions of the space where preferable settlements for all concerned are less likely. Moreover, the preceding assumes that the agents have settled on which concerns are in need of settlement! Identifying the right concerns to settle is itself a hard problem that can require negotiation.

In this abstract, I present a few perspectives on the negotiation process and how it can be made tractable. The emphasis is on a variety of approaches that my students, colleagues, and I have taken toward this end. The literature on negotiation in computational systems is large and diverse, and obviously much more can be said if one were to provide an exhaustive treatment. I do not present such a treatment. I do try to point out relationships to some of the other work in the area, but such pointers should be treated as illustrating examples rather than comprehensive comparisons.

One thread of work in negotiation in multiagent systems has been focused on agents with similar or identical preferences over system-wide goals, but whose limited local perspectives can lead them into performing ineffective or counterproductive activities relative to each other. This is the viewpoint typically taken in what has been traditionally known as Cooperative Distributed Problem Solving (CDPS), where the system of agents is viewed as trying to cooperatively solve problems that none of them can solve alone. In this kind of a setting, negotiation is needed to settle questions about what each agent should be doing to contribute best to the overall system goals. Because agents share common preferences about system performance, disagreements arise solely because of lack of knowledge: an agent might act in a manner that is counterproductive because it does not know something known to others that would have allowed it to act more productively. This is in contrast to, for example, disagreements that arise due to different preferences, which could require agents to actually change their preferences such as in Sycara's PERSUADER system [Sycara 1989].

In CDPS systems, therefore, negotiation is not so much a matter of "convincing" or "compromise" between agents as it is "informing." It therefore sounds like it should be easier to accomplish than in systems where agents have conflicting objectives, and in some respects it is, since once the "right" information is exchanged, reaching agreement is trivial. However, the challenge generally lies in the identification of the "right" knowledge. In systems that concentrate on conflict resolution and allocating scarce resources through mechanisms such as contracting (e.g., [Sandholm, 1998]), constraint-based search (e.g., [Conry et al, 1991], Sycara et al, 1991]), and markets (e.g., [Walsh and Wellman, 1998]), the concerns (resources and tasks) at the heart of the negotiations are established as part of the mechanisms. In contrast, in a CDPS of the kind we are talking about, it is usually the case that once a concern requiring agreement is identified, reaching agreement is easy; the hard part is that the participating agents might know too little of what each other are doing (what resources they need or where they will be applying the resources they have) to even be aware that there are disagreements that need to be settled! In this context, negotiation involves a sufficient exchange of information for agents to identify and settle such disagreements.

One strategy for arriving at such states of sufficiently global knowledge is to allow agents to share the broad outlines of their plans and goals, such that they can over time align these. This was the strategy our work took in developing Partial Global Planning (PGP) [Durfee and Lesser, 1991; Durfee, 1988]. In PGP, an agent represents its intended activities at an abstract level of detail, and passes the representation to other agents as dictated by the coordination relationships among agents (captured in the meta-level organization). As agents become aware of the plans of others, they synthesize the pieces into a more global view of the collective activities. Because we assume that the agents have homogeneous preferences (and that agents can assume this about others), each agent can identify revisions to the more collective activities that will improve the expected group benefit. Each will map the applicable revisions into its own plans, and act in the expectation that others will do the same. Despite asynchronous knowledge exchange and dynamic plan revisions, over time the agents react to each other's changes to work together well.

PGP implicitly takes a BDI (Belief-Desire-Intention) perspective on agents and negotiation. That is, it assumes that the role of negotiation is to align the intended actions of the agents, and that these intentions can be changed by changing the belief states of the agents. Returning back to the definition for negotiation framed in this paper, we can see that in PGP each agent can settle the concerns if it knows enough about other agents (specifically, about what they know). Thus, whereas in some classes of problems the emphasis on negotiation is on communicating about proposed (pieces of) settlements, in PGP the emphasis in the negotiation process is on communicating about agents' beliefs, from which settlements will fall. From the perspective of negotiation technologies, this amounts to techniques for propagating sufficiently rich models of other agents to enable reasoning about them. PGP suggested a number of strategies that agents can use to decide when to exchange plan information and, sometimes more importantly, when to refrain from doing so to prevent a chain reaction of minor plan revisions [Durfee and Lesser, 1988].

If agents do not share common preferences over group performance, then the negotiation problem involves making tradeoffs among different preferences. One form that these tradeoffs can take is in the rewards or payoffs to each individual participant. In this sense, it is in an agent's own self interest to select a course of action that, if it were in other circumstances, would be inferior, if the course of action has the highest expected reward given the likely decisions by other agents. Making such a determination, however, requires anticipating the likely decisions of others. And their decisions might, in turn, be based on models of others as well. Our work on the Recursive Modeling Method (RMM) has focused on the representation and solution of such nested agent models [Gmytrasiewicz and Durfee, 1995]. Again, from the perspective of negotiation technology the emphasis is not so much in the "give-and-take" among agents, but rather in how agents can use local knowledge to jump to likely good choices of activities. In the extreme, such as when competitive agents engage in no communication whatsoever, this amounts to each agent conducting the negotiation within its own head, using models of others to anticipate how they will counter particular choices. For example, in time constrained negotiation, it is possible that an agent can reason about another sufficiently anticipate a settlement that the other agent will be forced to take because of the costs of further negotiation [Kraus and Wilkenfeld, 1991]. When more cooperative solutions are possible, agents can engage in communication to enumerate other options or change expectations in their joint activity space [Gmytrasiewicz and Durfee, 1993].

If agents must agree on a collective settlement over their various concerns, and yet each faces different needs and preferences that are unknown to others, then negotiation can involve the iterative exchange of proposed settlements to some concerns, hopefully leading to a combination of settlements that satisfies everyone. This is the strategy taken in solving Distributed Constraint Satisfaction Problems (DCSPs) [Conry et al, 1991, Yokoo et al, 1992]. A well-defined protocol for DCSP will allow agents to explore the entire space of settlements (if necessary) in a systematic fashion. To the extent that the systematic exploration supports preferential search sooner in areas of the space that are more likely to lead to mutually satisfactory solutions, so much the better [Armstrong and Durfee, 1997].

When agents have an overarching desire to satisfy collective constraints, and yet each might have preferences over exactly how those constraints are satisfied, then the problem begins to take on the characteristics of an optimization problem where agents wish to minimally relax their constraints [Yokoo, 1993]. For example, in the application domain of distributed meeting scheduling, we often assume that each participant wants the meeting to be scheduled, but each might have idiosyncratic preferences over which of the potential meeting times/locations would be preferred. In such situations, the protocol that agents use will influence the order in which possible solutions are explored, giving potential power to some agents relative others. Moreover, stalemate is possible if agents fail to entertain options that are less than the best for them. Strategies are needed to allow agents to relax the strengths of their preferences. Moreover, the willingness of agents to be more flexible in the choices they make about what options they entertain, will strongly influence the costs of arriving at a compromise at all [Sen and Durfee, 1996]. Finally, sometimes identifying the objectives for collective optimization and how alternative assignments made by (or to) agents affect these objectives and the costs for attaining them can itself be a complex task [Clement and Durfee, 1998].

As has been mentioned before, it can sometimes be advantageous (or necessary) for an agent to anticipate internally the course of a negotiation, rather than to incur the costs, inefficiencies, or ambiguities of explicitly passing information back and forth. In fact, when competing agents are communicating, there might be times when agents fail to negotiate "in good faith" by misrepresenting their preferences or the worth of particular solutions, such that additional mechanisms are needed to ensure that rational agents will truthfully represent themselves [Rosenschein and Zlotkin, 1994]. Thus, when an agent cannot retract a proposal once it has made it, it should "look" carefully before it "leaps."

A way of introducing such strategic reasoning into an agent's negotiation framework is to have the agent internally model the negotiation process. For example, if the negotiation is over the price for a particular good or service, an agent can model the pricing mechanism to envision how prices might fluctuate in the near future. The mechanism could be an auction, for instance. A strategic agent could consider how different proposals (bids) that it might make might fare in the auction, based on what it knows about the current state of the auction (the standing offers currently there) and how that state evolves (what other offers are likely to arrive and when). Our work has used Markov models to capture the evolution of such auctions [Park and Durfee, 1996; 1998]. By anticipating the future behavior of the auction, an agent can sometimes wait for more propitious moments to make its bids, and can extract more personal benefit out of the negotiation process embodied in the auction. It is also possible, however, than an agent with a poor model of the situation, who does not realize that its model is poor, can drag down the whole system [Hu and Wellman, 1996].

If an agent lacks good models for envisioning the future course of events of a negotiation, it could employ the alternative strategy of projecting from prior experience into the future. By learning correlations between agents prior negotiating stances (proposals) and ultimate decisions (settlements reached), an agent can adapt its own negotiation techniques to learn when to accept the proposals of others, when to counterpropose, and when to opt out of the negotiation all together [Matos et al, 1998; Vidal and Durfee, 1998]. Of course, part of what it learns could be models of others, and of their models of others, and so on. Thus, part of what agents learn could be the grist for other kinds of strategic reasoning.

Finally, most of the above assumed that agents know ahead of time what the concerns that need to be settled through negotiation are in the first place: that their plans/actions need to be coordinated, that their bindings of times and locations to meetings must be consistent, that they must arrive on prices for exchanging goods and services, and so on. This assumption can be problematic for a number of reasons. One reason is that decisions about how to represent the relevant concerns can have a huge impact on the costs and outcomes of negotiations. For example, negotiating over the root causes of numerous disagreements can sometimes be more cost-effective than negotiating over each of the individual disagreements separately. A second reason is that, in open multiagent environments, the space of concerns will continuously evolve, so designing ahead of time the concerns to be negotiated over is ultimately going to fail.

Our work has explored two classes of techniques for deciding what to negotiate over. One class is based on search, and the other on learning. The search-oriented techniques assume that the space of concerns is structured and traversable. Thus, agents that need to negotiate first need to search the space of concerns to find the particular part of the space that suits their needs. In most of our work, we have focused on negotiating over potentially conflicting plans. As was mentioned earlier, PGP assumed that agents would exchange abstract plans to identify and resolve potential conflicts. But no matter what level of abstraction is designed into PGP for this exchange, problems can arise. If for the particular current needs the abstraction is too abstract, then the negotiation is over broad plans leading to broad resolutions of conflicts, and these are usually quite inefficient. On the other hand, if the abstraction is not abstract enough, then the negotiation gets tangled resolving individual plan details that could be better dealt with simply by viewing them as manifestations of an underlying, broader conflict.

Our early work in exploring the space of abstractions focused primarily on representing movement plans in hierarchies of increasing/decreasing sized groupings of time and space [Durfee and Montgomery, 1991]. When negotiating to identify and resolve potential conflicts with each other, agents could begin with their most abstract representations and compare these to determine whether conflicts were possibly lurking in the details. If not, the (degenerate) "negotiation" was done, but if so then agents could either resolve the potential conflict at the abstract level (sequentialize their plans or allocate different resources to prevent conflicts) or exchange information at the next level of detail. This process could repeat until either the conflicts were eventually resolved or it was discovered, upon looking deeply enough, that there really were no conflicts. Our more recent, ongoing work in this area has been generalizing these techniques to handle more generic hierarchical plan representations (not just involving time and space) and alternative means of resolving potential conflicts.

The second class of techniques for deciding what to negotiate over involves learning and adaptation on the part of the multiagent system. That is, while the search-oriented approach assumes that agents have sufficient knowledge and context to be able to find the concerns to negotiate over before they begin interacting, a learning-based approach instead accepts the fact that agents might engage in suboptimal negotiations for a time, but they over time learn to do better. To the extent that agents can even institutionalize what they learn in the multiagent structure, the multiagent system as a whole adapts to the agents' collective benefit.

Our work has explored this area in two types of multiagent structures. One is a physical structure, where adapting the structure means moving agents around (or, more precisely, having agents move themselves around). We have explored how various impediments and inducements to movement, as well as different environmental conditions, can lead to the emergence of cooperative structures [Armstrong and Durfee, 1998]. Conceptually, physical clusters in a mobile-agent world can correspond to virtual clusters in a networked world. In our digital library work, we have explored how agents can use what they have learned during prior interactions to suggest different clusterings of agents into auctions. That is, for efficient allocation through competition among price takers, an auction should attempt to have as many participants as possible. Yet, sometimes an overlarge auction is bringing together agents who might provide or prefer to consume somewhat different goods or services. Our work has begun to investigate how agents can learn from the deals struck in an auction which deals they like and which they dislike [Durfee et al, 1999]. From these experiences, they can break an overly large auction into subauctions such that they are more likely to be satisfied with interactions in a particular subauction. Thus, the concerns being settled in the auctions are themselves open for revision, leading to the evolution of auctions that support negotiation over the goods and services that matter most to the agents, rather than those initially foreseen by a human designer.

This paper has described a few data points in the large space of negotiation processes. Clearly, there are many unanswered questions and open problems in our understanding of how negotiation can be done and how to realize the possibilities into computational technologies. This paper hinted at a few of what I see as some of the exciting challenges lying ahead. I will conclude by recapitulating two of those themes.

One theme revolves around the problem of defining what is being negotiated over. A number of very exciting and advanced techniques have been developed over the years that allow agents to express preferences for how various concerns are settled such that individually and globally rational decisions can be made. For the most part, however, these presuppose that the agents already know what they are "arguing" about, and what remains to be done is to settle the "argument." It is my contention that, in many domains, a substantial part of the negotiation effort is involved in figuring out what needs to be settled. As our computational agents are increasingly applied in dynamically evolving worlds (like on the internet), capabilities for identifying who needs to negotiate and over what, rather than having these predefined by system developers or users, will come to the fore.

The second theme I would like to briefly revisit is that of building models of agents. While certainly in many applications it could be reasonable to view each agent as myopically expressing what it wants given the environment, and allowing agents to converge on global solutions through the iterative exchange of such expressions, it also appears likely that much more efficient and effective negotiation for some domains will require agents to model enough about each other "in their heads" so as to internally simulate some of the negotiation. This avoid excessive numbers of explicit iterations, allowing agents to more quickly "cut to the chase." I see exciting challenges ahead in developing computational systems that communicate about themselves or learn about each other with the specific goal of internalizing some negotiation steps. So far, I think our community has some suggestive examples of how this might be done, but careful, well-founded characterizations remain to be found.

In conclusion, if I return to my strawman definition: negotiation is a process by which one or more agents use what they know about each other to reach an acceptable settlement of their mutual concerns, my claim is that a full-fledged understanding of negotiation has to continue to improve upon the procedural aspects of reaching settlements, but also has to encompass other aspects of the definition, especially identifying mutual concerns and establishing sufficient knowledge about other agents. These tasks are both challenging and crucial for truly exploiting negotiation technologies in the digital age.

[Armstrong and Durfee, 1997] Aaron Armstrong and Edmund H. Durfee. "Dynamic Prioritization of Complex Agents in Distributed Constraint Satisfaction Problems." In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI97), pages 620-625, August 1997.

[Armstrong and Durfee, 1998] Aaron Armstrong and Edmund H. Durfee. "Mixing and Memory: Emergent Cooperation in an Information Marketplace." In Proceedings of the Third International Conference on Multi-Agent Systems (ICMAS98), pages 34-41, July 1998.

[Clement and Durfee, 1998] Bradley Clement and Edmund H. Durfee. "Scheduling High-Level Tasks Among Cooperative Agents." In Proceedings of the Third International Conference on Multi-Agent Systems (ICMAS98), pages 96-103, July 1998.

[Conry et al, 1991] Susan E. Conry, Kazuhiro Kuwabara, Victor R. Lesser, and Robert A. Meyer. Multistage negotiation for distributed constraint satisfaction. IEEE Trans. of Systems, Man, and Cybernetics SMC-21(6):1462-1477, Nov. 1991.

[Durfee, 1988] Edmund H. Durfee. Coordination of Distributed Problem Solvers, Kluwer Academic Press, Boston 1988.

[Durfee et al, 1999] Edmund H. Durfee, Tracy Mullen, Sunju Park, José M. Vidal, and Peter Weinstein. "Strategic Reasoning and Adaptation in an Information Economy." Intelligent Information Agents (M. Klusch, editor). Springer-Verlag, 1999 (to appear).

[Durfee and Lesser, 1988] Edmund H. Durfee and Victor R. Lesser. "Predictability Versus Responsiveness: Coordinating Problem Solvers in Dynamic Domains." In Proceedings of the Seventh National Conference on Artificial Intelligence , pages 66--71, August 1988.

[Durfee and Lesser, 1991] Edmund H. Durfee and Victor R. Lesser. "Partial Global Planning: A Coordination Framework for Distributed Hypothesis Formation." IEEE Transactions on Systems, Man, and Cybernetics, Special Issue on Distributed Sensor Networks, SMC-21(5):1167-1183, September 1991.

[Durfee and Montgomery, 1991] Edmund H. Durfee and Thomas A. Montgomery. "Coordination as Distributed Search in a Hierarchical Behavior Space." IEEE Transactions on Systems, Man, and Cybernetics, Special Issue on Distributed Artificial Intelligence, SMC-21(6):1363-1378, November 1991.

[Gasser 1989] Les Gasser, Nicholas F. Rouquette, Randall W. Hill, and John Lieb. "Representing and Using Organizational Knowledge in Distributed AI Systems." In Distributed Artificial Intelligence, Volume 2 (Gasser and Huhns, editors), pages 55-78, Morgan Kaufmann, 1989.

[Gmytrasiewicz and Durfee, 1993] Piotr J. Gmytrasiewicz and Edmund H. Durfee. "Toward a Theory of Honesty and Trust Among Communicating Autonomous Agents." Group Decision and Negotiation 2:237-258 (Special issue on Distributed Artificial Intelligence), 1993.

[Gmytrasiewicz and Durfee, 1995] Piotr J. Gmytrasiewicz and Edmund H. Durfee. "A Rigorous, Operational Formalization of Recursive Modeling." In Proceedings of the First International Conference on Multi-Agent Systems (ICMAS), pages 125-132, June 1995.

[Hu and Wellman, 1996] Junling Hu and Michael P. Wellman. "Self-fulfilling bias in multiagent learning. In Proceedings of the Second International Conference on Multi-Agent Systems (ICMAS96), pages 118-125, December 1996.

[Kraus and Wilkenfeld, 1991] Sarit Kraus and Jonathan Wilkenfeld. "Negotiations over time in a

[Matos et al, 1998] Noyda Matos, Carles Sierra, and Nick R. Jennings. "Determining successful negotiation strategies: An evolutionary approach." In Proceedings of the Third International Conference on Multi-Agent Systems (ICMAS98), pages 182-189, July 1998.

Park et al, 1996] Sunju Park, Edmund H. Durfee, and William P. Birmingham. "Advantages of Strategic Thinking in Multiagent Contracts (A Mechanism and Analysis)." In Proceedings of the Second International Conference on Multi-Agent Systems (ICMAS96), pages 259-266, December 1996.

[Park et al, 1998] Sunju Park, Edmund H. Durfee, and William P. Birmingham. "Emergent Properties of a Market-Based Digital Library with Strategic Agents." In Proceedings of the Third International Conference on Multi-Agent Systems (ICMAS98), pages 230-237, July 1998.

[Sandholm, 1998] Tuomas W. Sandholm. "Contract types for satisficing task allocation: Theoretical Results." AAAI Spring Symposium of Satisficing Models, pages 68-75, Stanford, March 1998.

[Sen and Durfee, 1996] Sandip Sen and Edmund H. Durfee. "A Contracting Model for Flexible Distributed Scheduling." Annals of Operations Research (Special issue on integration of AI and OR and decision analysis), volume 65 pages 195-222, 1996.

[Sycara, 1989] Katia Sycara. "Multiagent Compromise via Negotiation." In Distributed Artificial Intelligence, Volume 2 (Gasser and Huhns, editors), pages 119-137, Morgan Kaufmann, 1989.

[Sycara 1991] Katia Sycara, Steven Roth, Norman Sadeh, and Mark Fox. Distributed constrained heuristic search. IEEE Transactions on Systems, Man, and Cybernetics SMC-21(6):1446-1461.

[Vidal and Durfee, 1998] José M. Vidal and Edmund H. Durfee. "Learning Nested Agent Models in an Information Economy." Journal of Experimental and Theoretical Artificial Intelligence (special issue on learning in distributed artificial intelligence systems). To appear 1998.

[Walsh and Wellman, 1998] William E. Walsh and Michael P. Wellman. "A Market Protocol for Decentralized Task Allocation." Third International Conference on Multi-Agent Systems (ICMAS'98), pages 325-332, July 1998.

[Yokoo et al, 1992] Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara. "Distributed Constraint Satisfaction for Formalizing Distributed Problem Solving." In Proceedings of the Twelfth International Conference on Distributed Computing Systems, pages 614-621, June 1992.

[Yokoo, 1993] Makoto Yokoo. "Constraint relaxation in distributed constraint satisfaction problem." Fifth International Conference on Tools with Artificial Intelligence, pages 56-63, 1993.