Abstract: Automated negotiation is a key form of communication in systems composed of multiple autonomous agents. One of these multi-agent environments could be e-commerce contexts in which agents participate in the trade instead of their owners and start a bargaining process. Hence, design and implementation of a scientific agent-based bargaining mechanism (based on negotiation) for such contexts is offered in this study. This bargaining mechanism which can decrease the negotiation time in specific situation, in effect, works out based on concession rate principal. Using this mechanism, not only negotiation time will be decreased, but also the gained utility will be increased (if specific criteria are satisfied). These aims are achievable using competitive-collaborative nature of suggested method. Collaborative nature results in agents to help each other to decrease negotiation time. Competitive nature also results in agents’ hard efforts to achieve higher personal utility and avoid utility loss.
INTRODUCTION
Nowadays electronic commerce as one of the most important ways of trading between sellers and buyers is field of attention. The reason is that placing online orders, making payments electronically and finding information about the products and the vendors have become much easier and faster using this technique. This has caused the online trading mechanism to be a popular method of trading (Mudgal and Vassileva, 2000). Forrester Research estimates that online retail sales were at about 600$ million USD in 1996, will exceed 2$ billion USD in 1997 and will reach 17$ billion USD by 2001 (Guttman and Maes, 1998).
Despite all the advantages that e-commerce has brought, humans are still involved in most of the important processes of business; for example, in making decisions in all phases of buying and selling which is a hard and time-consuming process. Therefore, nowadays autonomous agents are applied to handle the task (Sandholm, 2000). An artificial agent is an encapsulated computer system that is situated in some environment and that is capable of flexible, autonomous action in that environment in order to meet its design objectives (Jennings, 2001; He and Jenning, 2004); it is predictable that in e-commerce contexts this objective is furtherance of user’s interests and achieving maximum utility for related user (which is accessible through self-interested nature of agents) (Binmore and Vulkan, 1999). Some simple search agents that involve in bargaining and negotiating on behalf of human can already be found on the internet (like BargainFinder and ShopBot) and others are being developed by Binmore and Vulkan (1999). However, whether e-commerce trades are done directly by people or indirectly and using autonomous agents, negotiation-a key form of interaction in multi-agent systems is an essential part of all trades (Maes et al., 1999). The aim of such interactions is to reach agreement through an iterative process of making offers and resolving probable conflicts in agents’ preferences (Faratin et al., 2000; Munroe et al., 2004; Meyer et al., 2004).
ESSENCE OF NEGOTIATION
Concept of negotiation was discussed in the introduction section. However, to realize negotiation’s worth in multi-agent communication, we will consider a sample scenario here.
An important mode of negotiation is concessionary mode in which agents are required to weaken their demands in order to accommodate the demands of others. If the demands of two agents conflict, each is required to weaken its demands, by dropping some, in order to come to an agreement (Meyer et al., 2004).
Consider Fig. 1 in which a seller and buyer are going to negotiate about price of an item. In Fig. 1, horizontal and vertical axis show item’s price and round of negotiation. Red and blue lines also show offered prices by seller and buyer and arrows show direction of changes by time. Clearly, main purpose of seller and buyer is receiving more money and paying less money, respectively. Hence, there is a conflict in agents’ preferences in this scenario and they should negotiate and bargain about this issue (price), repeatedly, till the time agents’ offers get closer and agreement occurs.
| Fig. 1: | Bargaining about item's price |
Note: Each buyer has a maximum afford that will never accept to pay more than this value for item. Seller also will never accept to sell the item less than its real price (cost). However, first offer of seller may be more or less than buyer’s maximum afford and its cost may also be greater or less than first offer of buyer (dashed lines); since agents are not aware of each other information. However, seeking for agreement point can take place while offered price of buyer agent do not overrun its own maximum afford and offered price of seller agent do not fall below (outlay) its own cost. Additionally, negotiation will end (either successfully or unsuccessfully) as soon as one of the agents reaches its deadline.
ONE-ISSUE AND MULTI-ISSUE NEGOTIATION AND OPTIMAL AGENDA
How the negotiation can solve probable conflicts was discussed earlier. However, each negotiation or bargaining process can have different forms. The simplest form of negotiation involves two agents (seller and buyer) and a single-issue; for example consider sample scenario of seller and buyer who negotiate about price. To begin, two agents are likely to differ on the price at which they believe the trade should take place, but through a process of joint decision-making they either arrive at a price that is mutually acceptable or they fail to reach an agreement (Fatima et al., 2006).
However, in most bilateral negotiations, the parties involved need to settle more than one issue. For example, agents may need to come to agreements about objects/services that are characterized by issues such as price, delivery time, guarantee, quality, reliability, timings, penalties, terms and conditions and so on (Jennings et al., 2001). For such multi-issue negotiations, the outcome also depends on two additional factors (Fatima et al., 2004; Wooldridge et al., 2004):
| • | Negotiation procedure: Clarifies the issues to be negotiated as a package simultaneously, or separately and in different times |
| • | Agenda: Identifies the set of issues that are under negotiation (we call it main agenda sometimes) |
There is a common question among different researches on agenda which refers to defining the most beneficial issues for each agent. In other words, it evaluates what issues provide more utility for each agent and locate in its’ optimal agenda? However, what is an optimal agenda and how it will be used? Each participating agent in the negotiation process owns an optimal agenda which is a subset of main agenda and consists of the issues that are beneficial for that agent (Wooldridge et al., 2004). It means although different issues may attend the negotiation process (available in main agenda), but all of them may not be beneficial for both agents. Based on this research, the participating agents in a negotiation may have or have not a zone of agreement for each issue in the main agenda.
According to Wooldridge et al. (2004), the optimal agendas for two negotiating agents α and ά, in situation where two issues B and C are under negotiation, are being shown by Aα and Aά symbols, respectively (α and ά are two agents from two different types: seller and buyer). As a result of existence of two candidate issues for negotiation (B and C), four negotiation scenarios are possible:
S1: If both issues have a zone of agreement (both issues are beneficial for both agents), optimal agendas of agents will be as follows:
Aá = AÜ = {B, C} |
S2: If only issue B has a zone of agreement (just issue B is beneficial for both agents), two cases will be possible:
| • | If issue C has positive utility for none of the agents, optimal agendas will be as follows: |
Aα = Aά = {B} |
| • | If issue C has positive utility for one of the agents, optimal agendas will be in one of these two forms: |
Aα = {B, C}, Aά = {B} Aα = {B}, Aά = {B, C} |
S3: Only issue C has a zone of agreement (similar to scenario S2).
S4: If neither issue B nor issue C has a zone of agreement, two forms of optimal agendas will be possible:
Aα = Aά = {A, B} Aα = Aά = Ø |
PROBLEMS AND MOTIVATION
Here, we are going to introduce two main problems with two preceding sections and our motivation towards suggested method.
First problem: As we are informed, due to the distributed nature of multi-agent problems, the agents, at best, possess only partial knowledge about other agents’ preferences and generally have incomplete information of each other. As an example, they are completely unaware of each other reservation values (e.g., maximum afford and cost) or deadlines:
Consider Fig. 1 in which seller agent is unaware of buyer‘s maximum afford and buyer agent is unaware of seller’s cost; because, for example, if the seller reveals the real cost of the item (e.g., 25$) to buyer, the buyer will never accept buying the item with specified price (e.g., 125$).
Moreover, agents are unaware of each others’ deadlines (Fig. 1). Hence, they should try to reach agreement as fast as possible (before their deadlines reach and negotiation time ends). Reduction of agents’ utilities by time is another important reason for agents’ hard efforts to reach quicker agreement (hypothesis).
Second problem: Except for the issues that both sides are eager to negotiate about (such as issue B in part b of scenario S2 in the earlier section), there may exist some issues that are just beneficial for one side of a trade (for instance, issue C in part b of scenario S2 is located in optimal agenda of one side of a negotiation and thus is beneficial for just that side). This means the other side is not eager to negotiate about this issue (it brings negative utility for the other agent). We call such issues peripheral issues of a negotiation. However, as we know, each agent prefers to negotiate about all the issues that are located in its optimal agenda and are beneficial for it. Hence, what will happen if an agent insists on negotiating about peripheral issues of its’ own? In other words, what would the reaction of other side be? Sensibly, other side will refuse negotiating about such issues (because of utility loss). This matter not only forces lots of limitations, but also it may cause never the negotiation starts; since two sides cannot reach agreement about peripheral issues.
Motivation: Considering the above problems, we are going to present a negotiation model in which an agent will accept negotiating about peripheral issues of its opponent, if specific criteria get satisfied. These criteria act in a way that not only the agents will never face utility loss, but also they will sometimes receive higher utilities. Furthermore, as will be illustrated, this model can reduce the negotiation time and can work in incomplete information settings.
Note: The proposed model of this study can work only in specific situation (when particular criteria are being satisfied). In other occasions, the model works similar to ordinary models of negotiation.
HYPOTHESIS
Hypothesis 1: It was discussed that most remarkable feature of proposed model would be the save it can make in time. Therefore, the first hypothesis could be as follow:
H1: There is a limitation in time or unawareness of other agent’s deadlines (incomplete information). As a result, reaching quicker agreement is essential.
Hypothesis 2: As it is shown in Fig. 2 for buyer, agents may have three behaviors over time (Fatima et al., 2004):
| • | Boulware (B): For this tactic the initial offer is maintained till time is almost exhausted, when the agent concedes up to its reservation value |
| • | Conceder (C): For this tactic the agent goes to its reservation value very quickly and maintains the same offer till the deadline. Based on concession rate principal, agents’ utilities usually decreases as the time passes and in fact its diagram has a descending shape; concession rate diagram usually has a high negative gradient |
| • | Linear (L): Price is increased linearly (e.g., by 1 at each round) |
| Fig. 2: | Negotiation decision functions for buyer |
This study’s main concentration is on trading between agents who appear in the role of conceder agents and decrease their utility by a factor of time. It is apparent that main reason of our motivation towards this matter is the save in time which can be achieved through this operation. Therefore, based on concession rate principal the following hypothesis is considered:
H2: It is assumed that all participating agents in the trade are conceder. As a result, if agent a gives offers Si at time t and Si+1 at time t+1, with maximum probability the utility gained through offer Si will be equal to or more than Si+1 (Fig. 2).
If U = Utility function, Agent = a ≤ Ua(Si)≥Ua(Si+1) |
Hypothesis 3: Third hypothesis would be first, negotiating about common issues which are beneficial for both agents and then, entering other issues (peripheral issues) to the negotiation process under special conditions. Again it is realizable that main reason of this matter could be time limitation or having incomplete knowledge of another agent’s deadlines. Therefore, it will be logical that firstly negotiation takes place base on issues which are acceptable for both agents.
H3: Negotiation process mainly takes place base on common issues.
Hypothesis 4: Since based on H3, negotiation process takes place mainly around common issues, the main
criteria for selecting a seller agent is number of issues which it has in common with buyer agent. Therefore, fourth hypothesis is as follows:
H4: Buyer agent selects the seller agent (for negotiation and trading) which has more issues in common with it.
DESIGN AND IMPLEMENTATION OF PROPOSED MODEL
Proposed model of this study consists of five main steps which will be discussed in details.
Step 1: In this step, first, all the available sellers (or buyers) will insert their information in their storages and then will publish it (Fig. 3). Insertion of information may be initialized by registering the services in to agent’s catalogue or by inserting the information into local databases of agent (second technique is being applied in this study). Then, local information will be saved partially in a global meta-database which can be used by agents to find proper opponent to trade with.
Figure 4 shows a sample table of a seller’s local database (seller2) designed using Microsoft SQL server management studio. This table consists of the information such as item’s name, item’s description, seller’s interested issues (such as price, color and delivery type) and minimum utility which is acceptable for each issue (such as min-price, min-color and min-delivery type in Fig. 4).
As discussed earlier, information such as cost of the item (equivalent to min-price in Fig. 4), min-color and min-delivery type should be hidden to buyers; it is realizable that main reason of such discretion could be sellers’ policies and their interest to hide the minimum utility which is acceptable for them in regard to each issue.
| Fig. 3: | Negotiation model |
| Fig. 4: | Sample table of information for seller2 |
Therefore, such secret information will not be published in the global meta-database. The generic information which has been saved in the global meta-database may be something like what is shown in Fig. 5 (the field seller ID in Fig. 5 shows the sellers, who have registered their services in the global meta-database). As depicted, information related to minimum utility has not been inserted in global meta-data base.
Step 2: In this phase, each registered buyer may receive some notifications (advertisements) about updated services of each seller (shown by inform in Fig. 3). Furthermore, buyer may start searching for the best opponent (seller) to negotiate with. This search will be accomplished using the information stored in the global meta-database. Figure 3 shows a buyer’s searching process for keyword camera. According to Fig. 5, three sellers with IDs 1, 2 and 3 offer service camera. Hence, search results (three sellers and their issues) for keyword camera will be shown to the buyer as it is shown in Fig. 6a. Showing each seller’s issues is because of the fact that buyer agent attempts to select the best seller to negotiate with. As a result, it will choose the seller that has more issues in common with it (hypothesis H4). Figure 6b (resulted by scrolling the window’s bar down) shows that seller2 is the best seller among three candidate sellers; comparing to other sellers, buyer and seller2 have more issues in common with each other.
Based on Fig. 6, the concerned issues of buyer and seller2 are as follows:
Buyer issues ={Price, Guarantee, Quality, Delivery type, Delivery date} |
Seller2 issues = {Price, Guarantee, Delivery type} |
Note: Figure 6b shows that common issues of buyer and seller2 (intersection of two above sets) in above scenario are price, guarantee and delivery type. In addition, quality and delivery date are peripheral issues of buyer (exist in buyer set and do not exist in seller2 set). Hence, this example can be classified in part b of scenario S2, which is described earlier, in which just one of the agents own peripheral issues. As a result, this sample scenario has some of the problems discussed in problem section and we will try to solve them using our suggested method in step 3).
Step 3: After extracting the common and peripheral issues of negotiation in the second step, in this phase and according to H3, negotiation takes place about a common issue (such as price).
| Fig. 6: | Search results for keyword camera |
| Fig. 7: | Offered prices of agents in regard to variable t at each round of negotiation |
However, based on hypothesis H1, main objective of proposed model is reaching quicker agreement and based on hypothesis H2 this model is based on concession rate principal. Hence, utility function should be in a way that agents’ offered prices (utilities) decreases by a factor of time (remember Fig. 1 in which the more the agents decrease their utility, the more the negotiation time will decrease and quicker the agreement will happen) and agents reach quicker agreement (see our sample Ub(R) and Us(R)).
However, the question is that what will happen if an agent starts bargaining with a price that exceeds opponent’s reservation price (cost or maximum afford)? In this case, the opponent will not accept bargaining at all and will repeat its previous offer.
For instance, imagine that in the discussed scenario, cost (defined by seller) is equal to 25$ and maximum afford of buyer is equal to 130$. Hence, if buyer offers 20$ for item, the seller will not accept giving any discount to the buyer (seller will repeat its earlier offer 125 in the next round (time) of negotiation (Fig. 7).
Thus, instead of negotiation time (R), we will define the utility functions as a factor of a variable named t (each agent has a separate variable t), which varies only if offered prices do not exceed agents’ boundaries (Fig. 7) In Fig. 7, it is imagined that each offer and its counter offer are given by buyer and seller in one round or time of negotiation).
Therefore, if (Ub(R)) and (Us(R)) are utility functions of buyer and seller at each round (time) of negotiation, agents will vary their utilities in round R of negotiation if their opponent’s offered price in the previous round did not exceed reservation values.
The code which should be satisfied to increase variable t values and so decrease the utility by time is as follows:
In the above codes, variable R shows round or time of the negotiation; thus, as long as the negotiation time is remained, the above condition (code) will be checked.
However, how the offered prices by two sides can be computed? In other words, what is the relation between
the gained utility and offered prices? The offered price of buyer and seller at each round of negotiation can be computed using Eq. 1 and 2, respectively.
| (1) |
| (2) |
Based on Eq. 1 the price offered by buyer at round R is difference of maximum afford and utility of buyer at round R; e.g., if the maximum money (maximum afford) which buyer agent accepts to pay for item in allover the negotiation process is 130 and it just pays 20 dollar at the first round of negotiation, the utility will be equal to 110$. Similarly, if the cost of item is 25 and seller tries to sell it for 125$ at the first round of negotiation, the gained utility would be equal to 100. Hence, Eq. 2 is also applicable for computing the price which is offered by seller.
Here, we will demonstrate this situation for our sample scenario in practice:
To compute Ub(1), at first, buyer code should be checked. Since, offered prices(0) in buyer code does not exist (first round of negotiation is R = 1), the condition is not satisfied and R will remain equal to t (t = R = 1). Therefore, Ub(1) will be equal to 110 (Fig. 8b) and offered priceb(1) will be equal to 20 (130-110 = 20 (Fig. 7, 8a). In the same way, Us(1) will be equal to 100 and offered prices(1) will be equal to 125. Ub(2) also can be computed in the same way. Since in the buyer code Offered prices(1) is less than maximum afford (125 is less than 130), t value for buyer agent will be increased (R = t = 2). Therefore, Ub(2) will be equal to 106 and offered priceb(t) would be equal to 24. However, the condition in the seller code is not satisfied while computing Us(2); since Offered priceb(1) is not greater than cost (20 is not greater than 25). Hence, t values for seller agent will remain equal to one, Us(2) will remain equal to 100 and offered prices (2) will remain equal to 125. Utilities and offered prices of agents in other rounds of negotiation can be computed in the same way. Figure 8b shows agents’ utilities in different rounds of negotiation in the discussed scenario. Figure 7 and 8a also show the offered prices of agents by time (round).
End of the negotiation: Sending offers and counter-offers can repeatedly happen till agents reach end of their deadlines or their offers exceed their reservation price (see essence of negotiation).
If the offered price of opponent exceed the reservation value of agent, the agent will repeat its’ previous offer and does not vary its offered price (see seller and buyer codes). However, if the next offer of agent its own exceed the reservation values, the negotiation will end unsuccessfully.
| Fig. 8: | Offered prices and utilities of agents in sample scenario |
Therefore, Eq. 3 and 4 should be tested permanently during negotiation process.
| (3) |
| (4) |
On the other hand, if the utility that each agent receives from offer of its opponent at each round of negotiation is greater than the utility that it may receive from its own offer at next round of negotiation, that agent will accept the opponent’s offer and will send an accept message to the opponent. The reason is that agents always look for higher utilities and also concession rate principal is satisfied in this model (H2). Hence, if the utility is greater than next round’s utility, it will also be greater than all the next rounds’ utilities. As an example, although based on Fig. 7 and 8a agents do not reach agreement in 5th round of negotiation, but buyer agent accepts the offer of seller in this round (80) because it is better than buyer’s own next offer at round 6 (110). The related codes for buyer and seller agents to accept finishing the negotiation are as follows:
BuyerIf (Ub(offered prices(R))>Ub(R+1)){buyerMSG:=accept;Agreement:=offered prices(R); } |
If (Us(offered priceb(R))>Us(R+1)){sellerMSG:=accept;Agreement:=offered priceb(R); } |
Although, in our sample scenario buyer agent accepts seller’s offer in the fifth round of negotiation, but negotiation finally will end in the 6th round of negotiation (because accept message should be sent to inform the other side). Figure 8a shows how the agents’ offers get closer in the fifth round of negotiation and how they finally pass each others’ boundaries (reach agreement) in the sixth round; Fig. 8a shows variation of offered price in each round of negotiation. Figure 8b also shows how much agents’ utilities will be in each round of negotiation and how it will decrease as the time passes (concession rate principal- hypothesis H2); Fig. 8b shows variation of Ub(R) and Us(R) in each round of negotiation.
Step 4: Based on hypothesis H3, the negotiation process mainly occurs around common issues. However, as discussed in the problem section, the main motivation of this study is suggesting a negotiation method where peripheral issues are also involved in the negotiation (such as the part b of scenario S2 or scenario S4-or such as sample scenario in our five-step architecture). Entrance of peripheral issues to proposed negotiation process occurs only if specific criteria (criteria 1 and 2) are satisfied.
Checking of criterion 1 and its related argument would be as follows:
Criterion 1If (|Losss(offered priceb(R))|< Uperipheral, s(R)) OR(|Lossb(offered prices(R))|< Uperipheral, b(R)) {Send argument;} |
Argument
I will accept your offer about common issue, if you accept my offer about
my peripheral issue (or issues).
According to above codes, if criterion 1 is satisfied, an argument will be sent to the opponent agent. Based on this argument, the agent will accept opponent’s offer about common issue, if the opponent also accepts the agent’s offer about its peripheral issues (Thus peripheral issues can also enter to the negotiation). However, the main condition (criterion) for sending this argument is that the agent totally does not face utility loss. In other words, the utility loss (the loss that the agent receives because of accepting the opponent’s offer about common issue- losss(offered priceb(R)) or losss(offered priceb(R))) should be compensated by utility of peripheral issues (Uperipheral, s(R) or Uperipheral, b(R)). In this case, the agent will insist on entrance of its peripheral issues to the negotiation and will send the argument. If the opponent also accepts the argument (criterion 2), peripheral issues of agent can enter in to the negotiation process.
Note: Utility loss usually is a negative value. Hence, we have used absolute value for it in criterion 1 (|Losss(offered priceb(R))| and |Lossb(offered prices(R))|).
Note: In criterion 1, just compensating the utility loss in round R (e.g., Uperipheral, s(R) greater than losss(offered priceb(R)) ) warranties that agent receives the best possible utility in all over the negotiation. Since, based on concession rate principal, the total gained utility in round R would be greater than round R+1 (specially that the probable loss in round R is being compensated by peripheral issues’ utility).
Figure 9 shows checking of criterion 1 during negotiation process. Based on this figure, criterion1 will be checked permanently by agents, when they receive an offer about common issue from their opponent. As soon as the criterion gets satisfied, the argument will be sent by next message.
Here, we will analyze each statement in criterion 1:
| • | Losss(offered priceb(R)), lossb(offered prices(R)) |
Offered prices by seller and buyer and their loss at each round of negotiation are shown in Table 1 (step 3). In such situation, for example, if buyer agent accepts seller’s offer about common issue at each round of negotiation, its utility loss will be equal to the amount of money it has to pay more than usual case (more than the time its own offer offered priceb(R) is accepted by opponent at that round). Hence, the utility losses of two agents are equal and can be computed using Eq. 5 (we simply name it loss). Computed results for our sample scenario are shown in Table 1.
| Fig. 9: | Step 4 and checking criterion 1 during negotiation process |
| Table 1: | Offered prices and utility loss of agents |
| Table 2: | Utilities that buyer agent gains from its peripheral issues |
| (5) |
| • | Uperipheral, s(R), Uperipheral, b(R) |
Second values that should be computed (for analyzing criterion 1), are utilities of peripheral issues. For the discussed sample, we imagine that buyer agent (b) has two peripheral issues, guarantee and delivery date (step 2). We call these peripheral issues P1 and P2 (P is abbreviation for peripheral issue). The utility functions of these issues are as follows (codes similar to step 3 should be checked-these codes will be used to compute Up1,b(R) and Up2,b(R) based on t):
Utilities which buyer agent gains from negotiating about peripheral issues P1, P2 or both of them, at each round of negotiation (based on above relations) are shown in Table 2. According to Fig. 2, since agents are conceder and maintains the same offer till the deadline, after round four Up1,b(t) and Up2,b(t) will remain equal to 23 and 8, respectively.
| • | Loss< Uperipheral, s(R), Loss< Uperipheral, b(R) |
As last, it should be checked if the loss can be compensated by utility of peripheral issues.
Table 3 shows that P1 and P2 cannot compensate the loss till 5th round of negotiation (this matter is also shown in Fig. 10. The utility of peripheral issues is less than loss in both shapes till 5th round). However, when discussed together they can compensate this loss from first round of negotiation (Table 3, Fig. 11). Therefore, if utilities of both peripheral issues are considered simultaneously, criterion 1 will be satisfied by buyer sooner. Then, discussed argument will be sent to seller.
| Table 3: | Analyzing if peripheral issues’ utilities can compensate probable utility losses |
| Fig. 10: | Loss and utilities of agents from: (a) P1 and (b) P2 |
| Fig. 11: | Loss and utilities of agents from: P1 and P2 together |
Note: In Fig. 10a, b and 11 after 4th round of negotiation, the utility that buyer agent gains from its peripheral issues will remain consistent. Since, based on Fig. 2, conceder agents keep their last offer till their deadlines (loss after round 5 also will remain consistent because of same reason).
Step 5: As discussed, in our proposed model, at first, criterion 1 should be checked. As soon as it gets satisfied by one of the agents, the opponent agent should start checking criterion 2. According to criterion 2, the opponent agent should be assured that the loss came from acceptance of argument (step 4) about peripheral issues does not totally reduce its utility comparing to ordinary cases. It means, although based on step 4, opponent will receive more utility from common issue, but it will lose some of this utility because of argument about entrance of other side’s peripheral issues to the negotiation. Hence, it should be assured that the summation of these two values is more than the case that its next offer is being accepted by other agent. For instance, in step 4 of our sample scenario, buyer agent satisfied criteria 1 and sent an argument about its peripheral issues to seller agent. According to Fig. 9, seller agent receives this argument in the next round of negotiation (Fig. 9 shows how criterion1 will be checked permanently up to the time one of the agents accept the argument sent by other side). In this round, seller also analyzes criterion 2 and sends its next offer. Therefore, if we call the new round R+1, criterion 2 for seller will be as follows:
If (Losss(Uperipheral, b(R))+Us(R)>
Us(R+1)) then Accept |
Based on the above code, the only condition of seller for accepting the sent argument by buyer is that the total utility of this matter is the best case in all over the negotiation (based on concession rate principal if this summation is greater than Us(R+1), it also would be greater than all the future utilities of common issues in the next round). The criterion 2 for buyer agent also can be computed in the same way. If buyer is supposed to check criterion 2, its code would be as follows:
If (Lossb(Uperipheral, s(R))+Ub(R)> Ub(R+1)) then Accept |
As a result, criterion 2, totally (for seller or buyer) will be as follows:
Criterion 2
If (Losss(Uperipheral, b(R))+Us(R)>
Us(R+1)) OR |
Again consider our sample scenario. As discussed in step 4, criterion 1 is satisfied for buyer agent from first rounds of negotiation, if both of its peripheral issues (P1 and P2) enter the negotiation. Hence, if criterion 2 also gets satisfied by seller agent, the negotiation will converge to agreement and will end successfully. Imagine that the utility loss that seller agent receives from acceptance of buyer’s offer about peripheral issues (Losss(Uperipheral, b(R))) are as shown in Table 4. Clearly, in this case, criterion 2 will get satisfied by seller in the third round of negotiation (round 3: 90+ (-14)>75). Therefore, seller will accept buyer’s offer about peripheral issues (argument) and negotiation will end in the third round of negotiation.
Figure 12 is a modified form of Fig. 9 for our sample scenario. As depicted, in first round of negotiation both agents will send their offers about common issues. Simultaneously, criterion 1 will be checked by both sides. However, just buyer agent can satisfy this criterion (using its peripheral issues P1 and P2). Therefore, besides its usual offer about common issue, it will send an argument about criterion 1 to seller agent in the second round. As a result, based on Table 4 and Fig. 12, seller will start analyzing the argument and checking criterion 2. Nevertheless, it cannot satisfy it (No symbol in Table 4). Thus, seller will send its next offer about common issues.
| Table 4: | Checking criterion 2 in present sample scenario |
| Fig. 12: | Analyzing criterion 1 and criterion 2 in our sample scenario |
| Fig. 13: | Checking criterion 2 in our sample scenario |
Again, buyer agent can satisfy the criterion 1 in this round and will send an argument to seller in the next round of negotiation (round 3). Finally, after checking criterion 2, seller will accept buyer’s argument in the third round of negotiation (Yes symbol in Table 4).
Note: In Table 4, if opponent agent does not accept entrance of both peripheral issues to the negotiation (it does not satisfy criterion 2 in round 3), the negotiation process will continue till fifth round of negotiation in which there is a chance to accept negotiating about one of the peripheral issues.
Figure 13 shows how summation of Us(R) and Loss(Uperipheral, b(R)) is more than Us(R+1) in the third round of negotiation (criterion 2 is satisfied in the third negotiation round); the mentioned summation in the third round is equal to 76 and Us(4) is equal to 75 (Fig. 13). Thus, accept message will be sent in the third round of negotiation and agreement will occur.
Experimental results: The sample scenario of this study showed how the 4th and 5th steps in the five-step architecture can solve some probable problems. As illustrated, in ordinary cases (three first steps) just common issues were under the negotiation and negotiation converged to agreement after 6 rounds of negotiation. However, by adding two other steps to first three steps, not only peripheral issues can enter to the negotiation process, but also the negotiation time will reduce and agreement will occur after three rounds. Additionally, usually agents receive more utilities by applying this method; since based on concession rate principal reaching quicker agreement results in achieving higher utilities.
CONCLUSIONS
Design and implementation of an agent-based bargaining mechanism (based on negotiation) for e-commerce contexts is presented in this study. Experimental results show that the imposed model can reduce negotiation time significantly. In addition, this method not only is applicable for incomplete information settings, but also can help the agents to gain more utilities. This proposed algorithm is in fact a competitive-collaborative method. It is collaborative since each agent helps the other agent to achieve higher utilities and it is competitive since each agent tries to achieve higher personal utility (and avoid utility loss). Hence, this method of bargaining could be beneficial from various aspects.