A Replicable Web-Based Negotiation Server for E-Commerce

A Replicable Web-Based Negotiation Server for E-Commerce

Stanley Y. W. Su, Chunbo Huang and Joachim Hammer

Database Systems R&D Center

University of Florida, Gainesville, FL 32611-6125

{su, chuang, jhammer}@cise.ufl.edu

Abstract

This paper describes our ongoing R&D effort in developing a replicable, Web-based negotiation server to conduct bargaining-type negotiations between clients (i.e., buyers and sellers) in e-commerce. Multiple copies of this server can be installed as plug-ins to existing Web-servers and clients can select a negotiation server that best represents their interests. Clients use a content specification language based on an extended object model to specify the requirements, constraints, and negotiation strategic rules, which are used by the negotiation server to conduct a negotiation. We present our architecture and a framework for negotiation and describe a number of communication primitives, which make up the negotiation protocol. We use our existing Event-Trigger-Rule (ETR) system to perform event management, constraint checking, and strategic rule processing. A cost-benefit analysis component performs quantitative analysis of alternative negotiation conditions.

1Introduction

In recent years, we have witnessed the dramatic increase in the number of companies doing business on the Internet. Electronic commerce (e-commerce) has been adopted by companies of all sizes ranging from multinational corporations to small mom-and-pop operations. It has been predicted that, by the year 2000, nearly 80 percent of all Fortune 500 companies will be doing their core business through the Internet. Today, there are more than 30 million Internet users and the number is projected to grow to 90 million in the near future. Since these users are potential consumers, there are many incentives for companies of all sizes to publish information about their goods and services on the Internet. Any company can become a global publisher by establishing an information site on the Internet’s World Wide Web (Web). The Web provides customers and businesses with ubiquitous interactive access to text, sound, images, and even video data published on each site. In the e-commerce paradigm, companies can receive purchase orders from individual consumers or business partners, deliver goods and services, and accept payments, all in an electronic fashion.

In ordinary, non-electronic business transactions, individual consumers and companies often want to negotiate the price, the delivery date, the quality of goods and services, as well as other purchase conditions; particularly if the order is large. Traditionally, negotiations are conducted by people involved in business transactions. In both consumer-to-business and business-to-business e-commerce, it is desirable to carry out this negotiation process either automatically or at least semi-automatically with human interventions only when necessary. Given the recent interest in e-commerce, a considerable amount of research work on automated negotiation systems is already available. Muller [MUL96] provides a thorough description on the principle of negotiation based on the investigations of the distributed artificial intelligence group. Beam and Segev [BEA97] also give an insightful overview of the existing research efforts on this topic.

There are several forms of negotiations: bidding, auction, and bargaining. Bidding is the simplest form of negotiation, in which a buyer specifies the product or service he[1] wants to acquire from suppliers and asks for their bids. Based on the bids, the buyer selects the supplier(s) from whom to order. The Contract Net Protocol (CNP) of Davis and Smith [DAV80] is a good example of bidding.

Auction is another form of negotiation, in which a fixed auction protocol is followed. There are several negotiation Web sites, which use auction protocols. Yahoo’s auction service, Cathay Pacific’s sealed-bid auction to sell airline tickets, and Onsale’s high tech goods auction [BEA97] are some examples. [KUM98] explores a variation of auction and [BEA96] discusses optimization issues. [LEE97] incorporates several typical auction protocols as a part of an intelligent EC framework with negotiation capabilities.

Bargaining is the most complex form of negotiation, which involves issuing proposal and counterproposal between negotiating parties until a mutual agreement or disagreement is reached. Researchers in distributed artificial intelligence have used negotiation for conflict resolution and coordination among multiple agents [MUL96]. For example, [SAN95] discusses a so-called self-interest agent to design an optimized evaluation/decision function and suggests several elements that should be considered in negotiation: commitment level, local deliberation, and linking negotiation items. Using ideas borrowed from game theory, [ZLO96] treats negotiation as a type of interaction among distributed computer systems. In order to make the overall system more efficient, interaction rules (called negotiation mechanisms) are followed by each component system. [SIE97] addresses the searching property of negotiation and discusses issues related to negotiation strategy, tactics, and search convergence. [KOI98] uses a service constraint satisfaction technique and a worth-based evaluation function to determine the final deal in a quality-of-service negotiation. [OLI97] shows that any pre-programmed negotiation strategy will not be effective in real negotiation cases and shows that a system of artificial adaptive agents using a genetic algorithm, can learn strategies that enable the system to effectively participate in business negotiations. However, [BEA97] points out that genetic programming requires too many trials to obtain good negotiation strategies.

Our work here focuses on bi-lateral and multi-lateral bargaining, which are very challenging problems in negotiation. It is founded on the concepts and issues addressed in the work mentioned above. However, we take an object-oriented database approach instead of the agent approach. Implementation work is in progress to build a Web-based negotiation server, which can be replicated and installed as plug-ins to existing Web servers. Buyers and sellers (henceforth referred to as clients) can select a trusted negotiation server to conduct negotiations on their behalf, the same way as lawyers are asked to represent their clients in legal matters. Similar to Web servers, which provide many useful Web services, negotiation servers provide negotiation services to their clients. Each negotiation server provides the following four negotiation services:

• A registration service to allow a buyer to specify the requirements and constraints of the goods or services he wants to acquire and a seller to specify the information and constraints related to the goods and services he provides. Additionally, a client can also register a set of negotiation rules, which specify the negotiation strategies to be followed when constraints are violated during the negotiation phase. A content specification language is used for the registration purpose. It is based on the extended object model (EOM), which represents objects in terms of attributes, operations (methods), events, rules, and triggers. The rule specification part of the language is an extension of the Event-Condition-Action (ECA) rule paradigm. The registered information is stored in a persistent store.
• A negotiation proposal processing service to evaluate proposals and generate counter-proposals, explanations, messages, etc. by following a negotiation protocol until an agreement is reached or not.
• An event and rule management service to detect and manage events and to trigger proper rules when events occurred (based our existing Event-Trigger-Rule (ETR) server [LS98]).
• A cost-benefit analysis service to allow a client to perform quantitative analysis on alternative negotiation proposals and obtain their relative, quantitative cost-benefit measures. For this service, we have adopted the cost-benefit decision model presented in [SU87].

The paper is organized as follows. Our architecture for Web-based negotiation servers and a framework for conducting automated negotiation are described in Sec. 2. Our content specification language and registration examples are given in Sec. 3. Sec. 4 explains the negotiation process and our protocol in more detail. Sec. 5 briefly outlines our cost-benefit decision model. A conclusion and discussion is given in Sec. 6.

2Negotiation Server Architecture

Figure 1 shows the relationships between negotiation servers, Web servers, client computers, and humans in the negotiation process. In addition, some of the clients may have application systems to maintain the inventories of goods or information about the services that they provide. To simplify our presentation of the negotiation process, we shall use the symbols EA, UA, and NSA to denote the expert, user, and negotiation server of the negotiation party A, respectively. The corresponding symbols EB, UB, and NSB are used to denote those of negotiation party B.

In the proposed framework of Web-based negotiation, sellers can publish information about the goods and services they provide on their home pages, which can be browsed by the potential buyers using Web browsers and search engines. Through searching and browsing, or other available trader services, a buyer can identify potential sellers with whom he wants to negotiate. In order for buyers and sellers to make use of the automated negotiation service, each must register with a negotiation server of their choice and provide the information that is necessary to conduct the negotiation (see below).

A client (i.e., UA in Figure 1) initiates the negotiation process by submitting an initial negotiation proposal to his selected negotiation server. The negotiation server (NSA) carries out the negotiation process by sending the XML-wrapped negotiation proposal to NSB, which represents the seller UB. NSB checks the information and constraints specified in the initial proposal against the registered information of UB. In the event that a conflict or constraint violation is found, relevant strategic rule(s) which have been provided by a negotiation expert EB are applied to either (1) reject the proposal, (2) to consult with UB for decision-making, (3) to suggest possible changes to NSA, or (4) to generate a counter-proposal to be returned to NSA. In case UB maintains an inventory of goods (e.g., a database system), NSB can use the data and constraints of the proposal to query the database to verify the availability of certain goods. In the event that multiple counter-proposals are generated (see Sec. 4), a cost-benefit analysis component is called to perform quantitative analysis and to provide a cost-benefit rating of the alternatives. The highest ranked alternative will be sent back to UA as the counter-proposal, which starts another round of negotiation. This process will continue until an agreement is reached or either side terminates the negotiation process.

Figure 1: Web-Based Negotiation.

3Registration and Content Specification Language

Before the automated negotiation can take place, a client must first inform the corresponding negotiation server, and indirectly the other parties involved, of the goods and services he provides (in the case of a supplier) or wishes to acquire (in the case of a consumer) as well as any special requirements that may influence the negotiation (e.g., delivery constraints or special discounts for large orders). For suppliers, part of this registration procedure is done in the form of advertisements, which are published as Web pages. The contents of these advertisements can be indexed and catalogued, for example, by application domains, and are searchable just like regular Web pages. We assume that negotiation servers either maintain their own index of relevant advertisements or use a third-party tool such as search engines (e.g., AltaVista) or yellow page services (e.g., Yahoo) to help locate the advertisements (“information pull model”). Alternatively, one can also envision a scenario in which suppliers actively inform the relevant negotiation servers of their goods and services by sending the advertisements directly to the servers (“information push model”). The approach to negotiation described in this paper is independent of the particular paradigm (i.e., either push or pull) used by suppliers. For simplicity, we assume the information push model is being used. For consumers, registration is done by submitting a set of requirements, constraints, and negotiation rules describing the desired goods or services and negotiation strategies to a negotiation server of their choice.

Multiple negotiation servers are made available on the Internet. A description of the procedures and criteria for selecting a negotiation server is beyond the scope of this paper. In this section, we focus on the registration procedure and supporting facilities.

First, in order for an arbitrary negotiation server to be able to communicate with its clients and process their registration information, both the sellers’ and the buyers’ information as well as the subsequent negotiations must be formulated in a common language (requirement 1) using a vocabulary that is understood by all parties involved (requirement 2). In order to satisfy the first requirement, we have developed a content specification language for expressing the registration information, i.e., attributes, data values, constraint, and strategic rules. In order to satisfy requirement 2, we need an ontology [FG94] for describing the terms and their relationships that are used during registration as well as those used in the actual negotiation process. Here, we assume that a common ontology exists and is used by negotiation participants, i.e., sellers, buyers, and negotiation servers. An in-depth discussion of the ontology (creation, editing, maintenance, etc.) is beyond the scope of this work. Another important part of registration information concerns the data that is used by the cost-benefit decision model, which will be discussed in Section 5.

3.1Data and Constraint Specification

The content specification is used by both suppliers as well as buyers to describe their requirements and constraints, which form the basis of the negotiation process. The syntax of the data and constraint specification part of the language is similar to existing object modeling languages (e.g., ODL, UML, etc.). Each item or service offered (supplier) or to be acquired (buyer) is represented as an entity, which has one or more attributes describing its properties and one or more constraints describing the attribute and inter-attribute constraints. Once completed, the finished model is then translated into an XML document and submitted to the corresponding negotiation server. For the remainder of this section, we will limit our illustrations of the content specification to supplier advertisements. Consumer registration information can be represented in a similar fashion.

The following depicts a sample advertisement for a computer system offered by a fictitious supplier.

ENTITY Computer_System {

ATTRIBUTE:

model StringENUMERATION{PII300, PII350, PII400}

memory Integer ENUMERATION {32m,64m, 96m}

monitor Integer ENUMERATION {17, 19}

hard_drive Integer ENUMERATION {4g, 6g, 8g}

serviceStringNotNegotiableENUMERATION("3 years service contract")

unit_priceFloat DERIVED

deliver_dayInteger RANGE(7..14)

quantityInteger?

CONSTRAINT:

quantity_deliver_day_1quantity >= 20 implies deliver_day >10

model_memory_1model = 'PII400' implies memory >=64m

}

In this example, the supplier is advertising a computer system, which is represented as ENTITYComputer_System. The advertised entity is available in many different configurations as described by the attributes. Each attribute value is of a particular (atomic) type (e.g., String, Integer). An attribute constraint is specified by enumerating a set of possible values (note that a single value is a special case of an enumeration) or by a value range. In addition, attributes whose values depend on other values and cannot be determined until the negotiation is under way are marked as derived. In addition, some attribute values are withheld and are marked by ? (meaning “ask for value during negotiation”). All attribute values are negotiable unless marked by the special keyword NotNegotiable.

Constraints specify the requirements that a client wants to be upheld during the negotiation. In a sense, an attribute which is marked as NotNegotiable represents one kind of constraint (attribute constraint). In addition, inter-attribute constraints are used (see below). There is a third kind of constraint, called external data constraint, which is similar to attribute constraint except that the values are not part of the registration information but stored externally, e.g., in a separate inventory database keeping track of how many items are available for sale. In the above example, an attribute constraint is shown for the service attribute. The question mark ? which takes the place of the value for the quantity attribute indicates an external data constraint (i.e., the exact value depends on the chosen configuration and must be looked up in the inventory database of the supplier).

The two public constraints (i.e., they are visible to the other party), which are listed explicitly under the Constraint keyword, represent inter-attribute constraints. The syntax for inter-attribute constraints is:

constraint-name antecedenceor

constraint-name antecedenceimpliesconsequence

Inter-attribute constraints describe the relationships between two or more attributes and may result in the splitting of the original proposal into several instances during proposal evaluation (see Sec. 4). In the example above, the constraint called model_memory_1, for example, specifies that if a customer opts for a computer system with model attribute value ‘PII400’, the corresponding memory size must be at least 64MB.

3.2Negotiation Strategic Rules

So far, we have described the format of advertisements and requests for goods including various constraints using our content specification language. As mentioned before, an important part of the registration procedure is the specification of negotiation strategies to be used by the negotiation server on behalf of its client. Each strategy is represented in terms of strategic rules, which specify the conditions to be checked and the actions to be taken by the negotiation server, given the occurrences of specific events during the negotiation process. Specifically, events can be violations of attribute and inter-attribute constraints, the receipt of a counter-proposal, the decision to reject a proposal, etc.

A strategic rule has three parts: (1) the condition under which the subsequent action is to be taken (e.g., proposed sales price is below manufacturing cost), (2) the particular action to be taken when the condition is met (e.g., generation of a new value for the counter-proposal), and (3) an optional alternative action to be taken when the condition is not met (e.g., request for human intervention). The relationships between events and rules are specified by triggers [LS98]. A trigger specifies that, upon the occurrence of any number of alternative events (trigger events), a composite event or event history should be checked. If the condition evaluates to True, a structure of rules is activated. This separation of events, rules, and triggers allows more flexibility in pairing of events with rules. Furthermore, it makes a clearer distinction between trigger events, the verification of composite events or event history, and the rule structure than is possible in traditional ECA rules.