A multi-agent system for electronic commerce including adaptive strategic behaviours

A Multi-Agent System for Electronic Commerce including Adaptive Strategic Behaviours Henrique Lopes Cardoso 1 , Max Schaefer, Eugénio Oliveira Faculdade de Engenharia, Universidade do Porto, NIAD&R-LIACC Rua dos Bragas 4099 Porto Codex, Portugal [email protected]t [email protected] [email protected] Abstract. This work is primarily based on the use of software agents for automated negotiation. We present in this paper a test-bed for agents in an electronic marketplace, through which we simulated different scenarios allowing us to evaluate different agents’ negotiation behaviours. The system follows a multi-party and multi-issue negotiation approach. We tested the system by comparing the performance of agents that use multiple tactics with ones that include learning capabilities based on a specific kind of Reinforcement Learning technique. First experiments showed that the adaptive agents tend to win deals over their competitors as their experience increases. 1 Introduction Internet and www popularity has strongly increased the importance and popularity of electronic commerce, which goes far beyond both the searching for services exposed in virtual stores and price comparison. Electronic commerce includes a negotiation process between buyers and sellers, in order to find an agreement over the price and other transaction terms. It also deals with service demands and electronic payment. Common systems that consider mainly the electronic ads, based on the creation of classified ads sites with search capabilities, can be enhanced by semi-intelligent mechanisms relying on agent technology. Such enhanced systems can be applied to the different stages of the Consumer Buying Behaviour model, as explained in [3][4]. In particular, when applying to the negotiation process, agents enable new types of transactions, where prices and other transaction issues need no longer to be fixed. A typical case of negotiation process is the auction. Negotiation on the Internet often amounts to one party (typically the seller) presenting a take-it-or-leave-it proposal (e.g., a sale price). Auctions represent a more general approach to look for an appropriate price, admitting a range of negotiation protocols [7]. These auctionbased negotiation protocols include the English auction, the Dutch auction, the Firstprice Sealed Bid and the Vickrey auction. These auction-based protocols are called single-sided mechanisms, because bidders are all buyers or all sellers, and they also 1 The work of Henrique Lopes Cardoso has been funded by a scholarship from Subprograma Ciência e Tecnologia do 2º Quadro Comunitário de Apoio. include an auctioneer. Double-sided auctions admit multiple buyers and sellers at once, like the continuous double auction [7]. There are several auction-based systems that are in use for electronic commerce. AuctionBot is an auction server where software agents can be created to participate in several types of auctions. Kasbah is a web-based system where users create autonomous agents that buy and sell goods on their behalf [1]. It is based on continuous double auction mechanisms. In the Kasbah marketplace, buying and selling agents interact and compete simultaneously, making price bids to their counterparts. The agents have a function that changes the price they are willing to propose over time. A different negotiation approach involves negotiating over multiple terms of a transaction, unlike the typical way of auction negotiation, that only considers the price of the good. Tete-a-Tete is a system where agents cooperatively negotiate in this way. It intends to provide merchant differentiation through value-added services, like warranties, delivery times, etc. [4]. Following this more general approach, in [2] negotiation is defined as a process by which a joint decision is made by two or more parties. The parties first verbalise contradictory demands and then move towards agreement by a process of concession making or search for new alternatives. In that paper, a many parties, many issues negotiation model is adopted, that is, multilateral negotiations (like a continuous double auction) about a set of issues (the transaction terms). Several negotiation tactics are tested, and a negotiation strategy model is explained. The work described in the present paper aims to combine those tactics in a dynamic way, in order to endow adaptive market agents with strategies (appropriate ways of selecting combinations of tactics) and to compare their performance with agents that are not adaptive. Since the marketplace is a dynamic environment, adaptive agents are expected to benefit from changing conditions, therefore taking advantage over others. A test-bed has been created to provide the interaction process between market agents with different capabilities. Section 2 describes our multi-agent platform for electronic commerce (the testbed), including the negotiation assumptions, model and protocols adopted (which have been based on those introduced in [2]). Section 3 gives details on negotiation tactics (also adopted from [2]) which can be combined to either user-defined strategies or strategies based on Reinforcement Learning techniques. Section 4 focuses on several different scenarios and describes those situations that were chosen for testing purposes. Conclusions drawn from the testing scenarios are presented in section 5. We conclude the paper, in section 6, by presenting some topics of our future work. 2 A System for Electronic Commerce In this section we describe the basic negotiation approach and the architecture of the SMACE (Sistema Multi-Agente para Comércio Electrónico) system. It is a multiagent system for electronic commerce, where users can create buyer and seller agents that negotiate autonomously, in order to make deals on services they are requesting or offering. SMACE has been used as a test-bed for different negotiation paradigms, both user-controlled and self-adaptive. 2.1 Negotiation Model The negotiation model we have adopted is multilateral and based on many issues (that is, multidimensional), as described in [2]. Multilateral refers to the ability that each buying or selling agent has to negotiate simultaneously with many other selling or buying agents. In auction terms, it relates to a sealed-bid continuous double auction, where both buyers and sellers submit bids (proposals) simultaneously and trading does not stop as each auction is concluded (as each deal is made). In practical terms, this multilateral negotiation model works as many bilateral negotiations that can influence each other. The bilateral negotiation model we are using is based on the one defined in [5]. In our work, negotiation is realised by exchanging proposals between agents. The negotiation can be made over a set of issues instead of the single issue price found in most auctions. A proposal consists of a value for each of these issues and is autonomously generated and proposed by one agent. This negotiation model is also called a service-oriented negotiation model [2], since it involves two roles that are, in principle, in conflict: sellers of services and buyers of services. A service is something that can be provided by an agent and requested by some other agent, and over which they can negotiate. As a general rule, we can say that opponents in the negotiation process have opposing interests over all issues under negotiation. However it could happen that both agents have similar interests on a specific issue, thus proposal evolution may proceed in the same direction. The sequence of proposals and counter-proposals in a two-party negotiation is referred to as a negotiation thread. These proposals and counter-proposals are generated by linear combinations of functions, called tactics. Tactics use a certain criteria (time, resources, etc.) in generating a proposal for a given negotiation issue. Different weights can be assigned to each tactic used, representing the importance of each criterion for the decision making. Agents may wish to change their ratings of criteria importance over time. To do so, they use a strategy, defined as the way in which an agent changes the relative weights of the different tactics over time. For each issue j ∈ {1, …, n} under negotiation, each agent has a range of acceptable values [min ij , max ij ], and a scoring function V ij : [min ij , max ij ]  [0, 1], that gives the score an agent i assigns to a value of issue j in the range of its acceptable values. The higher the score, the better the agent’s utility. Agents also assign a weight w ij to each negotiation issue that represents its relative importance. Assuming normalised weights ( ∑ j w ij = 1), the agent’s scoring function for a given proposal x = (x 1 , …, x n ) combines the scores of the different issues in the multidimensional space defined by the issues’ value ranges: V i (x) = ∑ j w ij V ij (x j ). The overall proposal evaluates to a score of zero if any of the issues’ values is outside its range. 2.2 Negotiation Protocol We assume for the negotiation protocol that message delivery is reliable and message delays need not to be considered (because they are presumably short). At a particular point in time each agent has an objective that specifies its intention to buy or sell a specific service. That objective has to be achieved in a certain amount of time, specified by a deadline. Negotiation stops when this deadline is reached. A bilateral negotiation starts after the two parties - the buyer and the seller – meet in the marketplace and match their objectives (i.e., they agree that what the buyer wants to buy is what the seller intends to sell). Once this is achieved, a negotiation thread x b ↔ s becomes active between the two agents. It will stay active while the agents negotiate with each other. The agents will then exchange a sequence of proposals and counter-proposals. When receiving a proposal, an agent will generate a counter-proposal. Both - the received proposal and the generated counter-proposal - will be evaluated using the scoring function described above, and the agent will answer with one of three possible ways:  withdraw from negotiation if the deadline was reached, or if a deal was made with some other agent;  accept the proposal received, if it scores higher than the one generated;  otherwise, send the generated proposal. When an agent b receives an accept message from agent a, it will respond with a deal confirmation or rejection. Since there can be virtually any number of agents in the marketplace, this solves the problem that could rise if an agent receives two simultaneous accept messages from two different agents (we are assuming that the agent’s objective only admits trading one unit of a service at a time). Therefore, if agent b did not commit with any other agent, it will close the deal with agent a, the sender of the accept message. This agent will wait until it gets an answer from agent b. A deadlock problem could rise if a group of agents was waiting for deal confirmations in a closed loop configuration. We address this problem by making agent a, which is expecting a deal confirmation, withdraw any other negotiations and reject any deal with any other agent. This means that eventually it will loose potential deals with other agents, if it receives a rejection from agent b. Since we are assuming short message delays, the problem of lost deals is not likely to occur often, and we ignore it. 2.3 SMACE SMACE allows users to create buyer and seller agents that negotiate under the model and protocol described above. The system was implemented with the JDK1.1.4 API [9], and uses the JATLite [8] package to easily build agents that exchange KQML [10] messages. The agents communicate with each other in the MarketPlace, which is an enhanced JATLite router, facilitating the message routing between the agents and working as an information centre for the agents to announce themselves and search for contacts. The SMACE API consists of three layers built on top of the JATLite packages. These layers also consist of packages, and using the SMACE system can take place at any of them:  Infrastructure – this layer consists of two fundamental parts:  MarketAgent: a template for the creation of market agents. It already has implemented the model of negotiation and its associated protocol. The only task left to the user starting in this layer is providing his own negotiation tactics;  MarketPlace: the application that represents the marketplace, as a space where the agents meet and trade. It includes message routing and agent brokering facilities.  Plug&Trade – this layer includes predefined market agents that can also be seen as examples of how an agent can be built using the MarketAgent template:  MultipleTacticAgent (MTA): a market agent that is able to use a weighted combination of three tactics, one from each of the tactic families described in the next section, to generate its negotiation proposals.  AdaptiveBehaviourAgent (ABA): a market agent that is able to weight the several tactics that it is using in an adaptive way, using Reinforcement Learning techniques.  UserInterface – this layer consists of an application that provides both an HTML user interface for the creation and monitoring of Plug&Trade market agents operation and their persistence. While accepting agents from anywhere to enter the marketplace and trade (provided that they use the same negotiation protocol), SMACE allows the user to launch predefined agents (both of MTA and ABA types) by adjusting its parameters. In order to do so, one can use the SMACE user interface. Through this interface the agents’ activities can also be monitored and its parameters setting can be changed as well. Furthermore, the user may create his own agent, with his own tactics, in any programming language or platform he wishes. The SMACE API Infrastructure package assists agent building in Java. This package allows the user not to worry about communication and negotiation protocol details, spending his efforts on building his own negotiation strategy, that is to say, the agent’s deliberative knowledge. 2.3.1 Agent Matching As mentioned before, market agents contact the MarketPlace to search for agents that have complementary objectives, i.e., objectives including opposite agents’ intentions over the same service. To facilitate the matching of services, these ones are described using what we call descriptive issues, i.e., descriptor/value pairs that all together define the object of negotiation. Then, values for the same descriptive issues for different objectives are compared, and if the agents agree that they are “talking” about the same service they will negotiate over it. The SMACE system can be easily configured to specify the descriptive issues that market agents will use to describe their own services. 2.3.2 Negotiation Issues In order to negotiate properly, besides using the same communication and negotiation protocols, market agents should agree in what issues the negotiation will be about. The SMACE system can be easily configured to consider any number of negotiation issues. All the market agents created in the system will then use the same set of issues. These issues are all considered as uniform, in the sense that, for the market agents, they do not have a semantic attached. Therefore, each market agent will define a weight, a range of acceptable values and a scoring function for each one of the used issues. Opposite intentions (buying and selling) usually imply somehow contrasting scoring functions, e.g., the scoring function for the issue price is decreasing for buyers and increasing for sellers as the price increases. 3 Tactics and Strategies One of the main aims of our work is to compare the performance of agents using strategies based on dynamic adaptive behaviours with those based on more conventional and less dynamic, or even static, behaviours. The goal of negotiation is maximising the utility gained in a transaction, and in order to do so the focus is on how to prepare appropriate proposals as well as counterproposals. The predefined SMACE market agents use a specific tactic or a combination of several tactics to generate proposals. We focused on tactics that we adopted from [2]:  Time-dependent tactics: agents vary their proposals as the deadline approaches. These tactics use a function depending on time that can be parameterised.  Resource-dependent tactics: agents vary their proposals based on the quantity of available resources. These tactics are similar to the time-dependent ones, except that the domain of the function used is the quantity of a resource other than time. This is done either by making the deadline dynamic or by making the function depend on an estimation of the amount of the resource.  Behaviour-dependent tactics: agents try to imitate the behaviour of their opponents in some degree. Different types of imitation can be performed, based on the opponent’s negotiation policy over a sequence of his proposals: proportional imitation, absolute imitation and averaged proportional imitation. 3.1 Time-dependent Tactics Time-dependent tactics vary the proposals as the deadline approaches. An agent a has to find a deal until t amax . A proposal x for issue j from agent a to agent b at time t, 0 ≤ t ≤ t amax , can be calculated as follows:      −α−+ −α+ = →increasing is if ,minmax1min decreasing is if ,minmaxmin a j V) a j a j (t))( a j ( a j a j V) a j a j (t)( a j a j [j] tba x (1) where V aj is the scoring function whose gradient reflects the agent’s intention (as referred in subsection 2.3.2). Any α aj (t) function defining the time-dependent behaviour must satisfy these constraints: 0 ≤ α aj (t) ≤ 1 (offers are inside the range); α aj (0) = κ aj ( κ aj adjusts the initial value at initial time); α aj (t amax ) = 1 (the reservation value – the smallest result of the scoring function V aj – will be offered at the deadline). In order to satisfy these constraints two classes of functions are presented:  Polynomial: β κκα 1 ) max ) max ,min( )(1()( t tt a j a j t a j−+= (2)  Exponential: a j ttt et a j κ β α ln) max ) max ,min( 1( )( − = (3) The parameter β ∈ ℜ + is used to adjust the convexity degree of the curve, allowing the creation of an infinite number of possible tactics. For values of β < 1 the behaviour of both classes of functions can be described as boulware, i.e., concessions are made close to the deadline, otherwise the proposals are only slightly changed. With β > 1 the behaviour is called conceder. An agent prepared like this urges to make a deal and reaches its reservation value quickly. 3.2 Resource-dependent Tactics Resource-dependent tactics vary the proposals based on the quantity of a resource available. Boulware behaviour, used in the presence of a large amount of resources, should change to conceder behaviour when resources run short. 3.2.1 Dynamic-deadline Tactics This tactic sub-family varies the agent’s deadline according to the availability of a particular resource. The resource modelled here is the number of agents that are negotiating and the average length of the active negotiation threads. If a selling agent a notices many interested parties for its good then there is no need to urge for an agreement. The set of agents negotiating with agent a at time t is { } active is )( t ai xit a N↔ = (4) A dynamic deadline using the resource described above is 2 )( max ∑↔ = itai x t a N aa t µ (5) where µ a is the time agent a assumes to be needed to negotiate with an opponent and |x ti ↔ a | is the length of the negotiation thread between agent a and agent i. 3.2.2 Resource-estimation Tactics Resource estimation tactics measure the quantity of a resource at a time t. Function α can be used to model this: )( )1()( tresource e a j a j t a j − −+= κκα (6) The function resource is here used to evaluate the amount of available resources at time t. The following examples model  interested parties: )()( t a Ntresource =  interested parties and negotiation threads’ length: ∑↔ = i tai x t a N a tresource 2 )( )( µ  time: ) max ,0max()( tttresource −= 3.3 Behaviour-dependent Tactics Behaviour-dependent tactics try to imitate the behaviour of the agent's opponents up to a certain extent. This can be useful once opponents will not be able to exploit the agent’s strategy. Tactics of this family make counter-proposals influenced by the opponent's former actions. Following there are three different ways of using imitating behaviours, assuming the negotiation thread { nnnnnn t ab t ba t ab t ab t ba t ab xxxxxx →→→→→→ −−+−+−− ,,,...,,,..., 1222122 δδδ } and δ ≥ 1. 3.3.1 Relative Tit-For-Tat These tactics imitate proportionally an opponent's behaviour δ ≥ 1 steps ago. The length of the negotiation thread must be n > 2 δ . The generated counter-proposal is: )max), a j min[j], 1 [j] 22 [j] 2 min(max([j] 1a j n t ba x n t ab x n t ab x n t ba x− → +− → − → = + → δ δ (7) The counter-proposal generated is calculated with the last proposal ( [j] n t b a x1− → ) and the proportional evolution of two consecutive proposals from the opponent ( [j] n t a b x δ 2− → and [j] n t a b x22 +− → δ ). 3.3.2 Random Absolute Tit-For-Tat These tactics imitate in absolute terms the opponent’s behaviour. They require the existence of a negotiation thread length of n > 2 δ . The resulting counter-proposal is: )max), a j minR(M), s (-1)[j]) 22 -[j] 2 ([j] 1 min(max([j] 1a j n t ab x n t ab x n t ba x n t ba x+ +− → − → + − → = + → δδ (8) where      =increaing,1 decreaing,0 a j V a j V s Parameter R(M) provides a way to overcome function’s local minima. The function R(M) returns a random integer in the space [0, M], where M is the threshold of imitative behaviour. 3.3.3 Averaged Tit-For-Tat These tactics imitate proportionally by calculating the average evolution of a certain number of proposals to the last proposal. The parameter γ refers to the number of past proposals that are considered. The counter-proposal obtained is: )max), a j min[j], 1 [j] [j] 2 min(max([j] 1a j n t ba x n tab x n t ab x n t ba x− → → − → = + → γ (9) for γ 2 > n. The behaviour of averaged Tit-For-Tat when choosing γ = 1 is similar to relative Tit-For-Tat with δ = 1. 3.4 User-defined Strategies Once an agent is created and correctly initiated, it can be activated in order to contact the marketplace, thus starting a new episode in its life. Within an episode, the objective can not be changed. The episode ends when the agent is deactivated. As defined in section 2.1, a strategy can be realised as the way weighted combinations of the former exposed tactics are selected. An agent’s strategy determines which combination of tactics should be used at any particular instant within an episode. The simplest strategy is to use the same combination at any time in that episode. The SMACE UserInterface allows the user to create a MTA, which combines three different tactics – one from each family described before. The sub-tactics are selected by fixing the parameters in the corresponding tactic family. Along with these parameters, the weight combination remains the same, unless the user explicitly provides different values for it. This means that a fixed weighted combination of tactics is always in use. The user can interact with the UserInterface to observe agent actions and change its parameters any time he wants, implementing by this way his own strategy. In order to make it possible to design and include new agent’s learning capabilities or for the user to reuse a successful agent, MarketAgents do not terminate after an