A replicable Web-Based Negotiation Server for e-commerce

Download 82.92 Kb.

Date	08.01.2017
Size	82.92 Kb.
	#7675

n Proceedings of the First Workshop on Internet Based Negotiation Technologies, Yorktown Heights, NY, March 18-19, 1999

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^¹ 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 String ENUMERATION{PII300, PII350, PII400}

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

monitor Integer ENUMERATION {17, 19}

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

service String NotNegotiable ENUMERATION("3 years service contract")

unit_price Float DERIVED

deliver_day Integer RANGE(7..14)

quantity Integer ?

CONSTRAINT:

quantity_deliver_day_1 quantity >= 20 implies deliver_day >10

model_memory_1 model = 'PII400' implies memory >=64m

}

In this example, the supplier is advertising a computer system, which is represented as ENTITY Computer_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 antecedence or

constraint-name antecedence implies consequence

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.

The following three simple examples outline some of the capabilities of our strategic rules; additional details are provided in subsequent sections. Please refer to the Entity Computer_System in the sample advertisement above for context. In the example, events are posted by a negotiation server upon encountering a conflict or violation of an attribute or inter-attribute constraint. The event names are generated by extending the corresponding constraint and attribute names. Since the sample negotiation rules are very simple (no composite events) we only show the trigger events and rules that constitute trigger specifications instead of using the full syntax of our content specification language.

Strategic Rule 1: If deliver_day out of range or quantity_deliver_day_1 constraint violated (TRIGGER EVENT), check value of attribute unit_price (CONDITION). If proposed unit_price less than the one stated by client, adjust deliver_day to 14 (ACTION). O.w., notify client (ALTERNATIVE ACTION).

TriggerEvent deliver_day_violation OR quantity_deliver_day_1_violation

Rule Condition proposal.unit_price < unit_price

Action proposal.deliver_day =14

Alternative notify_manager()
Strategic Rule 2: If proposed model, memory, hard_drive, or monitor values do not meet the specifications outlined in the supplier’s advertisement (TRIGGER_EVENT), the proposal is rejected (ACTION). Note, a missing condition means the action is always taken (condition always TRUE).

TriggerEvent model_violation OR memory_violation OR hard_drive_violation OR monitor_violation

Rule Action reject_proposal(message);
Strategic Rule 3: If the quantity_price_1 constraint is violated (EVENT), modify the constraint of quantity to range [5...10].

TriggerEvent quantity_price_1_violation

Rule Action proposal.quantity = RANGE[5.. 10]

4Negotiation Process

We now describe three important aspects of the negotiation process: (1) the negotiation primitives, which define messages passed between negotiation parties, (2) the negotiation proposal, which expresses negotiation conditions and constraints, and (3) the procedure for processing the proposal, which includes constraint checking, triggering of strategic rule, inventory verification, and cost-benefit analysis.

4.1Negotiation Primitives

The following table shows a list of negotiation primitives used in our system. It is a subset of the primitives given in [MUL96]. Many other primitives stemming from work in agent communication languages are not germane to this work.

Proposal	Initiate a proposal or return a counter-proposal
Accept	Accept the terms and conditions specified in a proposal without further modifications
Terminate	End current negotiation process and terminate session
Reject	Reject the current proposal with or without an attached explanation
Acknowledge	Acknowledgement after receiving a message
Modify	Modification to the proposal received last
Withdraw	Withdraw latest proposal

Table 1: Negotiation Primitives.

4.2Negotiation Proposal

A client initiates a negotiation process by sending a proposal via its server to tell the other side about his intentions, requirements, and constraints with respect to a planned purchase. The proposal will be evaluated, modified, and returned during the negotiation process and is the basis of analysis for reaching a final agreement. Existing negotiation systems allow only constant values to be specified in a proposal. For example, in a proposal describing a task allocation scenario, the negotiated task must have fixed values for resource requirements, time deadline, cost, etc. When buying a TV, for example, the proposal must provide values for the TV's size, brand name, price, etc. The disadvantages of this restriction are obvious. First, a client may not have the domain knowledge to give a value for a certain attribute. In our example below, the computer buyer has no idea about the particular warranty contract, which is available for the desired product and should be able to leave this value unspecified. Second, a client may not have enough knowledge to compute values that depend on other (unknown) values. For instance, determining the proper CPU/memory configuration is a complicated decision task for most customers. Instead, clients may be able to specify ranges of values or enumerate alternatives for these attributes. In our approach, a negotiation proposal/counter-proposal contains the specification of data conditions and constraints associated with goods and services, under which a buyer or seller wants to buy or sell. We use the same content specification language to specify proposals and counter-proposals as in the registration phase for specifying advertisements. Proposals are translated into XML documents for transmission to the other party.

The following is an initial proposal issued by a buyer to purchase computers (XML tags not shown):

Entity Proposal{

ATTRIBUTE:

model String ENUMERATION{"PentiumII 350"} NotNegotiatiable

monitor Integer ENUMERATION{15, 17, 19}

memory Integer RANGE[16m..64m]

hard_drive Integer RANGE [1g.. 12g]

service String ?

unit_price Float ENUMERATION{1700.00}

deliver_day Integer RANGE[3..10]

quantity Integer RANGE[10..30]

CONSTRAINT:

Constraint1 memory < 64m implies hard_dirve < 4g

Constraint2 monitor = 15 implies unit_price < 1500

}

A more abstract representation of a proposal is a tree of attributes and constraint specifications. Each composite attribute is represented by a substructure of attributes or composite attributes. Since range and enumeration are used to specify the constraints of some or all of the attributes, a proposal specifies many combinations of data values. In this work, a proposal is treated and stored as an instance of a proposal class. The data, attribute, and inter-attribute constraints of the proposal instance are processed against the registered data and constraints of the recipient of the proposal. Comparison operators for Range and Enumeration are introduced for processing the data. During processing, conflicts or violations of constraints will result in the posting of the corresponding violation events. Note that proposal and the registration information differ mainly in the fact that proposals do not include any strategic rules. Also, note that the constraints in a proposal must be consistent with the registered constraints of the client issuing the proposal.

4.3Negotiation Procedure

After receiving a proposal, a negotiation server has the following choices: accept it, modify it and respond with a counter-proposal, reject it with an optional explanation, or terminate the negotiation. In order to arrive at a decision, the negotiation server follows the following general proposal processing procedure (in pseudo-code):

Check attribute constraints given in the proposal against registration information

IF (violations found)

THEN post proper events in order to trigger strategic rules

ELSE modify the proposal so that both sets of constraints are satisfied

Check inter-attribute constraints

IF (range value in antecedence overlaps with a value in registration information)

THEN split the range to create two instances of the proposal

IF (consequence violation)

THEN post proper events to trigger strategic rules to either modify proposal, reject proposal, notify manager, terminate, etc.

IF (terminate)

THEN send terminate message

IF (proposal class is empty, i.e., no proposal instance satisfies the registered constraints)

THEN send reject message

ELSE call the DBMS to verify if the inventory can satisfy each proposal instance and delete the instance if not

IF (proposal class is empty)

THEN send reject message

ELSE IF (only one proposal)

THEN send it as counter-proposal

ELSE invoke cost-benefit analysis to do quantitative analysis of the alternatives; pick the best as the counter-proposal

We shall explain the above procedure using examples. The buyer’s proposal is processed by the negotiation server NSB against the seller’s registration information given in Sec. 3. The procedure first matches the two sets of attribute constraints. Since there is no violation, no strategic rules are triggered. The proposal is modified so that the specification satisfies both sets of constraints as shown below:

Entity Proposal{

model String ENUMERATION{"PII350"}

monitor Integer ENUMERATION {17,19}

memory Integer ENUMERATION{32m, 64m}

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

service Integer ENUMERATION{"3 years free repair"}

unit_price Float ENUMERATION{1700.00}

deliver_day Integer RANGE(7..10]

quantity Integer RANGE[10.. 30]

}

NSB continues to check the inter-attribute constraints. Now, it finds that the quantity_deliver_day_1 constraint given in the advertisement specifies that if the ordered quantity is greater or equal to 20, the number of days for the delivery has to be greater than 10. Based on this constraint, NSB will split the quantity value range into two ranges, namely {10..19} and {20..30}, and create two new instances of the proposal labeled A and B to replace the original instance.

A: Proposal{

model String ENUMERATION{"PII350"}

monitor Integer ENUMERATION{17,19}

memory Integer ENUMERATION{32m, 64m}

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

service Integer ENUMERATION{"3 years free repair"}

unit_price Float ENUMERATION{1700.00}

deliver_day Integer RANGE(7.. 10]

quantity Integer RANGE[10..19]

}

B: Proposal{

model String ENUMERATION{"PII350"}

monitor Integer ENUMERATION{17,19}

memory Integer ENUMERATION{32m, 64m}

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

service Integer ENUMERATION{"3 years free repair"}

unit_price Float ENUMERATION{1700.00}

deliver_day Integer RANGE(7.. 10]

quantity Integer RANGE[20, 30]

}

Continuing with the analysis, instance A is left unmodified because the ranges of quantity and deliver_day do not violate the constraints in the advertisement. However, instance B violates the constraint quantity_deliver_day_1. The violation triggers the strategic rule 1 given in Sec. 3. If the seller derived unit_price is $1,800, instance B will be modified as shown below:

B: Proposal{

model String ENUMERATION{"PII350"}

monitor Integer ENUMERATION{17,19}

memory Integer ENUMERATION{32m, 64m}

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

service Integer ENUMERATION{"3 years free repair"}

unit_price Float ENUMERATION{1700.00}

deliver_day Integer ENUMERATION{14}

quantity Integer RANGE[20, 30]

}

Now both A and B are consistent with the rest of the inter-attribute constraints, including the constraints specified in the buyer’s proposal. Assuming the existence of a DBMS-controlled inventory, NSB verifies these two instances by generating queries. For example, proposal A is used to generate the following SQL query:

SELECT *

FROM Computer_Inventory

WHERE model = "PII350" AND

(montior =17 OR monitor = 19) AND

(memory = 32m OR memory = 64m) AND

(hard_drive = 4g OR hard_drive= 6g OR hard_drive = 8g) AND

(service = "3 years free repair") AND

(unit_price = 1700.00) AND

(devliver_day >7 AND deliver_day <=10) AND (quantity >=20 AND quantity <=30);

The inventory validation process may remove some proposal instance(s) from the class, if the inventory can not meet the instance’s requirements. When multiple instances remain, a quantitative cost-benefit analysis need is performed to determine the best candidate for a counter-proposal or a final agreement.

When the counter-proposal arrives at the buyer's NSA, it will go through a similar processing procedure except that the registered constraints, strategic rules, and the cost-benefit evaluation model of the buyer are used. After that, NSA may decide to reject or accept the counter-proposal, or generate another counter-proposal to be sent back to NSB. This back-and-forth process continues until a mutual agreement is achieved or either side terminates the negotiation process. A formalized specification of the negotiation process is shown in the finite state diagram in Figure 2.

Figure 2: Finitie State Diagram for Negotiation Process.

In this finite state machine, S0 to S6 represent the different states of a negotiation server during a negotiation process. E is the terminal state in which an agreement or disagreement is reached. The sent (Send) and received (Recv) primitives specify the interactions between negotiation servers and cause state transitions. For example, the sequence of transitions, S0S1S2S4S2S6E, can be interpreted as follows: NSA sends a purchase proposal to NSB (S0S1) and receives a counter-proposal from NSB (S1S2). After evaluation, NSA rejects the counter-proposal (S2S4) but receives a second counter-proposal from NSB (S4S2). NSA decides to accept the second proposal (S2S6) and sends out an acceptance message. It receives an acceptance message from NSB (S6E). A mutual agreement is therefore reached and the negotiation process terminates.

5Quantitative Cost-Benefit Decision Model

Negotiation is a complex decision making process, which may involve many activities. The decisions may include not only the rejection or acceptance of a proposal, but also the evaluation of and the selection from multiple choices. The latter is needed in the following situations:

A client receives a proposal, which specifies a number of alternative negotiation conditions.
A client may conduct negotiations simultaneously with multiple parties.
A single proposal may be split into multiple candidate counter-proposals.
A single proposal may contain a large number of value combinations, which need to be evaluated to make the selection (since a proposal uses range, enumeration, and constraints to specify purchase or sales requirements).

A systematic, quantitative, and justifiable cost-benefit evaluation model is needed for implementing an automated negotiation system. In this work, we have adapted the cost-benefit decision model (CBDM) reported in [SU87]. In this model, the contents of each proposal instance are divided into two structures: the cost structure, which contains all the attributes to which costs can be assigned, and the preference structure which contains all the attributes to which preference scores can be assigned subjectively (note: these two sets of attributes may overlap). The structures are separately analyzed to obtain two values: a cost value and the global preference score. These two values are then combined to derive a global cost-preference indicator for each proposal instance.

In the preference analysis based on the preference structure, preference scores in the range of zero to one are assigned to all the attribute-value pairs using a set of “elementary criteria.” The elementary preferences are then weighted and aggregated into a global reference rating using a spectrum of “preference aggregation functions”, which are derived from a weighted power mean:

By varying the value of r, a spectrum of aggregation functions is generated, including common functions such as min, max, weighted arithmetic mean, etc. Some commonly used functions are given in Table 2:

Minimum	E= min(e1, e2, … ,en)	r = -
Harmonic mean	E=1 / (w1/e1+w2/e2+… + wn/en)	r = -1
Geometric mean	E….	r=0
Weighted arithmetic mean	E=w1e1 + w2e2 +… wn*en	r=1
Square mean	E=	r=2
Maximum	E= max(e1, e2, …., en)	r=+

Table 2: Aggregate Function Spectrum.

These alternative aggregation functions represent different degrees of conjunction and disjunction of negotiation conditions. They can be selected by clients to suit different decision situations and for the selection of different products and services. For example, the maximum aggregation function is suitable when one or more of the negotiation conditions is acceptable to a client. In that case, the maximal value of the preference scores derived for the negotiation conditions will be used as the global preference score.

6Conclusion

In this paper, we have presented an architecture and the services provided by a replicable Web-based negotiation server. A content specification language for information registration, a negotiation protocol and procedure, and a cost–benefit decision model were described. In contrast to most of the existing research on negotiation, which is based on distributed agent technology, our work makes use of object-oriented, active database technology. We introduce a content specification language, which is based on an extended object model. The language is used by buyers to specify the data characteristics and constraints of goods and services in which they are interested; and by sellers to publish information about the goods and services they wish to provide. Negotiation experts also use this language to specify negotiation strategies in terms of active negotiation rules. The same language is used by clients to define proposals and counter-proposals. The constraint, event, rule and trigger specification facilities of the language and its object model are extensions of the traditional object definition language and model, in which objects are defined only in terms of attributes and methods. The added semantics in the specifications of goods and services and negotiation proposal/counter-proposal allow negotiation servers to carry out constraint checking, activation of negotiation strategic rules, and the generation of counter-proposals in an automated fashion. In our research, we have found that existing work on auctions and bargaining-type negotiations focuses mainly on single negotiation items (e.g., price alone) and uses a single element scoring function or a single aggregation function [SIE97] to evaluate proposals. In distinction, our work tackles negotiation problems that involve multiple negotiation items and uses a number of elementary scoring functions and a spectrum of aggregation functions to conduct cost–benefit analyses.

The design and implementation of the negotiation server is in progress; the four negotiation services described in Sec. 2 are being implemented. We make use of our existing object manager to provide meta-data management and persistence for the registration service. Our Event-Trigger-Rule server, which is based on CORBA, is being modified to operate over the Web. It will be used to provide the event management and rule services needed for processing negotiation rules.

References

[BEA96] C. Beam, A. Segev, and J.G. Shanthikumar " Electronic Negotiation through Internet-based Auctions", Technical Report, University of California at Berkeley, 1996.

[BEA97] C. Beam, A. Segev, et al., “Electronic Catalogs and Negotiations,” Technical Report, University of California at Berkeley, 1997.

[DAV80] R.G. Smith, “The contract net protocol: High-level communication and control in a distributed problem solver.” In Readings in Distributed Artificial Intelligence (A. Bond and L. Gasser, eds.), Morgan Kaufmann, San Mateo, CA, 1980.

[FG94] M.S. Fox and M. Gruninger, “Ontologies for Enterprise Integration,” in Proceedings of the Second International Conference on Cooperative Information Systems (CoopIS), Toronto, Canada, pp. 82-89, 1994.

[KOI98] J. Koistinen and A. Seetharaman, “Worth-Based Multi-Category Quality-of-Service Negotiation in Distributed Object Infrastructures”, HP Technical Report, 1998

[KUM98] M. Kumar and S. I. Feldman, “Business negotiation on the Internet.” IBM Institute for Advanced Commerce (IAC) Report, 1998. http://www.ibm.com/iac/reports-technical/reports-bus-neg-internet.html

[LS98] H. Lam and S.Y.W. Su, “Component Interoperability in a Virtual Enterprise Using Events/Triggers/Rules”, In Proc. of OOPSLA ’98 Workshop on Objects, Components, and Virtual Enterprise, Oct. 18-22, 1998, Vancouver, BC, Canada.

[LEE97] J. G. Lee et al., "ICOMA: An open infrastructure for agent-based intelligent Electronic Commerce on the Internet ", In Proceedings of the International Conference on Parallel and Distributed Systems (CPADS). IEEE Comp Soc, Los Alamitos, CA, pp 648-655, 1997. http://seopo.skku.ac.kr/~feb01/papers/icpads.ps

[MUL96] H. J. Muller, “Negotiation Principles”, Chapter 7, Foundations of Distributed Artificial Intelligence, (G. M. P. O’Hare and N. R. Jennings eds.), John Wiley & Sons, Inc, 1996.

[OLI97] J. R. Oliver, "A Machine Learning Approach to Automated Negotiation and Prospects for Electronic Commerce", Journal of Management Information Systems, 13(10), pp. 83-112. http://opim.wharton.upenn.edu/~oliver27/papers/jmis.ps

[SAN95] T. Sandholm et al., "Issues in Automated Negotiation and Electronic Commerce: Extending the Contract Net Framework”, In First International Conference on Multi-Agent Systems (ICMAS-95), San Francisco, CA, 1995. ftp://ftp.cs.umass.edu/pub/lesser/sandholm-icmas95-issues.ps

[SIE97] C. Sierra, P. Faratin and N. Jennings: "A Service-Oriented Negotiation Model between Autonomous Agents, In Proc. 8th European Workshop on Modeling Autonomous Agents in a Multi-Agent World (MAAMAW-97), Ronneby, Sweden, 17-35.

[SU87] S. Y. W. Su, J. Dujmovic, D. S. Batory, S. B. Navathe, and R. Elnicki, “A Cost-Benefit Decision Model: Analysis, Comparison, and Selection of Database Management Systems,” ACM Transactions on Database Systems, Vol. 12, No. 3, Sept. 1987, 472-520.

[ZLO96] G. Zlotkin, S. Jeffrey, and A. Rosenschein, "Mechanism design for automated negotiation and its application to task oriented domains", Artificial Intelligence 86 (1996), pp. 195- 244.

 Work funded by a NIST/ATP grant.

1 The terms he, his, etc. are used throughout this paper to refer either to an individual (male or female) or a company.

Database Center - University of Florida

Directory: ~jhammer -> publications
publications -> An Internet-based Negotiation Server for e-commerce 
publications -> An Internet-based Negotiation Server for e-commerce 

Download 82.92 Kb.

Share with your friends: