A Model-Driven Approach for the Rapid Development of E-Negotiation Systems [original]

A Model-Driven Approach for the Rapid

Development of E-Negotiation Systems1

Morad Benyoucef and Stefanie Rinderle2

University of Ottawa

Ottawa, Ontario K1N 6N5, Canada

Abstract: Most of today’s e-marketplaces support a single negotiation protocol.

The protocol is usually built into the e-marketplace infrastructure, therefore if a

new one is introduced then a time consuming and complex process of

implementing it takes place. Moreover, participants in the e-marketplace need to

adapt their interfaces to the new protocol, especially if they make use of automated

means such as software agents to interact with the e-marketplace. This paper

reports on a model-driven approach and a framework for rapid and user-friendly

development of configurable e-marketplaces and automated e-negotiation systems.

A designer on the e-marketplace specifies negotiation protocols using Statecharts

and feeds them to a mapping system that transforms them into web service

orchestrations. Participants use automated negotiation systems to interact with the

e-marketplace. An automated negotiation entity capable of interacting with the e-

marketplace is generated based on the negotiation protocol implemented on the e-

marketplace. The automated negotiation entity is provided with negotiation

strategies and tactics specified in a declarative format. We propose a mapping

algorithm to transform Statechart models of negotiation protocols into web service

orchestrations.

1 Introduction

The Object Management Group (OMG) defines negotiation as “mechanisms that allow a

recursive interaction between a principal and a respondent in the resolution of a good

deal” [OMG99]. Usually, the principal and the respondent are a buyer and a seller who

are set to negotiate the price, the delivery date, the conditions of the purchase, the terms

of the guarantee, etc. The principal and the respondent can be individuals or

organizations. Negotiation is vital in establishing business-to-business (B2B)

relationships and, to a lesser extent, in facilitating consumer-to-consumer (C2C)

commercial interactions. Indeed, a report by the Hurwitz Group claims that “80% of

commerce is performed through negotiated trade” [Hur00]. Today, most of this

negotiated trade takes place electronically, facilitated by e-commerce - i.e., the process

of buying and selling goods and services electronically; and by e-business - i.e., the use

of the Internet and information technology (IT) to execute all business processes in the

enterprise, including e-commerce.

1 This work was conducted as part of a SSHRC funded project on E-Negotiations, Media, and Transactions for

Socio-Economic Transactions

2 Stefanie Rinderle is from University of Ulm, Germany. This work was conducted during her post-doctoral

stay at the University of Ottawa, Canada

Proc. Workshop on Enterprise Modelling and Information Systems Architectures (EMISA'05),

Klagenfurt, Austria, October 2005

By integrating their IT infrastructures with those of their partners, traditional businesses

are moving closer towards becoming real e-businesses. We believe that IT supported

negotiation is a cornerstone in that integration. Electronic negotiation (e-negotiation)

takes place when the negotiating function is performed through electronic means. We

talk of fully automated e-negotiation when all parties involved are software agents, semi-

automated e-negotiation when a human negotiates with a software agent, and manual e-

negotiation when all parties are human [BSS96]. The interest in e-negotiation is

motivated by its potential to provide business partners with more efficient processes,

enabling them to arrive at more satisfying agreements in less time.

The most basic form of e-negotiation is the fixed price sale where an online seller offers

goods or services at “take-it-or-leave-it” prices then buyers decide whether or not to

make a purchase at the posted price. Auctions are a bit more complex and they are

currently the most visible form of e-negotiation. Online auctions can reach a large and

physically distributed audience at reduced cost, whereas offline auctions tend to cost

more and require that the participants gather in one physical location. E-negotiations can

take an even more complex form called bargaining. This involves making proposals and

counter-proposals until an agreement is reached [San99]. Bargaining can be bilateral or

multi-lateral, depending on whether there are two or more parties involved [OMG99]. If

the object of the negotiation has more than one negotiable attribute (e.g., price, quality,

and delivery date) then we talk of multi-attribute e-negotiations.

The negotiation process is manually intensive therefore using e-negotiation systems to

automate it can reduce the costs associated with it [Hur00]. This is why the interest in

designing these systems has focused on achieving higher efficiency and lower

transaction costs [Mal87]. We distinguish three categories of e-negotiation systems

[BKS03]: (1) negotiation support systems assist users with communication and decision-

making activities; (2) negotiation software agents replace users in their communication

and decision-making activities; and (3) e-negotiation media provide a platform that

implements a negotiation protocol. There are two categories of e-negotiation media:

servers which implement multiple protocols, and applications which implement a single

protocol. Traditionally, applications have dominated negotiation design, but lately, the

importance of servers has increased, and a need for configurable servers is being felt

[NBBV03]. Attempts were made to design configurable e-negotiation media to support

more than one negotiation protocol. They were partially successful, but they were

designed in an ad-hoc manner. Some of these attempts were: the AuctionBot [WWW98]

which supports the configuration of various auctions; GNP [BKL+00] which separates

auction specifications from the logic of the server, and eAuctionHouse [Eau02] which

allows for the configuration of auctions with the help of an expert system. Recently,

Kersten et al. [KLS04] designed a configurable negotiation server that supports

bargaining, based on a process model which organizes negotiation activities into phases;

and a set of rules that govern the processing, decision-making, and communication. The

main problem in designing e-negotiation media is the lack of a systematic approach.

Indeed, to this day, design has been a trial-and-error process.

This paper presents a model-driven approach for rapid and user-friendly development of

e-negotiation systems. We consider two categories of e-negotiation systems: “e-

negotiation media” and “negotiation software agents”. We propose a new framework for

configurable e-negotiation systems in which “e-negotiation media” is the electronic

marketplace (e-marketplace) where human and software participants meet to negotiate

deals. Automated negotiation systems provide a framework for the existence of

“negotiation software agents” and serve as the interface between the negotiator and the

e-marketplace. The e-marketplace enforces negotiation protocols and therefore should

make these protocols available for consultation and automation purposes. Separating the

protocols from the e-negotiation media is a first step towards a configurable e-

marketplace. Separating negotiation strategies from protocols also brings flexibility to

the design of automated negotiation systems. Clearly, the design of e-marketplaces has a

direct effect on the design of automated negotiation systems.

The first objective of this paper is to propose a service oriented framework for e-

negotiation systems. The two main components of such framework are an e-marketplace

and an automated negotiation system. The framework enables a designer on the e-

marketplace to specify negotiation protocols and feed the resulting specification to a

mapping system that transforms them into executable processes described using a web

service (WS) orchestration language. The novelty here lies in the separation of the

protocols from the e-negotiation media as well as in the mapping algorithm. Since no

protocol exists that can fit the needs of all participants, the e-marketplace must be able to

implement any new negotiation protocol with minimum time and effort. The automated

negotiation system is also based on the separation of the negotiation protocols and

strategies from the system. Based on the negotiation protocol implemented on the e-

marketplace, an agent factory generates the component of the system that automates the

exchange between the participant and the e-marketplace. A designer on the participant’s

side can specify negotiation strategies using a declarative format. The second objective

is to propose a mapping algorithm that transforms Statechart models of negotiation

protocols into processes described using a WS orchestration language.

The paper is organized as follows: In Section 2 we discuss the use of Statecharts to

specify negotiation protocols. In Section 3 we detail our service oriented e-negotiation

framework. Section 4 describes the mapping of Statechart descriptions of negotiation

protocols into processes described using a WS orchestration language. In Section 6 we

discuss some related work, and in Section 7 we conclude and discuss the perspectives

and future work.

2 A Generic Statechart Template for Business Transactions

Based on a requirements analysis for modeling e-negotiations, Statecharts [Hare87]

qualify as an adequate formalism. Statecharts have a good formal basis and can be

serialized, visualized, and executed. They are well established, easy to understand,

complete, and can be converted into other formalisms.

In [RiBe05] a requirements analysis for the suitability of Statecharts as formalism for

modelling e-negotiation protocols as well as the Statechart models of five commonly

used e-negotiation protocols are presented. This approach is extended in the current

paper by introducing a mapping algorithm from the Statechart models to a web service

orchestration language.

As shown in Fig. 1, a negotiated transaction between two or more parties usually goes

through three distinct states. In the initialization state participating parties register on the

e-marketplace which performs the necessary checks on the parties. The initialization can

be as simple as signalling one party’s intent to participate in the transaction, in case the

e-marketplace is set up for a closed circle of registered or invited members. If the e-

marketplace is public, then the initialization can be as complex as one party completing

rigorous registration procedures, and the e-marketplace performing the necessary

verifications such as credit checks. If electronic links exist between the e-marketplace

and the ERP systems of the participating parties, the initialization can be greatly

facilitated by granting protected and restricted access to each other’s internal databases.

The negotiation state is where the parties negotiate by exchanging messages (offers,

counter offers, etc.) according to the precise protocol of the negotiation implemented on

the e-marketplace. A negotiating party can require an electronic link to its own ERP

system to automatically check stock levels, manufacturing schedules, etc. The link

makes it easier and quicker to respond to offers made by the other parties and to

formulate counter offers. A successful negotiation leads to the drafting of a contract that

needs to be executed by the agreeing parties. This is the settlement state. If a certain

level of contract automation is achieved, then electronic links to the parties’ ERP

systems are necessary to carry out certain transactions such as sending purchase orders,

receiving payments, etc.

Negotiated Transaction

Initialization

Negotiation

Settlement

ERP System

Party 2 Party 1 Negotiation

Figure 1: Generic Template for Business Transactions

3 Service-Oriented e-Negotiation Framework

Businesses are rapidly moving towards exposing their services on the web (giving way

to WS), hoping to interact more efficiently with their partners and to achieve higher

levels of automation at lower cost. For that reason our framework is based on a service

oriented architecture (SOA). We believe that WS are appropriate for deploying e-

negotiation systems because: (1) relationships between negotiating partners are dynamic;

(2) negotiation is part of procurement therefore interoperability between internal and

external IT systems is important; and (3) WS provide a standardized and flexible

integration technology that no organization can afford to ignore if it wants to interact

with its partners [KiSe05]. Simply put, WS provide the means for software components

to communicate with each other on the web using XML. A WS describes itself (using

WSDL), can be located (using UDDI), and invoked (using SOAP).

It is important to remember that the e-marketplace is deployed by a negotiation

facilitator (usually a third party) and its main role is to implement a negotiation protocol.

An automated negotiation system, on the other hand, is deployed by participants in the

negotiation (i.e., negotiators). It can be seen as the interface between the negotiator’s

internal IT systems (mainly the ERP system) and the e-marketplace. The framework

presented in Figure 2can be interpreted as follows.

The e-marketplace: a designer on the e-marketplace side uses the Protocol Modeling

Interface to design Negotiation Protocols. These protocols are usually represented using

a formal specification such as Statecharts. The designer can also use Negotiation

Templates available on the e-marketplace, and eventually modify them into negotiation

protocols that answer the needs of the moment.

Internet

Negotiation

Protocols

Mapping

yste

Negotiation

Processes

E-Marketplace

Negotiation

Strategies

Automated Negotiation System

Process

Modeling

Interface

Monitoring

Interface

Protocol

Modeling

Interface

Strategy

Modeling

Interface

Process Engine

Web Services

Negotiation

Templates

Monitoring

and Control

Interface

Software

Agent

Factory

Figure 2: Service Oriented e-Negotiation Framework

The designer can choose to directly design the processes using a Process Modeling

Interface which is a WS orchestration authoring tool. A Monitoring Interface will be

used to monitor the execution of the negotiation process. The engine runs the process.

The Automated Negotiation System: In manual or automated negotiation, we have to

distinguish between negotiation protocols which are the rules of the game (e.g., how the

exchange of offers and counter offers takes place between the participants) and the

negotiation strategies which are used by the participants to maximize their benefit (and

to minimize their loss). Negotiation tactics are the small steps taken by participants

towards achieving their strategies. Protocols are made public to every participant, but

strategies and tactics are kept secret. However, nothing keeps a participant from trying to

discover its opponent’s strategies and tactics by observing the opponent’s present and

past behavior. In the framework of Figure 2 a designer on the participant’s side uses a

Strategy Modeling Interface to design Negotiation Strategies. Based on the negotiation

protocol implemented on the e-marketplace, a Software Agent Factory generates the

components of the system that automates the exchange mechanism between the

participant and the e-marketplace. A Monitoring and Control Interface is used to monitor

and control the behavior of the automated negotiation system. The WS component

groups all the interactions of the Automated Negotiation System and makes them

available in the form of WS.

4 On Mapping Negotiation Protocols to Web Service Orchestrations

In this section we provide an algorithm for mapping Statechart models of e-negotiation

protocols to processes described within a WS orchestration language.

4.1 Statecharts and Web Service Orchestration Language (BPEL4WS)

One particularity of our service oriented e-negotiation framework is the fact that it is

based on the separation of negotiation protocols from the e-negotiation media (i.e., the

implementation of the e-marketplace). This separation is achieved by using Statecharts

to specify the protocols. Based on [JaSu04] we define a Statechart as a tuple ST= (S, T,

E, C, A, sinitial, sfinal) where

• S is a finite set of states, E is a finite set of events, C is a finite set of conditions, and A is

a finite set of actions

• T ⊆ S × E × C × 2A × S is a finite set of transitions where 2A denotes the power set of A

• sinitial ∈ S is the (unique) initial state (i.e., sinitial has no incoming transitions)

• sfinal ∈S is a final state (sfinal has no outgoing transitions)

From different case studies we derived several assumptions which hold for the Statechart

models of e-negotiation protocols. Firstly, the event and action parts of the transitions

comprise message sending and receiving events, i.e., the e-marketplace either waits for

an incoming message sent by one of the participants or the e-marketplace itself sends a

message to one or more of the participants3. Secondly, we assume that the Statechart

models are hierarchically decomposed (i.e., except for concurrent flow super-states there

are no hierarchical states). For example, super-state Negotiation (cf. Figure 6a) can be

decomposed and removed without losing basic information. As mentioned, one

exception is the use of concurrent execution where sub-states may be ordered in parallel

but must not be hierarchically decomposed themselves. Thirdly, the use of cyclic

structures is restricted to loops with length less than three (i.e., only short loops of length

one and mutual calls between two states of length two are allowed). The above

assumptions can be formalized as follows:

Let EType be the set of all possible event types and let AType be the set of all possible

action types. Let further eType: E Æ EType be the function which maps events to their

specific event type and aType: A Æ AType the function which maps actions to their

specific action types. Then:

o ∀ e ∈ E: eType(e) = msg_receiving

o ∀ e ∈ E: e = rec_message(sender, [paramList]) where sender is one of the e-marketplace

participants

o ∀ a ∈ A: aType(a) ∈ {msg_sending, assign_values}

o ∀ a ∈ A with aType(a) = msg_sending:

a = send_id(sender, [paramList]) where sender is one of the participants of the e-

marketplace

o no loops with lengths > 2: Let ST = (S, T, E, C, A, i, f) and ST’ = (S, T’, E, C, A, i, f) be

Statecharts where ST’ is obtained by reducing transition set T of ST in the following

way:

- if ∃ s ∈ S with ∃ (s, e, c, a, s) ∈ T: T’ := T \ {(s, e, c, a, s)}

- if ∃ s, s’ ∈ S with ∃ (s, e, c, a, s’), (s’, e’, c’, a’, s) ∈ T: T’ := T \ {(s’, e’, c’, a’, s)}

Then ST’ has to be acyclic.

o ST is hierarchically decomposed except for concurrent execution

o Concurrent execution contains no hierarchically decomposed sub-states∃ e ∈ E:

eType(e) = msg_receiving with ∃ T = (i, e, c, a, s), i.e., there is a transition condition

containing a message receiving event4

As a WS orchestration language we use a subset of BPEL4WS. Within this paper a

BPEL4WS process P is defined as a tuple P = (A, AT, S, ST, V, VL, PT, PL, i) where

• A is the set of simple activities and S is the set of structured activities

• AT is the function which assigns to each simple activity its particular type, i.e.:

AT: A → {<assign>, <empty>, <terminate>, <receive>, <invoke>, <pick>}

• ST is the function which assigns to each structured activity its particular type, i.e.: ST: S

Æ {<sequence> … </sequence>, <switch> … </switch>,

<flow> … </flow>, <while> … </while>}

• V is the set of variables and VL ⊆ (A × V) ∪ (V × A) is the set of read / write accesses

linking activities to variables and vice versa

• PT is the set of port types and PL is the set of partner links

• i is the initial state of P

3 In addition, the action part of a transition may include the assignment of process variable values.

4 This is important in order to generate the first receive activity within the process that drives the e-

marketplace which initiates a new process instance.

4.2 Pattern-wise Mapping

In general, finding a complete mapping from Statecharts to a WS orchestration language

such as BPEL4WS is a difficult task. Some approaches face this challenge in order to

provide a model-driven development of WS [BBCT04, BDS05]. However, these

approaches are based on some restrictions and assumptions (e.g., restricting transitions

conditions to the conditional part). In our approach we start from a different direction by

exploiting the assumptions which result from the specificity of Statechart models of e-

negotiation protocols (cf. Section 4.1). Furthermore, we exploit the idea of identifying

commonly used patterns within the Statechart models (comparable to workflow patterns

in the process management domain [AHKB03]). For these commonly used Statechart

patterns the corresponding BPEL4WS patterns have been elaborated. In the following

we present and describe a selection of important patterns (for a more detailed description

on the pattern-wise mapping refer to [BeRi05]). We provide an algorithm that constructs

the complete BPEL4WS process based on these patterns in Section 4.3.

Figure 3 depicts the Statechart pattern for a sequence of states S1 and S2 connected by

transition (S1, msg1(s1, pL1), cond1, msg2(s2, pL2), S2). The associated BPEL4WS

pattern is shown as sub-pattern SP1_2: the e-marketplace waits for receiving message

msg1 from sender s1. If msg1 is received and condition cond1 is true then the e-

marketplace invokes the associated operation within the port type connected with sender

s2 by sending message msg2. The parameter lists of messages msg1 and msg2 constitute

the variables of the e-Marketplace. Note that a more precise definition of the variables is

conceivable by splitting the parameter lists into single parameters and specifying the

associated variables of the e-marketplace. The data flow is specified within the

implementation of the receive and invoke operations (e.g., operation invoke_msg2 has

input variable pL1 and output variable pL2). There may also be variations like sub-

pattern SP1_1 (cf. Figure 3) depending on whether the event or the condition part of

transition (S1, msg1(s1, pL1), cond1, msg2(s2, pL2), S2) is specified or not. Sub-pattern

SP1_3 reflects the case where, within the action part of the transition, not only a message

is sent but also a certain value is assigned to a particular process variable.

S1 S2

msg1(s1, pL1)[cond]\msg2(s2, pL2)

Statechart Pattern:

Corresponding BPEL4WS Patterns:

Transition from S1 to S2 contains:

Pattern1: Sequence (one incoming, one outgoing transition)

Variables

Partner Links:

<plnk: name=”e-Marketplace

ÅÆ

s1”/>

<plnk: name=”e-Marketplace

ÅÆ

s2”/>

Port Types:

e-Marketplace

ÅÆ

s1:

e-Marketplace

ÅÆ

s2:

SP1_2: event, condition, action SP1_3: event, condition, assign, action SP1_1: no event, condition, action

switch

invoke_msg2



cond

terminate

otherwise

receive_msg1



switch

invoke_msg2



cond

terminate

otherwise

receive_msg1



switch

invoke_msg2



cond

terminate

otherwise

assign_param

Figure 3: Sequence with Different Sub-Patterns

When mapping a Choice Statechart pattern (i.e., transitions from one to different other

states are possible) the resulting BPEL4WS process pattern depends on whether the

choice is based on different conditions (then the corresponding BPEL4WS process is a

switch construct) or if it is triggered by different incoming messages (then a pick

construct is used instead, cf. Figure 4).

These simple patterns give an idea of the principle of a pattern-wise mapping between

Statecharts and BPEL4WS. In [BeRi05] mappings for more complex patterns are

introduced: Pattern 3 (Short Loop) for loops of length 1, Pattern 4 (Mutual Call) for

loops of length 2, and Pattern 5 (Concurrent Flow) for states which are ordered in

parallel. Note that we do not claim completeness of our mapping approach. Our aim it to

present a practicable approach for the model-driven development of e-negotiation

processes.

4.3 Mapping Algorithm

Starting from the initial state the algorithm analyzes the Statechart patterns by traversing

the Statechart graph and maps them to the associated BPEL4WS patterns as described in

Section 4.2 and [BeRi05]. A Statechart pattern is determined by the currently analyzed

state, its outgoing transitions, and its direct successor states.

S1 S2

msg11(s11,pL11) [cond1]\msg12(s12, pL12)

Statechart Pattern:

Corresponding BPEL4WS Patterns:

Choice is based on:

Pattern

Choice

ncoming, at least

two outgoing

ansitions

and none of them a short loop)

msg21(s21, pL21)

[cond2]\msg22(s22, pL22)

Variables:

Partner Links:

<plnk: name=”e-Marketplace

ÅÆ

s11”/>

<plnk: name=”e-Marketplace

ÅÆ

s12”/>

<plnk: name=”e-Marketplace

ÅÆ

s21”/>

<plnk: name=”e-Marketplace

ÅÆ

s22”/>

Port Types:

e-Marketplace

ÅÆ

s11:

e-Marketplace

ÅÆ

s12:

e-Marketplace

ÅÆ

s21:

e-Marketplace

ÅÆ

s22:

SP2_2: 2 events, 2 conditions, 2 actions SP2_1: 2 conditions, 2 actions

invoke_msg1



switch

invoke_msg2



ond

invoke_msg2



receive_msg11



pick

receive_msg21



ond

switch

terminate terminate

invoke_msg12



SP2_3: one event, 2 condtions, 2 actions

invoke_msg2



switch

receive_msg21



invoke_msg12



ond

Figure 4: Choice with Different Sub-Patterns

We start with the pattern Mutual Call which may be also combined with a Short Loop

pattern [BeRi05]. If the current pattern is neither a Mutual Call nor a Short Loop we

check the number of outgoing edges. One outgoing edge indicates the Sequence pattern,

more than one outgoing edge leads to the Choice pattern. Already “visited” states are

stored within the set VisitedStates. The states to be analyzed next are determined as the

direct successors of the currently treated state (set CurrentStates). The sets of variables,

partner links, and port types can be determined by merging the corresponding sets of the

particular patterns.

As an example we apply the mapping algorithm to the Statechart model of the Dutch

auction protocol [RiBe05] as depicted in Figure 6a resulting in the BPEL4WS process

depicted in Figure 6b.

Algorithm MapStateChartToBPEL4WS

input: Statechart model ST= (S, T, E, C, A, s

initial

, s

final

)

output: BPEL4WS process

initialization

CurrentStates := {s

initial

}; VisitedStates := ∅;

begin

// parse Statechart structure

while VisitedStates ≠ S do

forall s ∈ CurrentStates do

if s is super-state of concurrent sub-states

//Pattern5: Concurrent Execution

add corresponding sub-pattern of Pattern5;

VisitedStates := VisitedStates ∪ {s};

determine set of outgoing transitions tOut

= {t

, …, t

} of

S with t

= (s, e

, c

, a

, s

), k = 1,…, n;

Pattern P is determined by s, tOut

Succ

= {s

| s

∈ S, k = 1, …, n, s

≠ s},

and conT

= {t | t ∈ T, t = (s

, e

, c

, a

, s

), s

k1,

∈ Succ

};

switch

case1: ∃ t

sk1

= (s, e

sk1

, c

sk1

, a

sk1

, s

) ∈ tOut

∧ ∃ t

sk2

∈ T with t

sk2

= (s

, e

, c

, a

, s)

if ¬(∃ t

sk3

= (s, e

, c

, a

, s))

//Pattern4: Mutual Call

concatenate corresponding sub-pattern of Pattern4 at dangling edge;

if s

is super-state of concurrent sub-states

//Pattern5: Concurrent Execution

add corresponding sub-pattern of Pattern5;

else // if ∃ t

sk3

= (s, e

, c

, a

, s)

//combined sub-pattern short loop and mutual call

concatenate corresponding combined sub-pattern of Pattern4 at dangling edge;

case2: ∃ t

∈ tOut

with t

= (s, e, c, a, s)

//Pattern3: Short Loop

concatenate corresponding sub-pattern of Pattern3 to dangling edges;

case3: if |tOut

| > 1

//Pattern2: Choice

concatenate corresponding sub-pattern of Pattern2 at dangling edge;

case4: |tOut

| = 1

//Pattern1: Sequence

concatenate corresponding sub-pattern of Pattern1 at dangling edge;

CurrentStates := (CurrentStates ∪ {s

| k = 1, …, n}) \ {s};

VisitedStates := VisitedStates ∪ {s};

end

Figure 5: Mapping Algorithm

Starting with the outgoing transition of the initial state, the first pattern to be inserted is

the Sequence pattern (cf. Figure 6b). The parameter list of the incoming message

Offer_to_sell is described by the variable offer. The partner links comprise links to the

seller and the buyers. The port types turn out as a receive Offer_to_sell operation within

the partner link for the seller and an invoke of an update operation within the partner

links of the seller and the buyers. The next state to analyze is Offer. The associated

pattern comprises the set of outgoing transitions tOuts = {(Offer, …, Offer), (Offer, …,

Deal), and (Offer, …, Auction Closed)}, the set of direct successor states Succs= {Deal,

Auction Closed}, and conTs = {Deal, …, Auction Closed} and corresponds to the

combined (Mutual Call, Short Loop) sub-pattern [BeRi05]. Note that assign activities are

inserted depending on the action parts of the corresponding transitions.

6 Discussion

In [KuFe98] different price negotiation protocols such as the Dutch auction are described

using finite state machines. Although finite state machines are a formally founded

formalism, Statecharts provide additional constructs (e.g., hierarchical states) which

make them better suited for modeling e-negotiation protocols. Rolli and Eberhart

[RoEb05] propose a reference model for describing and running auctions as well as an

associated three-layered architecture which consists of the auction data, the auction

mechanism, and the auction participants. Apparently the auction protocols are modeled

manually using BPEL4WS which might be a complex task for users in general.

Offer Deal

Auction closed

Offer_to_sell(seller_id, product_description,

price, current_amount)

[Registered(seller_id)]

/ update(product_description, price,

current_amount)

[timeout ∨ price = reserve_price]

/ update(“closing”)

Accept_offer(buyer_id, amount)

[Registered(buyer_id) ∧ amount <= current_amount]

/ update(notification) ∧ current_amount := current_amount - amount

utch aucti

(n item

New_offer(seller_id, decrement)

[Registered(seller_id) ∧ decrement > 0 ]

/ price := price - decrement ∧

update(price, current_amount)

[current_amount > 0]

[current_amount = 0]

/ update(“closing”)

nitializati

Negotiation

E-Marketplace (Dutch Auction)

current_amount > 0 AND

timeout = FALSE AND

price > reserve_price

Offer

Accept_offer New_offer

assign

decrement > 0otherwise

Seller

Offer_to_sell

New_offer

update

Buyeri (i = 1,..,n)

Accept_offer

update

otherwise

amount <= current_amount AND

Registered = TRUE

amount decrement

offer

receive invoke empty

switch

while

variable

port

pick

Offer_to_sell

otherwise

Registered = TRUE

update

Sequence pattern

Combined Mutual Call

and Sh

ort Loop

pattern

Figure 6: Pattern-Wise Mapping applied to the Dutch Auction Protocol

a) b)

Kim and Segev [KiSe05] also follow an approach for establishing a web-service enabled

e-marketplace. The authors provide a Statechart description of one e-negotiation

protocol and the corresponding BPEL4WS process. In this paper we adopt the idea of

providing understandable models of e-negotiation protocols and to automate them within

a service-oriented architecture. However, we extend the approach of Kim and Segev

towards a systematic description of generic e-negotiation protocols and by providing an

automatic mapping of the Statechart models to the corresponding web service

orchestrations. In [SiRe04] e-negotiation protocols are modeled using the Petri Net

formalism. Special focus is put on the modeling of attributes which reflect the different

strategies the participants in the e-negotiation might adopt. Chiu et al. [CCH+05] present

an interesting approach for developing e-negotiation plans within a web services

environment. The authors provide meta-models for e-contract templates and e-

negotiation processes which can be used to set up the concrete e-negotiation processes

within a web service environment. Although this approach is generic, we believe that

providing (generic) e-negotiation templates (i.e., Statechart models) to users which can

be individually modified and immediately mapped onto executable web service

orchestrations is more intuitive and user-friendly.

In [BDS05] the authors present a model-driven approach for developing web services.

They model web services using the Statechart formalism and provide a mapping

procedure from Statecharts to web services. Their paper presents a general and

systematic mapping approach which has been implemented within a prototype called

SelfServ. Due to the generality of the approach there are certain restrictions imposed on

the Statechart models. One example is that transitions can be solely labeled by

conditions (i.e., the authors do not consider the event and action part of the ECA rules).

In our paper we introduce another way of addressing the challenge of mapping

Statecharts to a web service orchestration language by exploiting the specificity of the e-

negotiation domain.

7 Summary and Outlook

This paper presented our current research on providing quick and elegant ways to

develop e-negotiation systems. We proposed a service oriented framework for

developing e-marketplaces and automated e-negotiation systems. The e-marketplace

component implements a negotiation protocol and represents the virtual place where

organizations and/or individuals meet to negotiate deals. The automated e-negotiation

system component is the interface between the participant in the negotiation and the e-

marketplace. Based on the negotiation protocol implemented on the e-marketplace, this

component creates an automated entity capable of negotiating based on strategies and

tactics provided by a human. The framework is based on (1) the separation of

negotiation protocols from the e-marketplace; (2) the formal specification of these

protocols using Statecharts; (3) an algorithm that transforms these Statecharts into web

service orchestrations; and (4) the separation of negotiation strategies from the

automated negotiation entity.

The framework is built on the assumption that e-marketplace participants are invited to

join the negotiation beforehand. The number of participants is therefore known in

advance, enabling us to fix the number of partner links in the BPEL4WS process before

the negotiation starts. This assumption is realistic in B2B scenarios. Businesses usually

choose their partners as well as the virtual markets where they negotiate very carefully,

and most importantly they join the negotiation before it starts. However in C2C

scenarios (e.g., on the eBay marketplace) the number of participants is not known at the

beginning as participants dynamically register and interact. In this situation the number

of partner links and port types is unknown at the beginning of the negotiation. One future

research direction is to rethink the framework to enable new participants to enter the

negotiation after it is started.

References

[ACD+03] T. Andrews, F. Curbera, H. Dholakia, Y. Goland, J. Klein, F. Leymann, K. Liu,

D. Roller, D. Smith, S. Thatte, I. Trickovic, and S. Weerawarana.: BPELWS -

Business Process Execution Language for Web Services – Version 1.1., 2003.

[AHKB03] W.M. P. v.d. Aalst, A.H.M. ter Hofstede, B. Kiepuszewski, and A.P. Barros:

Workflow Patterns. DPD 14(1):5-51 (2003)

[BBCT04] K. Baïna, B. Benatallah, F. Casati, and F. Tournani: Model-Driven Web Service

Development. In Proc. CAiSE’04, pages 290-306, Riga, June 2004

[BSS96] C. Beam, A. Segev, and J. G. Shanthikumar. Electronic negotiation through

internet-based auctions. Tech. Rep. 96-WP1019, Haas School of Business, UC

Berkeley, December 1996

[BDS05] B. Benatallah, M. Dumas, and Q.S. Sheng: Facilitating the Rapid Development

and Scalable Orchestration of Composite Web Services. DPD 17(1):5-37 (2005)

[BKL+00] M Benyoucef, R. K. Keller, S. Lamouroux, J. Robert, and V. Trussart. Towards a

Generic E-Negotiation Platform. Int’l Conf. Re-Technologies for Information

Systems, pages 95-109, Zurich, Switzerland, February 2000

[BeRi05] M Benyoucef and S. Rinderle: A Model-Driven Approach for the Rapid

Development of E-Negotiation Systems. Working Paper 05-32, School of

Management, University of Ottawa, Canada (2005).

[BKS03] M. Bichler, G. Kersten, and S. Strecker. Towards a Structured Design of

electronic Negotiations, GDN 12: 311–335, 2003

[CCH+05] D.K.W. Chiu, S.C. Cheung, P.C.K. Hung, S.Y.Y. Chiu, A.K.K Chung:

Developing e-Negotiation Support with a Meta-Modeling Approach in a Web

Services Environment. DSS 40(1): 51-69 (2005)

[DuHo01] M. Dumas and A.H.M. ter Hofstede: UML Activity Diagrams as a Workflow

Specification Language. Int’l Conf. UML’01, pages 76-90, Toronto 2001.

[Eau02] University of Washington. The eAuctionHouse. 2002

[Hare87] David Harel: Statecharts: A Visual Formulation for Complex Systems. Scientific

Computer Programming 8(3): 231-274 (1987)

[Hur00] Hurwitz Report. Negotiated Trade: the Next Frontier for B2B e-commerce.

Technical Report. 2000.

[KLS04] G. Kersten, K. P. Law, and S. Strecker. A Software Platform for Multi-Protocol

E-Negotiations. An InterNeg Research Report 04/04, 2004

[KiSe05] J. B. Kim and A. Segev: A Web Services-Enables Marketplace Architecture for

Negotiation Process Management. DSS 40(1):71-87 (2005)

[KuFe98] M. Kumar and S.I. Feldman: Business negotiations on the Internet. Technical

Report, IBM Research Division, New York, 1998

[KuFe98a] M. Kumar and S.I. Feldman: Internet Auctions. Technical Report, IBM Research

Division, New York, 1998

[Mal87] T. W. Malone, et al., Electronic Markets and Electronic Hierarchies.

Communications of the ACM, 1987, 30(6): p.483-494.

[Muth98] P. Muth, D. Wodtke, J. Weißenfels, A. Kotz Dittrich, and G. Weikum: From

Centralized Workflow Specification to Distributed Workflow Execution. JIIS

10(2): 159-184 (1998)

[NBBV03] D. Neumann, M. Benyoucef, S. Bassil, and J. Vachon. Applying the MTL

Taxonomy to State of the Art E-Negotiation Systems. GDN 12(4):287-310,(2003)

[OMG99] Object Management Group (OMG) Negotiation Facility final revised submission.

Technical report. March 1999.

[RoEb05] D. Rolli and A. Eberhart: An Auction Reference Model for Describing and

Running Auctions. In Proc. of the Wirtschaftsinformatik, Bamberg 2005.

[ReDa98] M. Reichert and P. Dadam: ADEPTflex - Supporting Dynamic Changes of

Workflows Without Losing Control. JIIS 10(2):93-129 (1998)

[RRD04] S. Rinderle, M. Reichert, and P. Dadam: Flexible Support of Team Processes by

Adaptive Workflow Systems. DPD 16(1):91-116 (2004)

[RiBe05] S. Rinderle, M. Benyoucef: Towards the Automation of E-Negotiation Processes

Based on Web Services – A Modeling Approach. Int’l Conf. WISE’05, New

York (to appear).

[SiRe04] C. Simon and M. Rebstock: Integration of Multi-attributed Negotiations within

Business Processes. Int’l Conf. BPM’04, pages 148 – 162, Potsdam, June 2004

[San99] T. Sandholm. An Algorithm for Optimal Winner Determination in Combinatorial

Auctions. Int’l Conf. AI, pages 542-547, Stockholm, Sweden, 1999.

[WWW98] P. Wurman, M. Wellman, and W. Walsh. The Michigan Internet AuctionBot. In

Intl Conf on Autonomous Agents, pages 301-308, Minneapolis, May 1998