An Architecture for Multilateral Automated Negotiation: AMAN

DOI : 10.17577/IJERTV3IS100166

Download Full-Text PDF Cite this Publication

Text Only Version

An Architecture for Multilateral Automated Negotiation: AMAN

Madhur Arun Patrikar1 Department of Computer Engineering

Maharashtra Institute of Technology, Pune

Prof. Sheetal Vij1 Department of Computer Engineering Maharashtra Institute of Technology, Pune


Prof. R A. Rane

Department of Computer Engineering Maharashtra Institute of Technology, Pune

Abstract- In E-commerce, number of transactions are increasing day by day in B2B and B2C trade. Online negotiation is possible because of automated negotiation. In this paper, we propose multi-attribute utility function based multilateral automated negotiation system and study some multilateral system with several methods. We have studied fuzzy inference logic based system, multithreading based automated negotiation system, time dependent strategies based system, linear programming based system and genetic algorithm based system and we have compared some methods of automated negotiation. Multilateral negotiation system gives better result to participant than bilateral automated negotiation.

Keyword – Multilateral automated negotiation, multi- attribute utility function, fuzzy logic, multithreading and linear programming based system.


    Automated negotiations have allowed people to online negotiations. An automated negotiation can be doing in two ways: bilateral automated negotiation and multilateral automated negotiation. In bilateral negotiations, two agents negotiate on single or multiple issues on behalf of people. When more than two agents come together to negotiate, with different constraints and preferences, then the process becomes complicated, the complicated process of automated negotiation is referred as multilateral automated negotiation. Many people do not like to traditional negotiation process because they view it as time consuming and complex process as people participation must require till the process is complete. This problem is solved by automated negotiations. It is the best way to solve conflict between two or more persons and to reach on the final agreement. Negotiations are conducted using bidding, bargaining or auctions. Automated negotiations are not easy without interaction of human being and can be done on bilateral or multilateral environment. It is difficult when the behavior of opponent is unknown. Prediction methods are used to identify the behavior of opponents. A prediction method of utility function gives good result to identify the behavior of opponents [4].


    As per Ricardo Buttner, automated negotiation is classified mainly as structure, theoretic foundation and restriction. We are going to focus on for the structure. The Protocols can be classified into three parts, as bilateral, one-sided and double-sided. One-sided and double-sided negotiations are also called as multilateral automated negotiation [7]. The Kasbah model was built on only a single issue as price. The system was built on multiple issues with two agents, but it has not given as much as good result to buyers andsellers

    Fig. 1. A point indicates the utility for both agents of a bid. The red line is the Pareto optimal frontier.

    In bilateral automated negotiation, maximum utility for a single agent can become minimum utility for opponent agent, and therefore the chance of agreement is low. Considering Figure 1, agent A and agent B have limited space to take their decision. This problem is avoided by multilateral automated negotiation. A major challenge in the negotiation using the bilateral protocol is that the agents hide their preferences. So agent does not know which preferences the opponent will prefer. This problem can be partly resolved by building a model of the opponent's preferences by analyzing the negotiation trace [6].

    Susanne Klaus, Karl Kurbel and Iouri Loutchko in 2001, gave overview of game theory based negotiation, multi-attribute utility theory based negotiation and auction based negotiation. As per then paper, there is scoring function problem and user dependent problem in many-to- many multilateral negotiation. For linear scoring function, optimal solution can be found but for non-linear scoring function, the mathematical analysis is very difficult. How to construct the negotiation strategy is not cleared in this

    paper. As per the paper, multilateral negotiation using game theory is very difficult to use. Utility theory can give better result than the game theory [13].

    Sanghyun Park and Sung-Bong Yang have proposed a negotiation agent system based on the incremental learning in order to increase the efficiency of bilateral negotiations and to improve the applicability towards multilateral negotiations. For the system, they also have introduced a framework for multilateral negotiations in an e-marketplace in which the components can dynamically join and disjoin. They proposed an automated negotiation system that can efficiently carry out multilateral negotiations with multi- attributes in pervasive computing environments. The effects of learning ability are investigated with focusing on the reciprocity of participants and on the execution time of negotiation. The issues in relation to the improvement in the incremental learning and the development of delicate protocols for agent interoperability are not included in this system [12].

    Also they developed linear programming based automated negotiation system. They used concept of mediator agent and two bilateral automated negotiation schemes based on linear programming. The experimental results show that the proposed system produces higher joint profits and is faster in reaching agreements on an average under the condition of agreement for reciprocity than a negotiation system based on the trade-off mechanism. [9].

    The multi issue negotiation model with distributed problem solving was presented by P Faratin, C Sierra, N R Jennings and P Buckle. In this, they developed fully autonomous agent who coordinates both agents interaction and handles individual agent also [16].

    Monotonic Concession Protocol for Multilateral Negotiation had been described by Ulle Endriss.It is a deadlock free protocol in which they restricted on the utility function. It is not applicable for all the cases of negotiation [13].

    In multilateral multi issues negotiation protocol, MAS (multi agents system) is used for decision making. They considered complex dependencies between multiple issues by modeling the preferences of the agents with a multi-criteria decision aid tool. [7]. In automated negotiation, cloud can provide security and privacy .It requires low maintenance on the data [3].

    Considering these papers, we can say multilateral automated negotiation gives better result to buyers and suppliers. In multilateral negotiation, we can use desperate or patient coordination strategies. In desperate strategy, if one of the sub agent successes then process is stopped. In that agent want negotiation process to be completed as early as possible and in patient strategy, if one of the sub agents gets success then process will be continued till all agents get success. After completing the process, the score of each agent is checked and among them, the agent who gives more profit is selected. Negotiation protocol is a

    general rule which can be used by anybody in the negotiations. The protocol determines the flow of messages between the negotiationing parties. Request based negotiation protocol and sequential bilateral negotiation protocol are used for bilateral negotiation. Automated mediation, baseline mediation, multiple bilateral, feedback based mediatin and contract net protocol are used for multilateral negotiation. Win-win strategy gives better outcomes to buyer and supplier [2]. Intelligent techniques such as neural networks, genetic programming, fuzzy logic theory and Bayesian theory are used to learn opponents behavior, decision-making and generating offers and fuzzy system, multithreading, game theory, genetic algorithms and linear programming are some of the methods which can be used for multilateral automated negotiations.

  3. MULTI-ATTRIBUTE UTILITY THEORY Utility theory is a systematic approach for

    quantifying an individual's preferences. It is used to rescale

    a numerical value on some measure of interest onto a 0-1 scale with 0 representing the worst preference and 1 the best. MAUT(Multi-attribute utility theory) is one methodology in the broader field of Multi-Criteria Decision Making (MCDM). Multiple-criteria decision-making is a sub-discipline of operations research that explicitly considers multiple criteria in decision-making environments.


    Some e-marketplaces for product and merchant brokering have been designed for helping the consumer to determine what to buy and who to buy the product from according to consumers preferences. Some of consumers preferences can be vague. In this case, the multi-attribute utility theory is normally used to rank the crisp proposals coming from the merchants according to the consumer's vague preferences. In the more general situation of multi- lateral negotiation with many issues and with vague preferences both by buyers and sellers, the same problem should be treated, namely, to rate the offers coming from the negotiation partners according to own vague preferences. we present some elements of the multi- attribute utility theory. We suppose that m participants take part in the negotiation and the negotiation subject can be characterized by n issues, all of them of numerical nature. Let Xi denote the value for issue j (j = 1,…,n) offered to the negotiation participant i (i = 1,m) by another participant at some moment. In general, an interval of values is acceptable by each participant, i.e.,

    Different values from this interval can be of different worth for every negotiation participant. The worth of values of negotiation issues is modeled by scoring functions:

    The bigger the value of a scoring function for a certain value of an issue is, the more suitable is this value for the negotiation participant. In a real negotiation, different negotiation issues are of different importance for every negotiation participant. To model this, we introduce the notion of relative importance that a participant assigns to

    system mediator is used, and mediator uses the issue tradeoffs strategy. Software agent is a piece of code that makes simulation between buyer and supplier and takes decision on behalf of them. Analytic hierarchy process can be used to take the preferences of participants in this system. This model supports many to many multilateral


    each issue under negotiation. Let i

    be the relative

    negotiations. A negotiation specification of the model has

    importance of issue j, j = 1,…,n, for the participant i, i = 1,…,m. For convenience, we assume that the normalization relation is valid:

    Now we suppose that negotiation participant i, i = 1,…,m, is given an offer. Because the negotiation is characterized by n issues, the offer can be represented by a vector

    Using the scoring functions and relative importance of issues under negotiation we can introduce the notion of a general scoring function:

    The exact form of scoring functions depends on a concrete situation. In many cases, linear function can be used to model the utility:

    This situation is the simplest one from the mathematical point of view. If all negotiators use the linear scoring functions, it is possible to compute the optimum value of x giving theoretical value for the best deal. In a real negotiation, however, the final result achieved in the process of negotiation will depend on negotiation strategies, even in the case of linear scoring functions.


    Multilateral negotiation is classified in two ways 1) one sided and 2) double sided. One sided is also called as one-to-many and double sided is also called as many-to- many respectively. Some of the multilateral automated negotiation methods are as follows:

    1. Fuzzy System

      In fuzzy system, requirements and preferences the two effective factors are considered. Requirements may be qualitative or quantitative which assign is given by the participant. Priority is assigned to preferences. In this

      been presented by Bahdor. In that method they have propose FANA (fuzzy system based automated negotiation) architecture as shown in Figure 2.

      Fig. 2. FANA model architecture

      In FANA architecture, they consider two components such as FOM (fuzzy system based offer modifier) and decision maker.FOM is the fuzzy system based offer modifier. Offer in FOM component is modified by supplier, with respective buyers requirement and this passes to decision maker component. After taking input from FOM, decision maker component decides to reject or accept the offer. It makes decision on the basis of supplier and buyers proposal and compute partial score for each issue. For qualities issues, if highest priority of suppliers acceptance value does not exist in buyers acceptance value then zero is assign to partial score. Otherwise partial score is calculated by using formula:

      In the above equation, partial score is computed for buyeri,supplierj, and quantitative issue k. In this equation, AVk denotes set of supplier values assigned to the issuek.Computing partial score for benefit type quantitative issues is as follows:

      For qualitative issues, if the value of the supplier with

      highest priority does not exist in acceptance values of the buyer, zero is assigned to the partial score; otherwise, partial score is computed as follows:

      Where, denotes one of the issue values that it has higher priority from supplierj perspective. The find position function returns the position of the in list of buyers i acceptance values , and length

      is the number of buyersi acceptance values for issue k.

      If a supplier score is higher than threshold value of buyer then negotiation will be terminated or it will require maximum no. of rounds for negotiation to terminate. In negotiation scheme, they have proposed two FIS, one for qualitative and other for quantitative. Qaulaitative issues and quantitative issues are calculated by non-iterative process and iteratively process respectively. Evolution of FIS is calculated by intersection of buyer and suppliers acceptance values. Decision makers require two inputs such as difference of issues and common priorities of issues between buyer and supplier. Difference lies between

      -1 and 1.CP is calculated by geometric mean of buyer and supplier priority. CP lies between 1 and product no. of AVs and AVb.1 is assigned to common priority of issues. The first priority is assigned to that issue which is present on the first position in the accepted value list of k issues. There are 9 rules for qualitative and quantitative requirements as referred in a fuzzy system approach to multilateral automated negotiation in B2C e-commerce . They compared Mamdani and Sugeno FIS and they found that Mandenis result produced more reasonable results than Sugeno. In this system they used the technique of both [1].

    2. Multithreading

      In multilateral automated negotiation using multithreading in this they compromise on game theory, heuristic method and argumentation method. In that coordinator creates thread for each issue and sub issue. All these issues are arranged in hierarchical pattern. They take preference in the form of advertisement and save into the database. According to their condition buyer and supplier are matched on the basis f constrain of unique product id. Utility function is used to generate counter offer. Evaluation of utility function is Umin=non function attribute

      * actual cost. Umax=non functional attribute * Cost with margin. Where, Umin is minimum utility of product, Umax is maximum utility of product, the function attribute are cost of overall. Minimum payoff is summation of Umin and maximum payoff is summation of Umax.

      Considering previous paper, negotiation is started by buyer, initially buyer generates offer for seller then seller inspects the offer and calculates the utility of each issue. After calculating they accept/reject the offer based on their price. If seller rejects offer then they decrease the utility. Therefore new utility is calculated by using product of old utility and F1.

      No . of rounds X penalty

      According to that utility can be varied and new value of penalty is calculated.



      Sum of not accepted Umax Umax Sum of not accepted Umin Umin No .of rounds

      Where x (penalty) => Sum of cost of attribute on which agreement has not been reached of penalty. This penalty is sent to thread on which negotiation is still in progress then accepted offer are temporally stored while issues are rejected. Negotiation process will go on until the time limit of counter or offer will be accepted. Time limit counter will be updated as per round. Parallel process will be done in multithreading based negotiation [7].

    3. Time-dependent strategy

      Time-dependent, resource-dependent and behavior- dependent are tactics used by agent .here we are describing time dependent strategy based negotiation .

      The time-dependent function is

      . (1)

      Where f1 and f2 are user defined value of the negotiation issue.

      . (2)

      Where =>time the agent was initialized by the user. =>time the agent has to complete the


      Is a parameter that determines how the agent changed the value of issue according to the time. Mediator is a coordinator between agents, who handles and manages communication between agents. In time- dependent multilateral negotiation system, they use bilateral negotiation protocol. Negotiation tactics are used to generate offer and the offer will be accepted or rejected on the basis of scoring function according to agents preferences, goals, issues etc. First they take preferences from agents then map buyer and supplier agents. After mapping they give rank to those agents. Suppose, n1, n2, are the number of agents have ranks like n1>n2>n3> Supplier agents send total value of offers at particular time t=ti, i=0, 1n. where n is no. of steps.

      Where, F1= 1-


      They consider all offers for both negotiation issue and pre selection issue. First x0 is an offer generated for n1 to nk

      Coordinator calculates the value of new penalty on the basis of overall attributes , how many agreements has not been reached, number of rounds left and weight.

      agents where nk<=nl. If offer gets rejected then they generate offer for next nk+1 agent to nl and xi offer for n1 to nk. Offers weight is xi+weight up to nk<=weight of offer x0+ weight nk+1 to nl. Time-dependent strategy based

      negotiation is dynamic in nature but they do not consider behavior of opponents.

    4. Linear programming

    This system produces higher joint profits in negotiations and it is faster in reaching agreements on the average under the condition of agreement of reciprocity than the trade-off mechanism based negotiation system. Agent can participate dynamically. In that, they extend Faratin (2000) system. In this paper, the multi-attribute utility theory (MAUT) is applied to evaluate the profits of the participants. In this they used mediator, client agent and proxy server. They proposed jini LUS architecture [7].The seller agent and buyer agent are connected to each other through proxy of mediator. The mediator agent evaluates the profits of the entire negotiation participant and sorts them in decreeing order of joint profit. Thereafter, the final couples are determined from the sorted list. The time complexity determines the final couples with the maximum profit criterion is where N is the number of negotiation partners, since sorting takes longer time than any other operations. A mediator agent, in this criterion, is designed to match the couples with the FordFulkerson algorithm that solves the maximum cardinality matching in a bipartite graph. It finds the final couples in O (NM) time, where M is the number of client agents who participated in the negotiation.

    The formula is used as,

    Evaluating the profits

    The value of the utility function can be regarded as the profit of either a buyer or a seller. The utility function Profits (xi) of a participant can be expressed as follows:


    Where n is the number of attributes, xi is a variable representing the offer value of the ith, attribute, wi is the weight of the ith attribute, and finally the evaluation function E(xi) of the ith attribute is expressed in terms of the request values (request_valuei) and the allowable values (allowable_valuei) as follows:


    where the allowable value means the maximum value to which the participant concedes for negotiation, and the request value means the maximum value the participant wants in negotiation. For example, for the price attribute of a product, if a buyer wants to pay $800 for the product, yet the buyer may pay up to $1000 for it, then the request and the allowable values for the buyer are $8000 and $1000, respectively. In Eq. (7), allowable_valuei and request_valuei are the allowable and the request values of the ith attribute, respectively. If xi= request_valuei, the degree of satisfaction of the ith attribute is assumed to be the highest, and E(xi) representing the degree of satisfaction of the ith attribute becomes 1. On the contrary if xi=allowable_valuei, the degree of satisfaction of the ith attribute is the lowest and E(xi) is set to 0. Therefore, when xi is within the range between request_valuei and allowable_valuei, E(xi) ranges between 0 and 1. If xi is out of the range between request_valuei and allowable_valuei. E(xi) is set to either 0 or 1 depending on the value of E(xi). That is, if E(xi) <0, it is set to 0, and if E(xi) > 1, it is set to 1.

    A mediator agent receives the negotiation information from the participants, a buyer and a seller, in a bilateral negotiation and carries out a negotiation between a buyer and a seller who have the common negotiation ranges (CNRs) of all the attributes of the product. The negotiation range of the ith attribute means the range between allowable_valuei and request_valuei for a participant and the CNR of a seller and a buyer for an attribute denotes the range overlapped between the negotiation ranges of both parties for the attribute. A mediator agent can finally find an agreement for reciprocity between both parties. Reciprocity means the reciprocal profit between a buyer and a seller, and an agreement for reciprocity means an agreement that is not partial to one participant over the other within a small allowable range.

    In this, they focus on the efficiency of a system with respect to joint profit, execution time, and the capability of extending toward multilateral negotiations in a virtual market. It is used in distributed system. It gives more profit and faster than trade-off based negotiation system. Practically it does not support for all types of frameworks. There are some more methods are developed. Some of few we explained here in short. Each method has different advantages on different cases. It is difficult to say that particular method is best for multilateral automated negotiations. But from our survey we can say that game theory is suited for B2B framework. In the game theory based negotiation, it is difficult to compute behavior of

    software agent in all situations. Genetic algorithm based negotiation is not sitable for large scaled system .If number of participant will increase then its searching complexity of agents can be increased then It will require more time. This problem is over come by linear programming. Linear programming negotiation system is faster than genetic algorithm based negotiation system. Parallel process is done using multithreading negotiation based system. We can improve performance of negotiation by adopting the environment conditions. The quality of an opponent model can be measured by using agents performance as a benchmark or directly evaluating its accuracy by using similarity measures [11].


    Market Basket Analysis is the discovery of relations or correlations among a set of items. Decision function sends final output of negotiation process to negotiation result module. In graphical analysis, we are trying to analysis the graph of negotiation in which preferences are taken using Matlab and analyzed using XLS.


    Multilateral negotiations are more complicated and time consuming than bilateral negotiations because in the multilateral automated negotiation we required to do multiple matching between the participants. Multilateral automated negotiation system gives better result than bilateral automated negotiation system. Participants can take joint decision about their number of issues. If web service is used in the multilateral automated negotiation system then it can give faster results to the participants. The system, in which the technique of finding the behavior of opponents is used, is always better than the system in which the technique of finding the behavior of opponents is not used.

    Fig. 3. Architecture for multilateral automated negotiation [AMAN]

    As shown in Figure 3, in multilateral automated negotiation, number of buyers and sellers are involved. The requirement of buyer and seller are passed to the product and preferences block. Each buyer and seller have their own preferences, as per their priority of item and weight will be assigned to each item. Each buyer and seller selects their agent by manually or automatically. Artificial neural network (ANN) is used to select agents automatically. The multi-agent module is used to select the agent. Agent performs negotiation on the behalf of buyer and seller.

    There should be one agent for each participant and this is a constraint in our model. Decision function is used to take the decision about negotiation process. After checking the constraints of system, decision function decides whether offer will be accepted or rejected. Offer generator is used to generate offers for buyer and seller. For offer generation we will use multi attribute utility function. Decision function saves each offer into the database, which is generated by offer generator. Available package is used by decision function in the case of urgency. The case of urgency is depending on time factor. If required time of buyer decreases then decision function sends direct available package to multi agent module. Among these packages, buyers agent selects one of the packages which is the most suitable for buyer preferences. Package will be available on the basis of market basket analysis.


Considering some of previous the papers, we found that multilateral negotiation system can be developed in fuzzy systems, multithreading, time-dependent systems, systems on linear programming and genetic algorithms. We are working in the direction such of building multilateral system using multiple agents as well as using the technique of predicting behaviors of opponents. The behavior of negotiation agents is determined by their tactics in the form of decision functions. Knowing the information about the opponent will increase an agents performance in negotiation. Various experimental results show that the predictive decision-making gives better results in terms of the utility gains for the adaptive negotiation agent as compared with a range of non-predictive negotiation strategies. Prediction of partners behaviors in negotiation has been an active research direction in recent years in the area of multi-agent and agent system. So by employing the prediction results, agents can modify their own negotiation strategies in order to achieve an agreement much quicker or to look after much higher benefits.


  1. Bahador Shojaiemehr and Marjan Kuchaki Rafsanjani, A fuzzy system approach to multilateral automated negotiation in B2C e- commerce, Springer-Verlag London 2013.

  2. Li,Min;Pan Li,Liu shijun and Wu Lei, A win-win Multi-issue Service Negotiation Model Based on Bayesian Learning, Cloud Computing and Big Data (CloudCom-Asia), International Conference on CLOUDCOM-ASIA,2013.

  3. Amruta More, Sheetal Vij, Debajyoti Mukhopadhyay, Agent Based Negotiation using Cloud – An Approach in E-Commerce 48th Annual Convention of the Computer Society of India, CSI 2013 Proceedings, Visakhapatnam, India, Springer-Verlag Germany, pp.489-496; ISBN 978-3-319-03107-1,2013

  4. Mohamad Irfan Bala and Sheetal Vij,Automatrd Negotiation and Behavior Prediction, International Journal of Engineering Research & Technology (IJERT), ISSN: 2278-0181 vol.2 issue, 2013.

  5. Mohammad Irfan Bala, Sheetal Vij and Debajyoti Mukhopadhyay, Intelligent Agent for Prediction in E-Negotiation: An Approach, CUBE 2013 International IT Conference, CUBE 2013 Proceedings, Pune.

  6. Mohammed Irfan Bala, Sheetal Vij and Debajyoti Mukhopadhyay, Negotiation Life Cycle: An Approach in E-negotiation with Prediction, 48th Annual Convention of the Computer Society of India; CSI 2013 Proceedings, Visakhapatnam, India; Springer- Verlag Germany; ISBN 978-3-319-03107-1,2013.

  7. Saurabh Deochake ,Shashank Kanth,Subhadip,Suresh Sarode,Vidyasagar Potdar and Debajyoti Mukhopadhyay, HENRI:High Efficiency Negotiation-based Robust Interface for Multi-party Multi-issue Negotiation over the Internet,Cube Pune

    ,India,ACM 978-1-4503-1185-4/12/09,2012.

  8. Raz Lin, Sarit Kraus, Tim Baarslag, Dmytro Tykhonov, Koen V. Hindriks, and Catholijn M. Jonker. An integrated environment for supporting the design of generic automated negotiators. Computational Intelligence, 2012.

  9. Miniar Hemaissia, Amal El Fallah, Christophe Labreuche and Juliette Mattioli, A Multilateral Multi-issue Negotiation Protocol, AAMAS, Honolulu, Hawaii, USA, 2007.

  10. Ricardo Buttner,A classification Structure for Automated Negotiations,IEEE/WIC/ACM international conference on web intelligence and intelligent technology, Hong Kong,China,2006.

  11. Sanghyun Park and Sung-Bong Yang, An efficient multilateral negotiation system for pervasive computing environments, SICE- ICASE International Joint Conference in Bexco, Busan, Korea, 2006.

  12. Ulle Endriss, Monotonic Concession Protocols for Multilateral Negotiation, AAMAS06 ACM, Hokkaido, Japan, 2006

  13. Sanghyun Park and Sung-Bong Yang, An Automated System based on Incremental Learning with Applicability Toward Multilateral Negotiations, SICE-ICASE International Joint Conference ,Bexco, Busan, Korea,2006.

  14. Karl Kurbel, Iouri Loutchko and Frank Teuteberg, Fuzzy MAN: An Agent-Based Electronic Marketplace with a Multilateral Negotiation Protocol, Springer-Verlag Berlin Heidelberg, 2004.

  15. Susanne Klaue, Karl Kurbel and Iouri Loutchko, Automated Negotiation on Agent-Based E-Marketplaces: An Overview, 14th Bled Electronic Commerce Conference Bled, Slovenia, June 25 – 26, 2001.

  16. P Faratin, C Sierra, N R Jennings and P Buckle, Designing Responsive and Deliberative Automated Negotiators .refer to use as public network.

  17. Charles J. Thomas,Federal Trade Commission, Harvard Law School and Bart J. Wilson, A Comparison of Auctions and Multilateral Negotiations, Bureau of economics federal trade commission Washington ,2000.

Leave a Reply