For efficient and informative coordination of agents especially in electronic commerce environment, a time-bound agent negotiation framework is proposed utilizing a time-based commitment scheme. By attaching commitment duration to agent messages, the traditional contract net protocol is extended to a time-bound negotiation framework (TBNF). The proposed negotiation framework has a new message type which allows for parties to agree upon the extension of a commitment duration, and a novel commitment concept in the form of negative commitment. The semantics of the messages with the commitment duration are interpreted, and then the three typical negotiation protocols are formally defined and compared — nothing-guaranteed protocol, acceptance-guaranteed protocol, and finite-time guarantee protocol — which can be incorporated into TBNF. The TBNF should provide a background for efficient and effective electronic commerce negotiation while accommodating each agent's adaptive negotiation strategy
As electronic commerce becomes more popular, the role of automated negotiation systems is expected to increase. For example, when a virtual shopping mall receives product orders from a customer, it is necessary to make the delivery orders automatically without human intervention, generate a request for proposal (RFP) and announce it to multiple delivery companies (as shown in Fig. 1).Then, the mall and delivery companies will negotiate over the price and quality (e.g., delivery date) of a specific delivery service. In this case, each agent is self-interested, the contractor agent (i.e., delivery company) is resource-constrained, and the status of agents constantly changes.
In such an electronic commerce environment, the efficient coordination of multi-agents is very important for the performance of each agent and the whole system. Contract Net Protocol [14] has been the most commonly used method for coordinating agents in negotiation. Contract Net Protocol specifies communication and controls in a distributed problem solver [3]. This communication protocol concerns how contract managers announce the tasks to other agents, how potential contractors return bids to the manager, and how the manager then awards the contract (a manager is responsible for monitoring the execution of a task and processing the results of its execution, and a contractor is responsible for the actual execution of the tasks). The basic steps of the protocol are listed below and shown in Fig. 2.
- A manager issues a task announcement describing the task and the criteria for bids.
- Contractors send bids announcing their willingness and ability to perform a task.
- The manager sends the award message to a successful contractor.
- The contractor sends an acknowledgement of the award back to the manager, either accepting or rejecting it.The original Contract Net Protocol can be somewhat simple for a specific purpose. However, it needs to be modified to satisfy various system requirements for improving performance. Therefore, there has been research conducted on the extension of the protocol by:
- Introducing new speech acts such as temporal grant, temporal reject, definitive grant, and definitive reject when tasks exceed the capacity of a single agent. The context involves an extended Contract Net Protocol [5].
- Introducing fuzzy theoretic techniques for determining next task announcement and the best bid [17].
- Using directed contracts and forgetting by case-based reasoning to reduce communication loads [15].
- Enabling agents to choose levels of commitments dynamically for iterative task allocation negotiations [10].
In this paper, we propose a negotiation framework emphasizing the commitment duration attached to every message (commitment is an agreement or pledge to do something in the future [7] and [12]). The time-bound framework provides a good background for choosing a proper negotiation protocol especially for a dynamic situation where desired tasks and available resources may be changing as the system is executing tasks. The following is a scenario for a delivery problem in a virtual shopping mall, which inspires this research.
1.1. A Delivery Problem in a Virtual Shopping Mall
1.A shopping mall agent (SMA1) asks a delivery company agent (DCA) if a product PA can be delivered to its buyer from a warehouse in 3 days.
2.DCA schedules its own facility (e.g., trucks) for the delivery of the product PA and replies ‘Yes’ to SMA1.
3.However, SMA1 has not yet awarded the bid to DCA.
4.In the meantime, another shopping mall agent, SMA2 asks the (DCA) whether DCA can deliver a product PB to its buyer from a warehouse in 3 days.
5.DCA tries to schedule its own facility for the delivery of PB and then learns that the product PB can not be delivered to the buyer for SMA2 on time without canceling the capacity reservation for SMA1.
In this case, what should DCA do? Three alternative protocols can be used to cope with these problems: (1) Nothing-guaranteed protocol, (NGP) (2) Acceptance-guaranteed protocol, (AGP) and (3) Finite-time guarantee protocol (FGP). The next section briefly explains each of them.
We expect that TBNF will be well suited for choosing a good protocol for the situation where self-interested and resource-constrained agents negotiate in a dynamic situation such as in a full-scale supply chain management for virtual shopping malls. Fig. 6 shows message flows in the context where the messages are exchanged among shopping mall agents, supplier agents, and delivery company agents etc. In summary, the merits of TBNF are.
1.TBNF provides a more informative framework with richer semantics.
2.TBNF provides the framework for promoting and expediting the negotiation process by allowing agents more strategic alternatives.
3.TBNF provides the background for finding an appropriate architecture and protocol for a specific domain and situation.
4.TBNF provides the background for efficient and effective multi-agent coordination while accommodating each agent's adaptive negotiation strategy.Future research topics related to TBNF include research on the desirable architecture of agents under a specified framework, the optimal commitment scheme for competition, and how agents cooperate. In addition, research should be conducted on a time-stamping mechanism for all agents to verify and agree on the sending or receiving time of a message, which is regarded as one of the functions of certificate authorities for electronic commerce.
