Automated Negotiation in E Commerce:Protocol Relevance and Improvement Techniques

S.R.Vij,D.MukhopadhyayandA.J.Agrawal

Abstract: We all negotiate,formally or informally,in jobs,in day today lives and outcomes of negotiations affect those processes of life.Although negotiation is an intrinsic nature of human psyche,it is very complex phenomenon to implement using computing and internet for the various purposes in E Commerce.Automation of negotiation process poses unique challenges for computer scientists and researchers,so here we study how negotiation can be modeled and analyzed mathematically,what can be different techniques and strategies or set of rules/protocols to be implemented and how they can be relevantly implemented.We are in a quest to find out how this complex process,which involves human psyche can be automated using computers and modern day technologies.Now,the quest is not only automation,looking at the research in the related field in last ten years;but it is all about finding solutions to make e-negotiation more efficient and more accurate,as well as useful in any kind of electronic trading situations.Here is an attempt to consolidate our work of last few years on automation of negotiation process;we call it as negotiation protocol on research,study as well as implementation level of negotiation automation.Overall,we are trying to give few solutions to make the automation more efficient.

Keywords: Negotiation automation,decision support systems,bilateral,multilateral,alternating offers protocol,multi strategy.

1 Introduction

Negotiation is ubiquitous,clearly an important activity in our lives as well in the global economy and is worthy of academic study.However,in Fatima et al.[Fatima,Kraus and Wooldridge (2015)],negotiation is central to our lives,that does not imply that we are good at it.Negotiation is usually a better and dynamic stand to other related approaches of reaching to an agreement like social choice,arguments and fair division.The purpose of negotiation is to reach an agreement,in particular,agreement in the presence of conflicting goals and preferences.Usually in the real world,preferences,goals,aspirations of individuals do not match,there negotiation can be utilized.The analysis of this deep psychological phenomenon and a question of how computers can be useful in implementing it virtually,to give inherent benefits of negotiation in trading,buying,selling,auctioning,bidding,bargaining raises many interesting scientific problems.When engaged in complex negotiations,people become tired,confused,emotional,making naïve,inconsistent,rash decisions.They fall prey to personal prejudices,misapprehensions and fallacies.Many times,it can be a profoundly stressful activity.So ultimately this is an era where we have to have computer programs/software agents/agents to negotiate on our behalf.These agents should be capable of overall activities (not all but few) like recognition of social conflict/problem where negation can be an approach,gathering and structuring private information,deciding participants/ stakeholders,opponent analysis,protocol/rules selection,exchange of offers and feedback,argumentation/justifications/promises,learning,dynamic strategy selection,resolution in case of failure,renegotiation.

Figure 1:Classification of automated negotiation

Our main focus in this paper is on how effectively and optimally few of the existing negotiation mechanisms (bargaining-bilateral/multilateral,Bidding,Auctioning,multi strategy) can be suitably implemented with techniques like decision support systems,linear programming and form a consolidated research material on various strategies with set of rules/protocols with few assumptions.We are presenting few results and detailed analysis on a working of bilateral negotiation protocol using behavior prediction in decision support system [Bala,Vij and Mukhopadhyay (2015)];multilateral negotiation protocol using linear programming [Vij,Patrikar,Mukhopadhyay et al.(2015)];Negotiation using Rule based and case based reasoning protocol [More,Vij and Mukhopadhyay (2015)].

2 Related work

Survey on bilateral e negotiation and opponent's behavior prediction based on decision support systems-Predicting the agent's behavior and using those prediction results to maximize agents own benefits is one of the crucial issues in the negotiation process.It is necessary for an agent to produce offers based on his own criteria because an agent has limited computational power and incomplete knowledge about opponents.Various approaches have been proposed for predicting the opponent's negotiation behavior.Bala et al.[Bala,Vij and Mukhopadhyay (2015)] reviewed some of the approaches to come up with certain conclusions regarding the efficiency of each approach likegame theory,bilateral model with time dependant decision functions,non linear regression,classification method,machine learning approach,feed-forward backpropagation neural network with tit for tat negotiation strategyand their short comings.

Survey on automated multilateral negotiation based on linear programming-There are many methods for multilateral automated negotiation.The commonly used methods areutility theory,heuristic based algorithms,argumentation-based negotiation,fuzzybased negotiation and game theory.Wang et al.discussed how amixed integer programming algorithm can provide optimal solutions,but scalability and computation time would increase when the number of agents increases.Park et al.[Park,Yang and Amyot (2006)] proposed a negotiation agent systembased on incremental learningin order to increase the efficiency of bilateral negotiations and to improve applicability towards multilateral negotiations.They proposed an automated negotiation system that can efficiently carried out as multilateral negotiations with multiple attributes in pervasive computing environments.Monotonic Concession Protocol for Multilateral Negotiation was described by Endriss [Endriss (2006)] is a deadlock-free protocol which restricts the utility function.It is not applicable for all cases of negotiation.When the participant does not share his preference in the negotiation,the agent needs to analyze the behavior of the opponent.Performance of the negotiation can be measured in two ways:using an agent's performance as a benchmark for the model's quality,and directly evaluating its accuracy by using similarity measures.As per Lin et al.[Lin,Kraus,Baarslag et al.(2012)],there is an almost linear correspondence between accuracy and performance of the system.This study measured accuracy of a system over timing,but did not consider a system based on resource dependence.Dong et al.proposed amultiattribute negotiation model based on internal factor argumentation;the system can achieve a Pareto efficiency solution,promotes cooperation between agents,and then reaches a win-win result.In a multilateral multiple issue negotiation protocol,a multiple agent system(MAS) is used for decision making.Considering these papers,we can say multilateral automated negotiation gives better results to buyers and sellers.A negotiation protocol is a general rule that can be used by anybody in the negotiations.The protocol determines the flow of messages between the negotiating parties.A win-win strategy gives better outcomes to buyer and seller.Intelligent techniques such as neural networks,genetic programming,fuzzy logic theory and Bayesian theory are used to learn the opponent's behavior,for decision-making and for generating offers.Fuzzy systems,multithreading,game theory,genetic algorithms and linear programming are some of the methods that can be used for multilateral automated negotiations.Vij et al.[Vij,Patrikar,Mukhopadhyay et al.(2015)] proposed an automated negotiation system based on linear programming with multilateral environment.

Survey on e negotiation using rule based and case-based reasoning-[Xiaowen and Jin (2012)] introduced automated negotiation model for tourism industry.To improve the negotiation efficiency and success rate,this system proposed RBR and CBR.The model employs CBR method to support an automated negotiation by past successful negotiation cases used for those negotiation partners that have no contract rule existing in each other.This system does not support multi party multi issue negotiation.Vrbaski et al.[ Vrbaski and Petriu (2012)] proposedContext-aware systemswhich use rule-based reasoning engines for decision making without involving explicit interaction with the user.It is difficult to rank suitable solutions based on unclear,qualitative criteria with a rule- based approach,whilerule-based systems excelin filtering out unsuitable solutions based on clear criteria.Agent also learns from its previous negotiation experience.Maes et al.[Maes,Guttman and Moukas (1999)] introduced aKasbahnegotiation model.In this system,agents can only negotiate over the single issue of price.However,B2B negotiationsoften involve multiple issues.Moreover,the Kasbah agents can only act according to one of their pre-defined negotiation strategies which may not lead to the optimal negotiation results.Wurman et al.[Wurman,Wellman and Walsh (1998)] introduced theMichigan AuctionBotis a general purposedInternet-based auction serverhosted by the University of Michigan.Sellers can create new auctions on AuctionBot by choosing from a set of pre-defined auction types and then enter their specific auction parameters such as clearing time,minimum bid increment and whether proxy bids are allowed.E-bay is the example of AuctionBot negotiation system.Some of above papers support multi party multi issue negotiation rule-based reasoning and case-based reasoning.Our negotiation system [Vij Patrikar,Mukhopadhyay et al.(2015)] is abilateral,multi-party,multi issue negotiation model.In this system,buyer and seller negotiate o multiple issues at a time and when both buyer and seller come to final decision,then only negotiation process will be stopped.

Survey on multi strategy-based e negotiation-A goal deliberated architecture by Cao M.which is based on BDI theory using Faratin's time dependent and behavior-dependent tactics.It uses Boulware or Conceder and concession rate to predict the behavior and to select the appropriate strategy,this system faster than the earlier ones.Nguyen and Jennings proposed a novel heuristic model for coordinating multiple bilateral one-tomany negotiations in service oriented contexts.The bilateral concurrent model comprises of coordinator,number of negotiation thread 8 (one per seller) and coordinating manager.The coordinator selects or changes strategy for each thread on the basis of probability distribution,success matrix and payoff matrix.The significant shortfall of the model is;It is suitable for the situations where the number of seller are more than one,for different seller different strategy is chosen,but our proposed system will be selecting among the strategy for a single thread,i.e.,one seller one buy dynamically,second shortfall in the model is designed based on the buyer's view point.A reward and regret based strategyalgorithm that usesa Soccer Play approachfor learning best strategy.In this model,a pool of strategies is chosen by expert where every strategy has a weight associated with it,implying the applicability for a negotiating situation.The effectiveness of this method can be verified if weight chosen or adjusted of a strategy against a negotiating situation in such a way that it will minimize the regret associated with the selection of strategy.Compared to Goal deliberated model this model needs more computational time for finding the best strategy,also needs an expert to choose the strategies to be included into the pool of strategies.All existing negotiation agent implementations deal with the problem of whether to accept and when to accept.In many cases,the agent accepts a pro- proposal when the value of the offered contract is higher than the offer.The Acceptance model of the paper [Awasthi,Vij,Mukhopadhyay et al.(2016)] takes into account the offer it is ready to send out at that moment in time.Moreover,the focus of the work is not on comparing acceptance conditions as only one specific instance is studied.

3 Architectural aspects and working for negotiation automation

The most prominent issues that must be addressed in a negotiation mechanism are:

1.How to represent negotiators' preferences and offers;

2.How to evaluate an incoming offer;

3.How to compute concession and generate an offer;

4.How to predict the opponents' preferences.

Components of automated negotiation system are;Service registration centre,Negotiation service requester,Negotiation service provider,Protocol.

Figure 2:Nissen's integrated commerce model and Components of automated negotiation system

3.1 System architecture bilateral e negotiation and opponent's behavior prediction based on decision support systems

In this particular protocol,we are using time dependant tactics of Decision Functions algorithm.We could analyze our readings of offers and counter offers as noted in our previous research values and by graphical representations of Hard headed/Conceder and Linear strategies,we can say an efficient bilateral negotiation protocol with opponent's behavior prediction and then counter offer,can be established by time dependant family of decision functions.Although it's a tough task yet to predict in all cases and identify all strategies and also the network delays could be taken care of in exterior environment of the system.

Figure 3:Bilateral system architecture

Proposals and counter proposals are evaluated using scoring function or utility function.

3.2 System architecture automated multilateral negotiation with linear programming:

In bilateral automated negotiation,maximum utility for a single agent can become Minimum utility for opponent agent,and therefore the chance of join decision is low.

Evaluating the profits,the utility function Profits(xi) of a participant is as follows:

wherenis the number of attributes,xiis a variable representing the offer value of theith,attribute,wiis the weight of theithattribute,and finally the evaluation functionE(xi)of the ithattribute is expressed in terms of the request values (request_valuei) and the allowable values (allowable_valuei) is:

Figure 4:Multilateral system architecture

Multilateral negotiations are more complicated and time consuming than bilateral negotiations because in the multilateral automated negotiation,we require to do multiple matching between the participants.It gives better result than bilateral automated negotiation system.The system,in which the technique of finding the behaviour of opponents is used,is always better than the system not using it.

3.3 System architecture e negotiation using rule based and case based reasoning

Our research on Automated Negotiation throws light on the aspect of making the protocol efficient if product data as well as negotiation process data is stored on cloud,we can say the negotiation process becomes easy.In this section,let us see how to make faster negotiation process using rule based reasoning and case based reasoning.

Figure 5:E-negotiation agent system with RBR and CBR

There are organizations to maintain data of the negotiation process and product data.

But this maintenance is a very tedious job.In order to overcome this problem,all organizations' product data is stored on cloud.In order to make faster E-negotiation process,we can use the rule base and case based approaches.This system is a bilateral negotiation model.In future this system can be implemented as multilateral negotiation model,behavior prediction and also use the concept of expert system for increasing success rate of negotiation process.

3.4 System architecture multi strategy based e negotiation

Negotiation strategy is an umbrella term which defines the bidding,opponent profiling and acceptance criteria of a party.Every party can define and develop its negotiation strategy.Every negotiation process requires an active collaboration of buyer and seller negotiating software entity (also called as negotiating agent).This drives a need for a negotiation framework which is flexible in terms of platform,implementation and place.We propose a web-service,multi- strategy selection based decision support system which can select strategies during the course of negotiation,in a more informative way and can deal with range of negotiation scenario.The advantage of using multi- strategy is high success rate i.e.,successful negotiation;Fast response because of profiling;High number of scenario because of strategy pool.The contribution of this research work is to maximize the success rate of negotiation process,i.e.,convergence into successful contracts and eventually maximizing the efficiency and effectiveness of the system.

Figure 6:Web based framework for automated negotiation

Negotiation strategy can be broadly classified into time,resource and behavior dependent strategies.Time dependant strategy are those which are driven (take certain action) with the tick of time.Behavior dependent strategies are those which are driven by opponent behavior.And resource dependent is based on availability of product.The different strategies can be defined as:

Conceder

Conceder strategy(C) is based on time and exposure to negotiation bids.

Boulware strategy

Boulware strategy (B) is based on time and exposure of bids.Notations are same as above.

Nice tit for tat strategy (NTT)

Nice Tit for Tat strategy is behavioral strategy.Concession =

Relative tit for tat strategy

Relative Tit for Tat(RTT) is also behavioral strategy with retaliation capability.

Utility based strategy

Utility Based(UB) is opponent based strategy,it uses average and variance.

where UT defines the target utility.

BRAM

Every strategy is analyzed against opponent strategy,and the behavior is analyzed.The two main parameters used in our experiments are average utility gain and average acceptance weight.All the six strategies can be categorized into three sub category,Conceder and Boulware (hardheaded) are time dependant,NTT and RTT are behavior dependent,BRAM and utility based is resource dependant.The experiment is conducted with two motives;first to prove the concept of multi-strategy,i.e.with the change in opponent strategy the performance of applied strategy varies,second to gain the insight of negotiation strategy.

4 Results and analysis

4.1 For bilateral system with opponents behavior prediction

Following are some of the project snapshots as well as graphical analysis.

Figure 7:Bilateral bargaining with behavior prediction for Automated Negotiation

Concession rate of each agent differentiates the various agent strategies.Best strategy is to concede when negotiating with competitive agent and be hard headed when negotiating with cooperative agent.There is no universally best approach or technique for automated negotiation.Prediction results can be used to improve the performance of agents.Huge scope for improvement,bilateral negotiation to multi lateral negotiation,agent mediated scenario,also to consider emotional and cultural differences.

4.2 Multilateral negotiations

Multilateral negotiations are more complicated and time consuming than bilateral negotiations because in the multilateral automated negotiation,we require to do multiple matching between the participants.Multilateral automated negotiation system gives better result than bilateral automated negotiation system.The system,in which the technique of finding the behaviour of opponents is used,is always better than the system not using it.

Figure 8:Bilateral vs. multilateral automated negotiation

For real time multilateral automated negotiation,cloud will be more helpful.Cloud requires low maintenance on data and is more secure,but it is useful for large application because cloud is costly.Intelligent decision function is required.

4.3 Negotiation using RBR and CBR and improved memory utilization and response time

There are organizations to maintain data of the negotiation process and product data.But this maintenance is a very tedious job.In order to overcome this problem,all organizations' product data is stored on cloud.In order to make faster E-negotiation process,I can use the rule base and case based approaches.This system is a bilateral negotiation model.In future this system can be implemented as multilateral negotiation model,behavior prediction and also use the concept of expert system for increasing success rate of negotiation process.

Figure 9:Response time and memory utilization for automated negotiation

4.4 Multi-strategy selection

Every Strategy has certain applicability,and its selection impacts the utility and final outcome of negotiation.To resolve the conflict among negotiating parties hard bounded strategy is chosen.Any selection of strategy has a significant impact on the utilities of agents and final outcome,therefore selecting a strategy is a critical problem since opponents and their behavior are unknown,difficult to model and could be uncooperative.Multi-strategy selection can deal with high number of negotiation scenario,can yield into higher success rate and utility gain,further its will be difficult for opponent to predict our strategy.

Figure 10:Multi strategy base selection results for automated negotiation

Selecting strategy for a particular opponent during negotiation for a small dataset is a complex task,as learning,profiling,predicting can't be applied effectively.Web- service based deployment facilities in-dependency of platform,place,implementation etc.Winwin case of negotiation is best suitable for real life negotiation.Win-loss go against the basic,it may incur negotiation failure.The future enhancement can be,more number of strategy to enhance the competitiveness of system and the proposed algorithm need to be verified on other negotiation scenario.

5 Conclusion

There is a huge scope for analysis and research on the performance aspect of an automated negotiation protocol techniques,mainly can be utilized in E-Commerce.So,the automated negotiation protocol relevance in modern times,on internet based systems and major speed as well efficiency,storage improvement techniques in the basic design are given in this paper which can be basis for further interdisciplinary research in Enegotiation and web services,software technology,human psychology in bargaining,bidding and auctions.

References

Awasthi,S.;Vij,S.;Mukhopadhyay,D.;Agrawal,A.(2016):Multi-strategy based automated negotiation:BGP based architecture.International Conference on Computing,Communication and Automation,pp.588-593.

Awasthi,S.;Vij,S.;Mukhopadhyay,D.;Agrawal,A.(2016):Multi strategy selection in e-negotiation:a proposed architecture.International Conference on Information and Communication Technology for Competitive Strategies,vol.C,no.79.

Cao,M.;Luo,X.;Luo,X.;Dai,X.(2015):Automated negotiation for e-commerce decision making:a goal deliberated agent architecture for multi-strategy selection.Decision Support Systems,Elsevier Science Publishers,vol.73,no.C,pp.1-14.

Endriss,U.(2006):Monotonic concession protocols for multilateral negotiation.ACM Conference on Autonomous Agent and Multiagent System,pp.392-399.

Bala,M.;Vij,S.;Mukhopadhyay,D.(2015):Automated negotiation with behavior prediction.International Journal of Internet Protocol Technology,vol.9,no.1,pp.44-50.

Fatima,S.;Kraus,S.;Wooldridge,M.(2014):Principles of Automated Negotiation,pp.1-269.Cambridge University Press.

Lin,R.;Kraus,S.;Baarslag,T.;Tykhonov,D.;Hindriks,K.et al.(2012):GENIUS:an integrated environment for supporting the design of generic automated negotiators.Computational Intelligence,Wiley Periodicals,vol.30,no.1,pp.48-70.

Liu,X.;Yu,J.(2012):Hybrid approach using RBR and CBR to design an automated negotiation model for tourism companies.International Conference on Management of e-Commerce and e-Government,pp.197-201.

Maes,P.;Guttman,R.;Moukas,A.(1999):Agents that buy and sell.Communications of the ACM,vol.42,no.3,pp.81-91.

Vij,S.;More,A.;Mukhopadhyay,D.;Agrawal,A.(2015):An e-negotiation agent using rule based and case based approaches:a comparative study with bilateral enegotiation with prediction.Journal of Software Engineering and Applications,Scientific Research Publishing,vol.8,no.10,pp.521-530.

More,A.;Vij,S.;Mukhopadhyay,D.(2015):An efficient e-negotiation agent using rule based and case based approaches.Advanced Research on Cloud Computing Design and Applications-Book Chapter 16,IGI Global,pp.245-261.

Park,S.;Yang,S.(2006):An automated system based on incremental learning with applicability toward multilateral negotiations.SICE-ICASE International Joint Conference,pp.6001-6006.

Vrbaski,M.;Petriu,D.;Amyot,D.(2012):Tool support for combined rule-based and goal-based reasoning in context-aware systems.Requirement Engineering Conference,IEEE Xplore,pp.335-336.

Vij,S.;Patrikar,M.;Mukhopadhyay,D.;Agrawal,A.(2015):Asmart andautomated negotiation system based on linear programming in a multilateral environment.Smart Computing Review,vol.5,no.6,pp.540-552.

Wurman,P.;Wellman,M.;Walsh,W.(1998):The Michigan internet AuctionBot:a configurable auction server for human and software agents.Proceedings of the Second International Conference on Autonomous Agents,pp.301-308.