Claudio Bartolini1, Chris Preist1, Harumi Kuno2
Hewlett-Packard Labs
(1) Filton Road, Stoke Gifford, Bristol, BS34 8QZ, UK
(2) 1501 Page Mill Road, Palo Alto, CA 94304, USA
Email: [email protected], [email protected], [email protected]
The increasing importance of business to business electronic trading has driven interest in automated negotiation to soaring heights. In recent times, web-service enabled electronic marketplaces have been displacing proprietary trading solutions. Looking at this trend, we foresee a need for a general software infrastructure that enables independent entities to interact using multiple forms of negotiation. This infrastructure would cover a variety of aspects, including defining a general protocol for negotiation (including the definition of the actors, roles and phases of negotiation); defining a taxonomy and a language for negotiation rules to cast the general protocol into one that embodies the desired market mechanism; defining a language to express negotiation proposals.
Negotiation has been for decades a central subject of study in disciplines such as economy, game theory, and management. When discussing negotiation, it is important to distinguish between negotiation protocol and negotiation strategy. The protocol determines the flow of messages between the negotiating parties, dictating who can say what, when and acts as the rules by which the negotiating parties must abide by if they are to interact. The protocol is necessarily public and open. The strategy, on the other hand, is the way in which a given party acts within those rules in an effort to get the best outcome of the negotiation for example, when and what to concede, and when to hold firm. The strategy of each participant is therefore necessarily private. In this document we concentrate on the requirements for architecting software enabling automated negotiation, therefore we discuss protocols and not strategy.
Existing approaches to architecting software enabling automated negotiation provide either ad-hoc software for particular market mechanisms or proprietary solutions. We take an open approach by defining a standard protocol for interaction among the participants in the negotiation process. Our protocol is defined independently from the negotiation rules embodying the particular market mechanism that the negotiation host wants to impose. Instances of negotiation rules will be used to cast the general protocol into a specific one that embodies the desired market mechanism. This approach is general with respect to a wide variety of market mechanisms, from one-to-one negotiation to auctions and double auctions.
Our position is that we need to design a standardized infrastructure that allows two or more independent entities to interact with each other over time to reach agreement on the parameters of a contract. This infrastructure is aimed primarily, though not exclusively, as a means to reach trade agreements. It can be used both by automated entities and by users via appropriate software tools.
The value of such a framework to negotiation participants is threefold. First, the framework frees participants from having to develop their own negotiation infrastructure, providing prerequisite services such as the provision of decision support and support for the automation of the negotiation process. Second, the infrastructure enforces the standardization of basic interaction rules, allowing participants to be confident that basic rules of interaction in any negotiation will be followed. For example, participants will able to negotiate simple contracts, where only price is undetermined, as well as more complex contracts involving multiple complex and interdependent parameters. Third, the protocols provide the participants with trust guarantees, ensuring that no party has access to extra information or is able to forge false information.
The value to negotiation hosts, such as auction houses and market makers, is that by providing a standard framework that is independent of any specific market mechanism, they will increase the number of potential customers who can interact with them. The infrastructure would allow the hosts to select an appropriate market mechanism. It would provide standard off-the-shelf market mechanisms (e.g. English auction), and also allow custom mechanisms to be implemented for particular special needs (e.g. the FCC auction).
We identify the following requirements for a negotiation protocol that would meet our goals:
1. Be sufficiently formal that automated entities can interact using it.
2. Support negotiation about simple and complex objects.
3. Be sufficiently general that a variety of different market mechanisms (e.g. 1-1 negotiation, combinatorial auctions, exchanges) can be expressed as specific instances of it.
4. Support security mechanisms and protocols that enable participants to do business in a trusted way.
5. Allow, but not require, the existence of a third party to arbitrate a given negotiation (e.g. an auctioneer in an auction.)
6. Support existing ways of doing business, as well as permitting more radical approaches in the future.
A negotiation protocol provides a means of standardizing the communication between participants in the negotiation process by defining how the actors can interact with each other. We therefore base the definition of our protocol on conversation orchestration protocols such as CDL [1] or WSDL [2].
We propose that the protocol should be general enough to support a wide variety of market mechanisms. Therefore the protocol should be based on the common aspects of the various market mechanisms that it wants to support. That is, define the negotiation process as an exchange of negotiation proposals followed by a phase of agreement formation. The two phases will often be intertwined for some market mechanisms.
Designing the protocol requires the definition of:
As noted above, the protocol is defined independently from the negotiation rules embodying the particular market mechanism supported by the negotiation host. The rules for negotiation will then cast the general protocol into one that can be used to embody a particular market mechanism.
Examples of types of rules for negotiation would be rules for deciding on the well-formedness of a negotiation proposal. Another example is rules regulating the alternation of participants in submitting proposals. Again, there will be rules the dictating the visibility aspect of proposals in many-to-many negotiation, i.e. who among the participants is entitled to see a submitted negotiation proposal, and so on. Rules will be needed for supporting mechanisms such as zero knowledge proofs to avoid revealing private information in the course of negotiation.
The language to define the rules of negotiation should be standardized. The idea is to have a declarative language for expressing rules in a way that participants to negotiation can reason about them. The declarative layer would then be mapped to reusable software components implementing the logic expressed by the rules. These components would be plugged in the orchestration infrastructure for the protocol to be cast to embody a desired market mechanism.
The format to express negotiation proposals has to be standardized. The requirements to be satisfied by a candidate language would be:
RDF [3] and DAML-OIL [4] are promising candidate languages
[1] Govindarajan K., et al. Conversation Definitions: A way of defining interfaces for web services – submitted to W3C Workshop on Web services, 11-12 April 2001, San Jose, CA
[2] http://msdn.microsoft.com/xml/general/wsdl.asp
[3] http://www.w3.org/RDF
[4] http://www.daml.org/2000/12/daml+oil-index.html