Informatica 35 (2011) 123-137 123
Order Statistics Bayesian-Mining Agent Modelling for Automated Negotiation
Samir Abdel Rahman, Reem Bahgat and George M. Farag Computer Science Department,
Faculty of Computers and Information, Cairo University, Egypt E-mail: {s.abdelrahman, r.bahgat}@fci-cu.edu.eg, gmf.deary@gmail.com
Keywords: bayesian mining, order statistics, automated negotiation, multi-issue, multi-session, opponent modelling Received: May 27, 2010
The availability of qualitative knowledge has been recently used to simulate human negotiations accurately. During real-life negotiation sessions, people accumulate their knowledge to opt for most adequate bids by which both negotiating parties reach a win-win agreement. Unfortunately, existing research mainly concentrates on few negotiation bids. This paper proposes order statistics Bayesian-mining agent approach to automate bilateral multi-issue multi-session win-win negotiation problems. The proposed agent applies a reallife social bid ranking based on historical bids of all previous negotiation sessions to dynamically update all issues' weights and preferences. Moreover, it uses our proposed deterministic Trade-Off counter offer method, rather than the existing haphazard estimation method, to estimate precisely the next bid. Experiments are conducted on 3-issue, 5-issue, 6-issue and 10-issue having 27, 3169, 3122 and 13219200 bids respectively. The selected evaluation analysis methods are mainly Pareto optimality, utility, cost and step-wise measurements. Compared with existing agent sorts, such as ABMP, Trade-Off Bayesian and Mining agents, the proposed agent approach is proved that it is more efficient, effective, scalable and sensitive (adaptable to the opponent steps). Also, it works better to maximize its utilities and to minimize the negotiation costs (the number of rounds).
Povzetek: Opisana je agentna metoda pogajanj, ki se odloca na osnovi Bayesovske statistike.
1 Introduction
The paper aims to automate bilateral multi-issue multisession win-win human negotiation. Negotiation is the process in which two or more parties, having conflicts in their interests, can mutually reach a beneficial agreement on the related set of issues by exchanging some bids. In any bilateral negotiation [20], there are only two parties who exchange their bids using some negotiation protocols. In multi-issue negotiations [20], each bid has many issues such that each issue consists of several discrete items. The negotiator goal is to adjust all issues' preferences to maximize his bid utility. The essential assumption of win-win multi-issue bilateral negotiation is that the two negotiators are rational and they are eager to find a solution of bid utilities that is acceptable to both parties [19], So, each party has to know the preferences of its opponent to reach an agreement. In reality, the negotiators are hardly willing to disclose their private preferences. Consequently, both parties have incomplete information about each other and so may hardly reach an optimal deal. A typical real-life negotiation may need more than one session to reach a successful deal such that each party commences the new session having some gained knowledge about his opponent from previous sessions, where a session is defined as the time duration in which the negotiators decide to communicate with each other to reach a satisfied agreement, if any.
Automated negotiation recently has become a disputed solution to compensate the human disability to do complicated negotiation calculations accurately.
Automated negotiation applications range from simple auctions, in which agents merely have to bid truthfully [29], to complex strategic models, in which agents argue for positions and aim to persuade their opponents of the particular course of action [24],
Some multi-agent research [2, 9, 12] presented strategies to automate multi-issue negotiation. Such research was usually motivated with the high complexity of multi-issue negotiation calculations executed with the lack of available knowledge about the opponent. Recently, some research [7, 12] investigated the use of available knowledge about the environment's bids, issues, or opponent preferences while negotiation sessions move forward. However, they either concentrated on cases having one issue or they depended on few bids from previous/current single session negotiation. Moreover, their assumptions of issue ranking and the data distribution are theoretical rather than experimental; real-life applications are complex in which the agreement is met after successive negotiations having massive hidden information about the environment's preferences and issues that could be mined, i.e. extracted and accumulated, while the negotiation sessions ensue.
This paper presents non-parametric Bayesian-mining agent modelling that depends on all historical successive sessions to solve the complexity of real-life applications. It proposes the following two crucial ideas.
First, while negotiation sessions advance, the
124 Informatica 35 (2011) 123-137
S.AbdelRahman et al.
proposed model gradually learns how to reduce the number of session rounds and to maximize the expected utility upon the ratio of accepted bids. To do that, the model weighs the bids, similar to the human ranking, by which the first bid from each session is the most significant bid and the current session is the most vital session. The model then utilizes order statistics, non-parametric, Bayesian learning to model the opponent preferences and profiles which deals with any unknown data distribution.
Second, a proposed trade-off counter-offer method is used to estimate the next bid more precisely. This is done by replacing existing randomness trade-off method with a proposed partial derivative utility function.
Our experiments are set up against some well-known existing agent approaches using 3-issue, 5-issue, 6-issue and 10-issue applications. We use some evaluation criteria, namely Pareto optimality, utility, cost (number of rounds), step-wise (sensitivity analysis and class studies), and confidence interval calculations. It is experimentally proved that any agent following our proposed model is efficient, effective and sensitive to the opponent steps. Also, the proposed agent scalability is verified as the agent guarantees these features on 10-issue applications.
In comparison with current negotiation approaches, the contributions of the proposed non-parametric Bayesian-mining approach are as follows:
1-It	works with any negotiation data distribution; all current approaches assume normal distribution of data, which is not necessarily true.
2-The	agent outcomes are more effective and sensitive as the agent can benefit from the historical data of all previous negotiation sessions.
3-When	our agent is involved in the negotiation, better agreement is reached fast.
4-When	our agent is involved in the negotiation, both negotiators tend to maximize their utilities.
5-	Our approach is scalable for large data set, while authors of the other approaches state that they have to adapt their models, if possible, to make them acquire such a feature.
The remainder of this paper is organized as follows. The next section discusses other negotiation approaches. Section 3 outlines the evaluation methods stated in the literature. Section 4 presents the overall proposed approach with its assumptions and parameters. Section 5 demonstrates the proposed Bayesian-mining approach. Section 6 presents the proposed counter-offer enhancement. Section 7 shows the experimental results. The paper is concluded with Section 8.
2 Related work
ABMP strategy [15, 16] takes the agent's own utility space in which the next bid utility has less value than the previous one. Unfortunately, the strategy does not use any domain or opponent knowledge. Also it does not search through the negotiation outcome space for results that are mutually beneficial for both parties. Therefore, this strategy is inefficient in complex negotiation
domains although it is shown that it outperforms humans in small domains [1].
Trade-off strategy [9] is based on similarity and iso-curve criteria. In this strategy, the agent tries to find a bid similar to his previously proposed one and to be simultaneously suitable for his opponent. However the random nature of its search impacts on its efficiency. Another disadvantage is its difficulty to determine the bid suitability for the opponent's utility without having any knowledge about his preferences. So, it always needs a complement strategy to detect the opponent preferences.
Bazaar model [33] is a learning approach for sequential decision making in a single session single issue (the price) negotiation. It works by generating random numbers of upper and lower limits for the agent's reservation price to ensure the existence of agreement zone. However, the negotiation model is dedicated only to the price issue which is already known earlier to both agents.
A Bayesian Markov chain model [21] was presented to learn the opponent preferences in single issue negotiation. Its major defect is that it does not have a state-memory to save all negotiation movements since it depends only on the negotiation current state to predict the future bids. Moreover, it works only on a single issue.
Kernel Density Estimator model [7], based on [9], provided a kernel estimation method that depends on the difference between two bids to predict the issue weight. Therefore, the estimator doesn't use its whole available negotiation history to define its kernel. Moreover, it does not provide a learning method for estimating the issue weights, hence, it may be used effectively only with single issue negotiations.
A Bayesian learning modelling [12] was presented to learn an opponent model, i.e. the issue preferences and priorities of the opponent. Unfortunately, the model uses single session only to know the opponent preferences. In most cases, the session has few bids to learn and thus the gained knowledge is often imperfect. Also, it enumerates all possible issue-weight ranks to form the weighted issue hypothesis space which makes the space considerably huge. Moreover, as most strategies do, it assumingly considers the negotiation data to follow the normal distribution which contradicts with real human negotiations.
[18] proposed a theoretical means to acquire negotiation knowledge from a batch of previous bids in previous sessions of negotiations within the e-Marketplace field. The model gives weights for each issue and related items based on the accept/reject probabilities. Then it sums these probabilities to weigh the related bid and finally it ranks the bids' weights to select the bid with the highest weight given that it was not previously selected. The authors report that they theoretically open the door for mining negotiation research. Unfortunately, the issue weight calculation doesn't consider the shape of issue evaluation function which yields some wrong bid selections. Moreover, the selected bid may not be the optimum choice for both
ORDER STATISTICS BAYESIAN-MINING...
Informática 35 (2011) 123-137 125
buyers.
As shown above, current automated negotiation strategies don't exploit all historical bids to enhance the negotiation outcomes. Moreover, they follow some theoretical assumptions which make the negotiation relatively far from reality.
We compare our work with the above mentioned approaches to prove our approach's efficiency, effectiveness, sensitivity to the opponent steps, and scalability. Fortunately, some research, such as [12, 23], tried to prove the scalability of their approaches. They report that it is not easy for any model to sustain high dimensional specifications. The authors of Bayesian Learning model [12] show that they modify their model to make it scalable for 10-issue applications and when compared with the Trade-Off agent, both performances were similar to each other as the agents stay close to the Pareto frontier. In [23], a system of artificial adaptive agents (AAAs), is created and tested for 10-issue against the human agents to evaluate their performance. The authors find that in high dimensions, such as 10-issue, it is very complicated to make a suitable comparison of the behavior and the performance between AAA and human agents since neither the two agents may outperform each other.
Before presenting the proposed framework strategy (Sections 4, 5 and 6), it is also worth exploring the reallife win-win bilateral game strategy. Three cases are possible. The first case is when both players are unprofessional or not able to accumulate knowledge about each other, then the game outcomes are weak. The second case is when one of them is skilful to gain experience from his opponent tactics, then he outperforms his opponent even if he commences the game weakly. Moreover, the game outcomes are relatively high. The last case is when both players are professional, i.e. they can benefit or learn knowledge about the tactics of each other, which may positively affect both of them on the general results of the game. If such game is negotiation, then people benefit from the past/current sessions to achieve the best, even if they have little initial data about their opponents. People always give the highest priority to the first bid in each session and lower priorities to successive bids. Also, they give weights to previous sessions and their bids but the weights reduce as the sessions are further away from the current session.
3 Evaluation methods
Most existing automated negotiation approaches consider mainly Pareto optimality [6, 8, 27], utility [17, 31], cost (number of rounds) [33] and step-wise (sensitivity analysis and class studies) [13] criteria as their evaluation methods. They consider the negotiation of an agent efficient if its outcomes have rapidly reached the Pareto Frontier with the maximum utilization and the minimum number of rounds. Also, they prove the agent effectiveness using Pareto optimality and sensitivity analysis. People, then, apply sensitivity analysis and class studies to test the negotiator adaptability to the
opponent preferences. We use all these methods to evaluate our proposed model.
3.1	Pareto Optimality
This method is to measure the distance of the negotiation outcome to the Pareto Frontier. A deal is Pareto optimal (or Pareto efficient), if it is not dominated by any other deal. In other words, a deal is Pareto optimal if it is the best agreement among all negotiation agents. When the deal is Pareto optimal, the negotiation should end with such an agreement [17, 31],
3.2	Cost Analysis
The cost of a negotiation process is measured by the number of proposals (rounds) exchanged before reaching an agreement [33], The agent is efficient if it does fewer rounds to reach optimum agreement with its opponent.
3.3	Utility Analysis
An automated negotiation strategy should guarantee its agent to reach the maximum utilities when the agreement deal is committed. An efficient negotiation strategy models its agent such that it swiftly increases the outcomes while the negotiation sessions advance.
3.4	Sensitivity Analysis
In the sensitivity analysis [13], not only the study of negotiation outcomes is essential, but also the investigation of the agent faults which are realized throughout the negotiation activities. Another useful sensitivity analysis of the opponent preferences is to dynamically find out the negotiation characterizations. It can be defined by comparing the percentage (Equation 1) of fortunate, nice and concession steps that increases the opponent's utility to the percentage of selfish, unfortunate and silent steps that decreases it. Spontaneously, an agent which only achieves steps increasing its opponent utility can be said to be sensitive to its opponent requirements.
A single negotiation step between an agent current bid and the previous one for that agent which is written as [13] based on utilities as follows:
K{s)=Ua{b')-Ua{b) (1)
For a step .v = /? , —> // . a e [V, 0}. for the Agent
S and its Opponent 0, to denote the utility difference of two bids b and b' in the utility space of agent A From the point of view of the agent S, the negotiation step 5 is classified as [13]:
•	Fortunate Step, denoted by (S+, 0+), iff:
As(sJX), and Ao(s)>0.
•	Selfish Step, denoted by (S+, 0<),	iff:
As(s)>0, and AQ(s)< 0.
•	Concession Step, denoted by (S-, 0>), iff:
As(s)<0, and AQ(s)> 0.
•	Unfortunate Step, denoted by (S<, 0-), iff:
As(s) <0, and AQ(s) <0.
126 Informatica 35 (2011) 123-137
S.AbdelRahman et al.
•	Nice Step, denoted by (S=, 0+),	iff:
As(s)=0, and Ao(s)>0.
•	Silent Step, denoted by (S=, 0=),	iff:
As(s)=0, and Ao(s)=0.
The measure for sensitivity of the agent A (Equation 2) to its opponent's preferences is defined for a given trace [13] which includes all session bids for both agents.
sensitivity a (t) = ((%
Fortunate	concession (O)) (2)
^t/0 Selfish (0)+ Unfortunate (K ))+ i^0 Silent (K ))) y
If sensitivitya(t) I. then an agent is more or less insensitive to opponent preferences. If sensitivity a(t)>\, then an agent is more or less sensitive to the opponent's preferences. The sensitivity notion is asymmetric, i.e. one agent may be sensitive to the other's preferences, but not vice-versa.
3.5 Class Studies
Given a trace (session offers) / = (b\, b], b]of
offers, f denotes the ith element of this sequence, ts(t0) denotes the sequence of steps from t that are
made by the agent himself (opponent), tc denotes the
subsequent steps that belong to a class c and finally t, .. written tac, denotes the subsequent steps by
ae{S,0} that belong to class c; where the class c 6 {Fortunate, Nice, Concession, Selfish, Unfortunate, Silent} (Section 3.4). In this research, we are interested in two essential metric measures namely:
• Total utility difference per class
of sums of utility differences in all
The pair Total c(t) of sums of utility differences i steps of class c in a sequence t of steps is defined by:
Total Jt) = TotaLJt)
Where for any agent
a e
Total c(t) = TotalSc(t) agent
{S,0}.Total ac(t)= X,A a (i,')
(3)
can be seen as a measure of adaptability of a party to its opponent.
4 The proposed approach
The proposed framework handles a bilateral multi-issue multi-session win-win negotiation (Section 1); the agents are rational to be involved in such negotiation. All negotiating agents work independently to maximize their utilities such that all of them win. The negotiation bids are independent which means that the values of bid preferences and issues are not derived from the other bid values. One essential assumption is that the data distribution is unknown. Two other crucial assumptions are related to bids' ranking and bid selection (Section 5). Finally, the model utility function is assumed to be a linear summation (Equation 5)

[8, 12] (5)
• Average Utility Difference per Class
The pair u-Avec(t) of average differences in utility in all steps in class c in a sequence t of steps is defined by:
u-Avec(t) = u-AveSc(t)	(4)
Where for any agent a e {S,0\.Total ac(t)= £ A fl (t'c)/#tc
Here #tc is the number of steps of class c in trace t.
This metric measures the average utility conceded per negotiation step [8], Negotiation strategies could be observable as negotiation dance patterns. For example, the success of a strategy that is supposed to learn its opponent's preferences can be verified by checking whether the frequency and/or the size of unfortunate steps over a negotiation trace decreases. Such patterns
Where w is the issue weight and is the issue
evaluation function; e e [0,1].
Beside the model utility function, the main model equations are issue hypothesis space function (Equation 13) and order statistics Bayesian-mining conditional probability function (Equation 14). Using the evaluation methods (Section 3) to test the proposed model, the following steps are orderly done:
1.	The model utility function is calculated.
2.	Using the above assumptions, bid weighted issues w is calculated (Sections 5.2 and 5.3).
3.	Issue hypothesis space (Equation 13) of all bids is defined as the Cartesian product of the shapes of the issue evaluation functions ei (Equation 5) and iv (Step 2).
4.	At each bid arrival, the prior probability ¡>(iij )',H }eH
is updated using Bayesian-Mining Learning approach (Section 5.4) and the Bayesian rule of historical bids order statistics (Equation 14).
5.	The proposed counter-offer ht (Equation 22) using
expected utility u{bt) (Equation 21) is updated using
(Equations 20 and 5).
Throughout the Steps (2-5), all possible bids transactions are recorded including session id, bid <issues, items, weights, utility, rank>, and opponent acceptance status (Yes/No).
5 Mining the opponent profiles
The order statistics Bayesian-mining strategy is to minimize the number of session rounds of an agent as well as to maximize its utility. The agent rationality is increased whilst the negotiation sessions advance. Also, it is proportionally boosted with the opponent rationality. The opponent results depend on its preferences and behaviour. Fortunately, any opponent always gains from playing against the proposed agent since the game session rounds are extremely diminished, hence, the agreement is reached faster.
ORDER STATISTICS BAYESIAN-MINING...
Informática 35 (2011) 123-137 127
In order to apply skilfully its strategy, the proposed agent should have twofold essential properties. First, it mines all historical data from all previous sessions regardless of the underlying data distribution. Second, it uses order statistics Bayesian-mining approach to learn successfully the opponent profiles/preferences and to make good weight estimation for all negotiation issues based on the proposed ranking and bid weighing.
5.1 Ranking Bids
In a multi-session negotiation, the current session is considered the most important session. All current (last) session bids take higher ranks than other previous sessions bids. Also, each session first bid is considered the most important one [22] so it takes higher rank than the consequent bids in the same session. Thus the bids are proposed orderly in sequence such that no bid is proposed twice in the same session. The session ranks
(the first bid in each session) /)'' is assigned and to a
negotiation session /' according to:
ri
■ , I \session\+x V
mt Y 1 j
(6)
Where x, y is user defined according to the importance of the session, taking a reasonable x for the starting session ranking; in this research y=l, x=3.
In addition, the rank of each bid /', r„ , inside the
v
session is ranked in sequential order as follows:
= i -C/-Ü
/; -r
i-1
N,
[18] (7)
Where
\N,
lis the total number of bids in the
P (reject) = 2, bid ranks (opponent accept = NO)/ N
(9)
Where N is the summation of all ranks. Thus the weight of each item in the issues can be estimated using [30, 5] as follows:
Wj = P(item(i)\accept)= ^ bid ranks containing
item i of (opponent accept = YES) / total ranks of accepted bids in all sessions for all issues.	(10)
If each issue is composed of more than one item, then the bigger item weight is considered as the issue weight with the normalization as follows:
'I
¿=1
w.
(11)
w = {w1)ll ;l>i=1 (12)
negotiation session /'.
5.2	Bid Selection
All framework agents are assumed to be rational such that the agent selects the bid once to allow win-win situation for both negotiating parties. Through the session activities, the utilities of bids are calculated to gauge the bid acceptance/rejection status. Hence, if the proposed bid utility is less than or equal to the opponent expected utility, then the agent has to make an agreement and the related session is accordingly stopped. Otherwise, the agent rejects the opponent bid and the agent bid is proposed.
5.3	Bid Weighing
As follows, the weight factor can be estimated using the historical sequence of bids, each bid items, the status of the opponent acceptance, and the rank of each bid.
P(accept) = ^ bid ranks (opponent accept = YES) /N (8)
Where n is the number of issues. Then, the remaining item set in each issue is adjusted.
5.4	Issue Hypothesis Space
[12] utilizes the issue weighted hypothesis space//as a Cartesian Product of Hw / II/II{ x...xHen ■ //"presents
all combinations of issues' weights related to each
possible issue ranks and is the shape of issue
evaluation function; the function shape may be downhill,
uphill, or triangular. However, since Hw is calculated based on all enumerations of issue weights and the related ranks, its size is relatively huge.
Fortunately, the proposed weighting issue mechanism (Section 5.3) estimates the issue weights based on the accepted ranked bids and hence the combinations of//"weights are limited to the estimated issue weights (l (Equation 12). Therefore, the size of the proposed //(Equation 13) becomes smaller, the number of session bids is reduced, and the bid acceptance likelihood is increased.
H =WxHelxHe2x...xHen (13)
5.5	Bayesian-Mining Opponent Modelling
In the proposed Bayesian-Mining approach, it is needed to update the probability associated with all hypotheses given to the new bid, i.e. the posterior probability given by Eq.14. In reality, the negotiation information about bids may be too imperfect or hidden to be easily estimated, i.e. there is no specific distribution for the historical negotiation data. So, it is decided to utilize the nonparametric and order statistics techniques.
Let />,_«, h,-„ i. bt_„+2,..., bt denote the order statistics of size n of a total number of opponent bids; the utilities of these bids are previously estimated. Let h be the class in which some of these utilities exist. In the proposed Bayesian approach, the most likely class value //. is the
one that maximizes Equation 14:
128 Informatica 35 (2011) 123-137
S.AbdelRahman et al.
Using similar thinking as presented in [10], where the conditional probability [14] is:
p((<è,_j|//Jxp((<è,_„+1)|//Jx - xp|M(è,)|//J) (15)
Equation 14 dominator could be calculated from Equation 16, which is the joint probability density function using the equation used in [4, 10, 14] and defined as follows
P(u(bMbj))=
0 <«(£>,) <«(£>,.) <1
=0 elsewhere
The conditional probability l'((i/(bl )|//;)) (Equation
15) can be estimated effectively using M-estimate approach [26] as follows:
P^p^nL^	(17)
1	n+m
Where „ is the number of transactions from
class//that takes the value u{bt )', n is the total number of
transactions from class Hj. p is a user-defined parameter
and can be computed as the prior probability p(u(bt )) •
m is a parameter known as the equivalent sample size and it determines the trade-off between the prior probability p and the observed probability „ „ [26];
the parameter m is set to 2.0 (this setting is usually used as a default and experimentally it gives satisfactory results) [32],
u(bt) is estimated as P(u(bt)) (Equation 16) which
could be calculated as follows using the equation used in [4, 14] :
P (.U(bt) accepted {bi))=
\P (accept) xY\ P(I,j I accept)} [(P(accepf)xII P{I,j I accept))+ (P(reject)xy[ P(I:j | reject))]
Where /,, is the item of the issue /,, p(acceP{) calculated by (Equation 8), and p (/ \ accept) calculated
by (Equation 10).
p(h] I U(bt_n ), U(bt_n+l ), u(bM ),..., U(bt )) normalization [21, 25] is as follows:
±P{Ht)p{(u(bt_n)Mbt^MbM\...,u(bt)pt)
P(H j) is updated proportional to Equation 8 to get:
gpfo) (20)
j=I
The expected utility u (bis updated when the current opponent counter-offer is proposed during the negotiation process, as follows, using Equation 5:
r\»i . A

j=i
U
[12,21] (21)
Where
•	Hj elf is a hypothesis, and bt is the new bid.
•	P (H j) is the prior probability of H. : the probability that Hj is correct before the new bid bt is seen or it is the current probability of hypothesis // [12],
•	P ((u(bt )|Hj)) is the conditional (likelihood) probability of the new bid bt that its utility might be proposed given that the hypothesis ^ is true.
•	p(u(bt)) is the marginal probability of u(bt)
6 The proposed counter-offer
It is assumed that any agent starts any negotiation session by proposing the offer (bid) which has the maximum utility for his owner. The opponent can accept the proposed offer if the utility of that proposal is higher than the offer he last proposed or the offer he intends to propose, else he rejects and proposes a counter-offer. The trade-off algorithm [9], based on the iso-curve concept,
starts at the opponent's last bid with a utility u {h,) (Equation 21); where the process is performed in ,v steps and /: is the utility difference between steps. In each step, n children are generated which is closer to the agents iso-curve with small tolerance + 5. the most similar to the opponent's bids is selected as a stating bid for another step until the ,v steps are completed. This last selected one is sent to the opponent. Thus the counteroffer is estimated as follows:
î>/+i = argmax w(z>)t9]
¿e^l \Uown !>)-», „¡.«1^}
(22)
This is similar to what was mentioned in [12, 9], However, in [9] the children are generated by distributing the utility gain randomly among the issues under negotiation as being mentioned in the algorithm [9] line (5):
- E-E rt = min( random (Et),--JL) [9] ^3)
Where E is the maximum evaluation gain for the
issue i at this step and /•.',, is the total amount of consumed utility. E - E n is used to limit the final gain to e .
ORDER STATISTICS BAYESIAN-MINING...
Informática 35 (2011) 123-137 129
The weak point in this algorithm is that it may increase the utility of a certain issue that has less effect on the opponent utility due to randomization.
Thus it needs to insert a third item to ensure that the increased utility e is distributed fairly among the issues, and to increase the search effectiveness by performing a more directed search for the children at each step in the direction that causes the smallest amount of satisfaction loss to the opponent while increasing the agent's own utility. To do so, the proposed solution is as follows: Consider a vector v e / ; v = {v, / = 1.. /: j< n },
the set of issues under negotiation, where n is the total number of issues, and v, is computed by normalizing the partial derivatives	). Thus, the proposed
enhancement to (Equation 23) is written as:
E-E.
rt = min (random

,(E,)
w:

(24)
This equation is repeated for all issues similar to the algorithm in [9],
7 Experimental work
The experimental environment is built as follows. First, all the previously mentioned aspects (Sections 3, 4 and 5) are implemented. Second, four agent types are selected and implemented to compete namely, ABMP (A) [15, 16], Trade-Off (T) [9], Bayesian (B) [12], Mining (M) [18] and the proposed Bayesian-Mining (BM) Agent. Finally, three data sets are generated with 3-issue [33], 5-issue [12], 6-issue1 and 10-issue [8] having respectively 27, 3169, 3122 and 13219200 bids. For each data set, the following bilateral experiments (Opponent vs. Me)/( A vs. B) are carried out:
Single-Session Experiments ABMP vs. ABMP ABMP vs. Trade-Off ABMP vs. Bayesian ABMP vs. Mining Trade-Off vs. ABMP Trade-Off vs. Trade-Off Trade-Off vs. Bayesian Trade-Off vs. Mining Bayesian vs. ABMP Bayesian vs. Trade-Off Bayesian vs. Bayesian Bayesian vs. Mining Mining vs. Mining ABMP vs. Bayesian-Mining Trade-Off vs. Bayesian-Mining Bayesian vs. Bayesian-Mining Mining vs. Bayesian-Mining Bayesian-Mining vs. Bayesian-Mining Multi-Session Experiments(l, 3, and 5 sessions) ABMP vs. Mining Trade-Off vs. Mining Bayesian vs. Mining
Mining vs. Mining ABMP vs. Bayesian-Mining Trade-Off vs. Bayesian-Mining Bayesian vs. Bayesian-Mining Mining vs. Bayesian-Mining Bayesian-Mining vs. Bayesian-Mining
7.1 Enhanced Trade-Off Experiments
(3-issue)	Enhanced-	Basic
(1 session)	TRADE-OFF	TRADE-OFF
Mean	0.658	0.510
std dev.	0.080	0.087
Confidence	0.070	0.077
confidence interval 1	0.728	0.587
confidence interva!2	0.588	0.4328
Table 1: Statistical Results for 3-issues		
(5-issue)	Enhanced-	Basic
(1 session)	TRADE-OFF	TRADE-OFF
Mean	0.4132	0.2168
std dev.	0.1084	0.1200
Confidence	0.0487	0.0539
confidence interval 1	0.4620	0.2708
confidence interva!2	0.3645	0.1628
Table 2: Statistical Results for 5-issues		
(6-issue)	Enhanced-	Basic
(1 session)	TRADE-OFF	TRADE-OFF
Mean	0.560	0.421
std dev.	0.145	0.155
Confidence	0.079	0.096
confidence interval 1	0.639	0.517
confidence interva!2	0.481	0.325
Table 3: Statistical Results for 6-issues		
(10-issue)	Enhanced-	Basic
(1 session)	TRADE-OFF	TRADE-OFF
Mean	0.560	0.421
std dev.	0.145	0.155
Confidence	0.079	0.096
confidence interval 1	0.639	0.517
confidence interval	0.481	0.325
Table 4: Statistical Results For 10-issues
Sensitivity	Enhanced-TRADE-OFF	Basic TRADEOFF
3-issue	2	1.5
5-issue	1.5	0.923077
6-issue	1.06666	0.380952
10-issue	3.083333	2.466667
1 We use the online-site: http://intemeg.concordia.ca/
Table 5: Sensitivity for The Basic/Enhanced Trade-Off
130 Informatica 35 (2011) 123-137
S.AbdelRahman et al.
	Agent	Trade-off vs. Trade-off	Trade-off vs. Enhanced trade-off	Performance increased
3-issue	A	0.6733	0.7566	12.376%
	B	0.7	0.76	8.51%
5-issue	A	0.555	0.6675	20.27%
	B	0.81	0.8125	0.309%
6-issue	A	0.82	0.85	3.659%
	B	0.861	0.8656	0.455%
10-issue	A	0.703	0.707	0.624%
	B	0.6436	0.7345	14.126%
Table 6: Performance for Both Algorithms for All issues
In order to weigh the enhanced trade-off contribution on the negotiation process, experiments are done on the mentioned data to compare both the enhanced trade-off and the basic trade-off algorithms (Tables 1, 2, 3 and 4) for (3-issue, 5-issue, 6-issue and 10-issue) respectively. 95% confidence interval is used and the increase in the confidence interval is found that it is between 24%-36%. It is noticed that the standard deviation, the data population variability measure and the confidence intervals, of the enhanced algorithm is smaller than the basic algorithm standard deviation. This means that the data is spread in smaller range of values leading to less marginal error (confidence). It is found that the agreement offers become more closely to the Pareto frontier raising the utilities for both the agent and his opponent (Table 6).
In 3-issue experiments, while the performance (the utility) of the agent is increased by 8.571%, it is increased by 12.376% for the opponent. In 5-issue experiments, while the performance of the agent is increased by 0.309%, it is increased by 20.270% for the opponent. In 6-issue experiments, while the performance of the agent is increased by 0.455%, it is increased by 3.659% for the opponent. In 10-issue experiments, while the performance of the agent is increased by 14.126%, it is increased by 0.624% for the opponent. Also the enhanced algorithm is more sensitive than the basic algorithm (Table 5).
7.2 Bayesian Mining Experiments
Experiments were run based on 3-issue, 5-issue, 6-issue, and to test the scalability of the approach, 10-issue is used. To compare the performance of the Bayesian mining approach, the agents using opponent modelling were compared with agents using the ABMP, Trade-off, Bayesian and mining strategies. All agents played against the same opponent to compare both negotiation trace (intra-transaction) and the final agreement (intertransaction). Negotiation takes place between agents A and B assuming that the latter is the experiment target.
7.2.1 Pareto analysis
The main objective for any automated negotiation is to stay as close as possible to the Pareto efficient frontier. However in current automated negotiation strategies, no player lias prior information about the preferences of the negotiating parties, and so all players don't know where the Pareto efficient frontier is located. It thus remains a challenge to stay close to that Frontier. In this research, the Bayesian-mining approach tries to predict the opponent preferences and to select a suitable bid near the Pareto Frontier. Figures 1, 2, 3 and 4 conclude that the Bayesian-mining approach often makes the best prediction to the opponent preferences compared with other strategies; hence, it selects the bids which are preferable to the opponent reaching an agreement close to the Pareto frontier. It may also be concluded that the Bayesian-mining approach gets the shortest distance between the final agreement and the Pareto Efficient Frontier. This is because the accumulated knowledge regarding the opponent behaviour and preferences shortens the distance between the final agreement and the Pareto Efficient Frontier. In 3-issue experiments (Figure 1), after 5 sessions, when the agent B applies Bayesian-mining strategy to negotiate with the opponent A following the same strategy, Bayesian, Trade-off, Mining or ABMP. it gets the distances of the final agreement to the Pareto Frontier equal to 0.020, 0.192, 0.192, 0.170 or 0.209 respectively. Compared with these results, when a Mining strategy agent has opponents, Bayesian. Tradeoff, Mining or ABMP, its distances would be 0.2618, 0.1828, 0.3753 or 0.261 respectively. Also, in 10-issue experiments (Figure 4), 5 sessions, when the agent B, having our proposed strategy, negotiates with its opponent A which follows the same strategy, Bayesian, Trade-off, Mining or ABMP, the distances of the final agreement to the Pareto Frontier are 0.009, 0.028, 0.072, 0.042, 0127 respectively. Comparing these results with the agent using Mining strategy having the opponents, Bayesian, Trade-off, Mining or ABMP, the distances bccomc 0.144. 0.164. 0.1266 or 0.129 respectively.
Figure l:3-issue Pareto Frontier Closeness Outcomes
ORDER STATISTICS BAYESIAN-MINING...
					
					
.....nil	llll				
LESSEE i i i ; ; i	E 5 E £ -111	E £ E £ E ™ E			
> > > m E >
"II
Figure 2:5-issue Pareto Frontier Closeness Outcomes
6 issues Pareto closseness	
^ .................	!■ Pareto clossensss
mmmmmminmn	ma a
Figure 3:6-issue Pareto Frontier Closeness Outcomes
0.3		
		
;.„.,i«lllllllll	mill 1	■ Pareto closseness |
1 |S! i 1 i s!111 *	11S33113111113	¡Ism
Figure 4:10-issue Pareto Frontier Closeness Outcomes
It is also noticed that when agent B follows the Bayesian-mining strategy, it generally achieves the shortest distance between the agreement and the Pareto Frontier when its opponent is more rational. However, when the agent uses the Mining strategy, there is no general rule to judge which opponent strategy would be better. When agent B follows the Trade-off strategy, it reaches better agreement when the opponent uses the Trade-off, then the Bayesian, and lastly ABMP. When agent B follows the Bayesian strategy (Figures 1, 2 and 3), it reaches better agreements when the opponent is the ABMP, then the Trade-off, and lastly the Bayesian itself. However, in 10-issue experiments (Figure 4), the order of its opponent strategies are the Bayesian. then the Trade-off and lastly ABMP. When agent B follows the ABMP, it reaches better agreements when the opponent uses the Trade-off, then the Bayesian and lastly ABMP.
Informatica 35 (2011) 123-137 131 7.2.2 Negotiation Cost and Utility
Strategy Vs. Strategy (3 Issues)
Figure 5:3-issue Single-Session experiments
Strategy Vs. Strategy (5 Issues)
Figure 6. 5-issue Single-Session Experiments
Strategy Vs. Strategy (6 issues)
Figure 7: 6-issue Single-Session Experiments
Strategy vs. Strategy [10 issues]
Figure 8: 10-issue Single-Session Experiments
132 Informatica 35 (2011) 123-137
S.A. Rahman et al.
0.8 0.7 0.6 >, 0.5 | 0.4 D 0.3 0.2 0.1
1
0.8 -£0.65 0.4 0.2 -0 -
1
0.8 -06
5 0.40.2 -
ABMP VS. BAYESIAN-MINING
(3 issues)
a
3 sessions SESSIONS
Trade-Off VS. BAYESIAN-MINING
08—ri~i
i06— ♦ -
S 0.4----|-
0.2-- ,-
0---^-,-
rW
ZZ! Rounds * Ua ■s-Ub
3 sessions SESSIONS
Bayesian VS. BAYESIAN-MINING
(3 Issues)

IZ^ Rounds ♦ Ua
3 sessions SESSIONS
MINING VS. BAYESIAN-MINING
(3 issues)
W
-3 1
— - 2 - 1
3 Rounds - Ua Ub
3 sessions SESSIONS
MINING VS. MINING
(3 Issues)
3 Rounds -Ua Ub
1 session	3 sessions	5 sessions
SESSIONS
BAYESIAN-MINING VS. BAYESIAN-MINING
(3 issues)
Figure 9: 3-issue Opponent vs. Bayesian-Mining
0.9 0.3 0.7 0.6 | 0.5 3 0.4 0.3 0.2 0.1 0
0.9 -0.8 0.7 -0.6 -| 0.5 1 0.4 0.3 0.2 -0.1 0 -
.èr 0.5
0.9 -0.8 -0.7 -0.6 -0.5 -0.4 -0.3 -0.2 -
ABMP VS. BAYESIAN-MINING
(5 issues)
0.9 T-_	_	_-r
0.8--— -1-----
0.7-----=.
0 6--« --A---
nm
1 session	3 sessions	5 sessions
SESSIONS
Trade-OffVS. BAYESIAN-MINING [5 issues]
M
ZZl Rounds ♦ Ua -■-Ub
1 session	3 sessions	5 sessions
SESSIONS
Bayesian VS. BAYESIAN-MINING [5 issues]
mm
1 session	3 sessions	5 sessions
SESSIONS
25 20
15 ¡S c
10 I
5 0
3 Rounds Ua Ub
MINING VS. BAYESIAN-MINING [5 Issues]
1 session	3 sessions
SESSIONS
MINING VS. MINING
(5 issues)

1 session	3 sessions	5 sessions
SESSIONS
BAYESIAN-MINING VS. BAYESIAN-MINING
(5 issues)
0.8 -0.6 -0.4 -0.2 -O -
m
w
1 session	3 sessions 5 sessions
SESSIONS
Figure 10: 5-issue Opponent vs. Bayesian-Mining
ORDER STATISTICS BAYESIAN-MINING.
Infoimatica 35 (2011) 123-137 133
0.89 -0.88 -0.87 -0.86 -M 0.85 -S 0.84 -=> 0.83 -0.82 -0.81 -0.8 -
0.91 -0.9 -0.89 -0.88 -£ 0.87 -3 0.86 0.85 -0.84 -0.83 -0.82 -
0.94 0.92 0.9 . 0.88 0.86 0.84 0.82 0.8 0.78
ABMP VS. BAYESIAN-MINING
(6 Issues)
			r___—	
	♦ i	u	■U	♦ —1
I Rounds * Ua -«-Ub
3 sessions SESSIONS
Trade-Off VS. BAYESIAN-MINING
(6 issues)
3 sessions SESSIONS
Bayesian VS. BAYESIAN-MINING (6 issues)
I Rounds » Ua ■S-Ub
3 sessions SESSIONS
MINING VS. BAYESIAN-MINING
(6 issues)
MINING VS. MINING
(6 issues)
SESSIONS
BAYESIAN-MINING VS. BAYESIAN-MINING
(6 issues)
1 session	3 sessions	5 sessions
SESSIONS
0.7 0.6 0.5 = 0.4 S 0.3 0.2 0.1 0
0.8 0.7
0.6 * 05
8 0.4 = 0.3 0.2 0.1
0.8 0.7 0.6 0.S 0.4 0.3 0.2 0.1 0
ABMP Vs Bayesian-Mining [10 issues]
120 100 80 60
40 1 20 0
ïRounds -Ua Jb
sessios
Trade-OFF Vs. Bayesian-Mining [10 issues]
120 100
DRounds Ua Ub
3 session sessions
Bayesian VS. Bayesian-Mining [10 issues]
1 Rounds -Ua -Ub
sessions
Mining VS Bayesian-Mining [10 issues]
80 70 60
50 % 40 I 30 ê 20 10 0
3 Rounds -Ua Ub
1 session
3 session
5 session
Mining VS Mining [10 issues]
I Rounds -Ua Jb
1 session 3 session 5 session
Bayesian-Mining VS Bayesian-Mining [10 issues]
]Rounds -Ua Ub
3 session sessions
Figure 11: 6-issue Opponent vs. Bayesian-Mining
Figure 12: 10-issue Opponent vs. Bayesian-Mining
134 Informatica 35 (2011) 123-137
S.AbdelRahman et al.
	3-issue	5-issue	6-issue	10-issue
ABMP	1.085	1.269	0.843	1.58
Trade-off	1.250	1.315	1.260	2.68
Bayesian	1.618	1.571	1.703	3.03
Mining	1.629	1.568	1.581	2.213
Bayesian-Mining	2.500	3.443	3.750	8.622
Table 7: Average Sensitivities for all strategies
The negotiation cost is presented by the number of rounds and increase in utility. It should be noticed that single session experiments are the baseline to compare all agent strategies (Figures 5, 6, 7and 8). Additionally, in all multi-session experiments (Figures 9, 10, 11 and 12), the curves of all existing agent strategies, except for our proposed strategy, are presented only by points as they never have previous session knowledge to shorten the negotiation rounds thus the related experiments are independent. To sum up the results, the following points may be stated.
•	In all Bayesian-mining experiments, the agent wins its opponent from the first session. It gains more experience through negotiation steps and sessions such that gradually its utility is increased and the session rounds are decreased. For example, when Agent B follows Bayesian-mining and plays against an opponent Agent A which follows ABMP on 5-issue data set (Figure 10), Agent B utilities outcomes are (0.825, 0.83, 0.842) and the game session rounds are (35, 25, 17) in 1, 3 and 5 sessions respectively. Moreover, when the opponent agent A is Bayesian on 6-issue data set (Figure 11), Agent B utilities are (0.9125, 0.92, 0.92566) and the game session rounds are (17, 15, 13) in 1, 3 and 5 sessions respectively. One may notice that the first session between these parties lias 17 rounds only, which are less than 29 rounds of Bayesian (Agent A) vs. Bayesian (Agent B) single session experiment (Figure 7).
•	All other opponents (agent A) gain from playing with a Bayesian-mining agent (agent B). For example, agent A which follows ABMP (Figure 6) on 5-issue data set gets session rounds (75, 57, 43, 35) vs. Agent B which follows ABMP, Trade-Off, Bayesian, Bayesian-mining respectively. Also, the Trade-Off fastest single-session agreements (Figures 5, 6 and 7) occurred with the Bayesian-mining agent; 9 session rounds (3-issue data set) and 25 session rounds (5-issue and 6-issue data set).
•	The Bayesian-mining agent outcomes (agent B) in all its experiments on 3-issue, 5-issue, 6-issue and 10-issue data sets effectively prove its principles.
•	It is illustrated that the Bayesian-mining approach lias less offers to reach rapidly the final agreement and the final utility. In most cases, especially in 10-issue experiments, it raises the opponent
utilities. The Bayesian-mining approach works with larger number of sessions having several issues as the accumulated knowledge becomes valuable.
•	It is noticed that in terms of the overall negotiation quality and number of proposals exchanged to reach an agreement, the Bayesian-mining approach outperformed the other strategies. This confirmed the intuition that building mining and learning capability into agents help the agents to work more accurate with its opponent with better performance and less expensive process.
7.2.3 Sensitivity analysis
The sensitivity analysis is interested only in the negotiation intra-transaction. Table 7 summarizes the average sensitivity for all negotiation strategies used in this research. Figures 13, 14, 15 and 16 illustrate the values of this study for all the negotiation experiments.
The average sensitivity for the Bayesian-mining strategy is greater than all other strategies, which is also influenced by the preferences' alternatives of each kind of issue (Table 7). In 3-issue experiments, the sensitivity increment ratio between Bayesian-mining (2.50) and the second highest sensitivity, i.e. Mining approach, (1.629) is 53%. In 5-issue experiments, the sensitivity increment ratio between Bayesian-mining (3.443) and second highest sensitivity, i.e. Bayesian approach, (1.571) is 119%. In 6-issue experiments, the sensitivity increment ratio between Bayesian-mining (3.750) and the second highest sensitivity, i.e. Bayesian approach, (1.703) is 120%. In all 10-issue experiments, the sensitivity increment ratio between Bayesian-mining (8.622) and the second highest sensitivity, i.e. Bayesian approach (3.03) is 184%. Figures 13, 14, 15 and 16 show that the sensitivity has increased after the first session due to the nature of the Bayesian-mining strategy which ranks the proposed offers during the session at the end of each session; the higher sensitivity value means that the agent who owns the related strategy has more information about the behaviour and the weights of preferences which the opponent gives to the issues.
In the sensitivity deep analysis, it can be found that for 3-issue, the Bayesian-mining approach sensitivity is between 2 and 4, but for other agent strategies, the sensitivity is between 0.667 and 2. For 5-issue, the Bayesian-mining approach is between 1.4 and 6, but for other agent strategies, the sensitivity is between 1.0 and 2.33. For 6-issue, the Bayesian-mining approach sensitivity is between 2.143 and 7, but for other agent strategies, the sensitivity is between 0.5 and 2.50. For 10-issue, the Bayesian-mining approach strategy is between 5.824 and 13, but for other agent strategies, the sensitivity is between 0.915 and 4.058.
To sum up the sensitivity results, the following points should be clarified:
•	Increasing the issues number leads to increasing the sensitivity values of all strategies, because the
ORDER STATISTICS BAYESIAN-MINING...
ability to select among great number of offers having many alternatives is increased.
•	The sensitivity is proportional to the agent rationality. Table 7 shows evidence that the descending rationality order would be Bayesian-Mining, Bayesian, Mining, Trade-off, and ABMP.
•	The sensitivity for the agent uses the Bayesian-mining strategy to the opponent in negotiation is more than any other strategy, which means that the agent outcomes are nearly closed to Pareto frontier.
•	If the agent has several history proposals, it has enough knowledge to be more sensitive and more close to the Pareto Frontier. Consequently, the proposed agent records most sensitive steps to its opponent.
•	The sensitivity feature is asymmetric; one agent may be sensitive to the other's preferences, but not vice-versa.
Figure 13: 3-issue Sensitivity Outcomes
Figure 14: 5-issue Sensitivity Outcomes
Informática 35 (2011) 123-137 135
				
	/			
	A-"			
	/\ A /' f			
Í	v V" J			
	/ ?			
				
				
	! s s s s s ! f 5 ; : : : ; ; ; j ;		i s s s s s s s s s s s s ; ; ;s ; ; ; ; ; ;	
Figure 16: 10-issue Sensitivity Outcomes 7.2.4 Class studies
In the class studies, Bayesian-mining sensitivity calculations, i.e. Fortunate Step, Selfish Step, Concession Step, Unfortunate Step, Nice Step, and Silent Step, are dependent on all historical bids. Hence, the selection of suitable bids which satisfy the conditions of these steps becomes almost granted. This may lead to more accurate/rational calculations than the other models' criteria. In this section, the study focuses on the effect of the presence of the Bayesian mining strategy in any agent (A or B) in the negotiation process.
The average unfortunate step over a negotiation trace decreases by 0.217 to 0.453 when the Bayesian-mining approach is included ( average of all cases of 3-issue, 5-issue, 6-issue and 10-issue experiments). However; the average unfortunate steps is between 0.431 and 0.531 when the Bayesian-mining approach is not included.
The average concession step is between 0.477 and 0.952 when the Bayesian-mining approach is included; however, the average concession step is between 0.475 and 0.78 when the Bayesian-mining approach is not included. Also the average fortunate step is between 0.056 and 0.424 when the Bayesian-mining approach is included while the average fortunate step is between 0.019 and 0.392 when the Bayesian-mining approach is not included.
In 5-issue experiments (Table 8), the average unfortunate steps over a negotiation trace decreases with using Bayesian-Mining. When Bayesian-mining approach is included, the average unfortunate step is 0.369, while the average unfortunate step is 0.444 when Bayesian-mining approach is not included. Also the average fortunate step is 0.262 when the Bayesian-mining approach is included while the average fortunate step is 0.182 when the Bayesian-mining approach is not included.
In 6-issue experiments (Table 8), the average unfortunate steps over a negotiation trace decreases with using Bayesian-Mining. When Bayesian-mining approach is included the average unfortunate steps is 0.365, while the average unfortunate steps is 0.528 when Bayesian-mining approach is not included. Also the average fortunate step is 0.224 when the Bayesian-mining approach is included while the average fortunate step is 0.106 when the Bayesian-mining approach is not included. Also the average concession step is 0.635
Strategy A VS. Strategy B [number of sessions] (5 discrete issues)
I? 000 5 000
Agent A i-Agent B

> > > >> > £ >>ssssssszzsssssssssszzsss5
136 Informatica 35 (2011) 123-137
S.AbdelRahman et al.
when the Bayesian-mining approach is included while the average concession step is 0.545 when the Bayesian-mining approach is not included.
Table 8: Averages of Some Class Studies
For 10-issue as illustrated in Table 8, the average unfortunate steps over a negotiation trace decreases with using Bayesian-Mining. When Bayesian-mining approach is included the average unfortunate steps is 0.294, while the average unfortunate steps is 0.473 when Bayesian-mining approach is not included. Also the average fortunate step is 0.409 when the Bayesian-mining approach is included while the average fortunate step is 0.375 when the Bayesian-mining approach is not included.
From the previous analysis, it is illustrated that the size of the unfortunate steps for an agent that uses the Bayesian-mining approach is lower than other agent strategies. The frequency size of the concession and fortunate steps for the Bayesian-mining agent is higher than other types of agent. Consequently, the Bayesian-mining agent, in most cases, performs the steps that increase its opponent's utility being sensitive to its opponent needs.
8 Conclusion and future work
This paper proposes an agent approach for automated multi-session multi-issue win-win competitive bilateral negotiation. The proposed approach exploits the historical and accumulated knowledge while negotiation advances between two competitive agents having the same number of issues, to select the suitable bid for both negotiating sides. In this research, the order statistics Bayesian-mining agent is used to estimate the opponent thinking, and then the enhanced trade-off is used to propose the counter-offer, reducing the processing cost in terms of number of rounds and increasing the chances of reaching an agreement with higher utilities for both competitive agents.
Extensive experiments are carried out to prove that the assumptions, hypothesis, and opponent modelling are effective. Furthermore, many proposed agent imperative features are verified. The proposed Bayesian-mining
agent is sensitive and rational. When the agent meets its opponent, both parties win since they reach the negotiation agreement fast. Moreover, the Bayesian-mining agent utility is increased while negotiation sessions advance. However, its opponent utility is dependent on the related opponent preferences. Further experiments are conducted on large-scale data sets having 10-issue data set. It is proved that the Bayesian-mining strategy is valid for scalable number of issues.
Handling continuous issues should be investigated in the future. Studying how to minimize the large number of offers before starting the negotiation process is another topic that needs further investigations. It is also needed to get benefit from the domain knowledge to spur the negotiation skilfully. Our approach is based on negotiation strategies among rational agents; it could be worth investigating how to handle cases when our rational agent negotiates with irrational or emotional agent.
Acknowledgement
The authors are deeply indebted to Prof. Atef AbdelMeneim who have thoroughly revised the proposed statistical approach; his valuable input has enriched our work.
References
[1]	T. Bosse, C.M. Jonker (2005). Human vs. Computer Behaviour in Multi-Issue Negotiation.
Proceedings of the 1st International Workshop on Rational, Robust, and Secure Negotiations in MultiAgent Systems, IEEE Computer Society Press, pp. 11-24.
[2]	T. Bosse, C.M. Jonker, L.V der Meij, V. Robu, J. Treur (2005). A System for Analysis of Multi-Issue Negotiation, Software Agent-Based Applications, Platforms and Development Kits, R. Unland, M. Klusch and M. Calisti, eds, Birkhaeuser Publishing Company, pp. 253-280.
[3]	L. Breierova, M. Choudhari (2001), An Introduction to Sensitivity Analysis, Massachusetts Institute of Technology MIT.
[4]	G. Casella, S. Fienberg, I. Olkin (1999). Mathematical Statistics A Unified Introduction, Springer-Verlag New York, Inc.
[5]	S. Chakrabarti, E. Cox. E. Frank, R.H. Giiting, J.H., X. Jiang, M. Kamber, S.S. Lightstone, T.P. Nadeau, R.E.N.D Pyle, M. Refaat, M. Schneider, T.J. Teorey, I.H. Witten, (2009). Data mining know it all, Elsevier Inc.
[6]	Y.M. Chen, P. Huang (2009). "Agent-based bilateral multi-issue negotiation scheme for e-market transactions", Elsevier Science Publishers B. V. Amsterdam, . The Netherlands, Volume 9, pp. 1057-1067.
[7]	R.M. Coehoorn, N.R. Jennings (2004). Learning an Opponent's Preferences to Make Effective Multi-Issue Negotiation Trade-Offs, Proc. of 6th International Conference on E-Commerce, pp. 5968.
	Bay esi an-Mining					
	Not included			Included		
Issues	Fortunate	Concession	Unfortunate	Fortunate	Concession	Unfortunate
10	0.375	0.673	0.473	0.409	0.828	0.294
6	0.106	0.545	0.528	0.224	0.635	0.365
5	0.182	0.541	0.444	0.262	0.580	0.396
3	0.041	0.522	0.448	0.231	0.552	0.363
ORDER STATISTICS BAYESIAN-MINING...
Informática 35 (2011) 123-137 137
[8]	H. Faiffa (2006). "THE ART & SCIENCE OF, NEGOTIATION", Belknap Press of Harvard University Press.
[9]	P. Faratin, C. Sierra, N. Jennings (2003). Using Similarity Criteria to Make Negotiation Trade-Offs in automated Negotiations, Journal of Artificial Intelligence, 142 (2), pp. 205-237.
[10]	P. Giudici (2005). Applied Data mining, John Willy & Sons, Ltd.
[11]	K. Hindriks, D. Tykhonov (2008), Towards a Quality Assessment Method for Learning Preference Profiles in Negotiation, The Tenth International Workshop on Agent Mediated Electronic Commerce (AMEC 2008).
[12]	K. Hindriks, D. Tykhonov (2008). Opponent Modeling in Automated Multi-Issue Negotiation Using Bayesian Learning, Proc. of 7th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS08), pp. 331-338.
[13]	K. Hindriks, C.M. Jonker, D. Tykhonov (2007). Negotiation Dynamics: Analysis, concession tactics, and outcomes, Intelligent Agent Technology, IAT '07. IEEE/WIC/ACM International Conference, 2-5 Nov. pp. 427-433.
[14]	RV. Hogg, A. Craig, J.W. McKean (2005). Introduction to Mathematical Statistics, Prentice Hall.
[15]	C.M. Jonker, J. Treur (2001). An Agent Architecture for Multi-Attribute Negotiation, Proc. of the 17th Int. Joint Conference on AI (IJCAI'01), pp. 1195-1201.
[16]	C.M. Jonker, V. Robu, J. Treur (2007). An Agent Architecture for Multi-Attribute Negotiation Using Incomplete Preference Information, Autonomous Agents and Multi-Agent Systems Journal, Springer Netherlands Publisher, Volume 15, pp. 221-252.
[17]	S. Kraus (2001). Automated Negotiation and Decision Making in Multiagent Environments, Springer-Verlag Berlin Heidelberg.
[18]	R.Y.K. Lau, O. Wong (2007). Mining Negotiation Knowledge for Adaptive Negotiation Agents in e-Marketplaces, Proceedings of the 40th Hawaii International Conference on System Sciences.
[19]	R.J. Lewicki, A. Hiam (2006). Mastering business negotiation: a working guide to making deals and resolving conflict, Published by Jossey-Bass A Wiley Imprint.
[20]	R. Lin, S. Kraus, J. Wilkenfeld, J. Barry (2006). An Automated Agent for Bilateral Negotiation with Bounded Rational Agents with Incomplete Information. ECAI 2006, pp. 270-274.
[21]	V. Narayanan, N.R. Jennings (2006). Learning to Negotiate Optimally in Non-stationary Environments, CIA 2006, LNAI4149, pp. 288-300.
[22]	J. Oesch, A. Galinsky (2003). First Offers in Negotiations: Determinants and Effects. 16th . limual 1.1 (/ Confcrcncc Melbourne, Australia.
[23]	J.R. Oliver (1997). "A Machine-Learning Approach to Automated Negotiation and Prospects for Electronic Commerce", Journal of Management
Information Systems. Vol. 13 No. 3, Winter pp. 83 - 112
[24]	S. Parsons, C. Sierra, N.R. Jennings (1998). Agents that reason and negotiate by arguing, Journal of Logic and computation, 8(3), pp. 261-292.
[25]	S.T. Rachev, J.S.J. Hsu, B.S. Bagasheva, F.J. Fabozzi, (2008). Bayesian Methods in Finance, John Wiley & Sons, Inc. Hoboken, New Jersey.
[26]	P. Tan, M. Steinbach, V. kumar (2006). Introduction to Data mining, Pearson Education, Inc.
[27]	D.A. Van Veldhuizen, G.B. Lamont (1998). Evolutionary Computation and Convergence to a Pareto Front, Morgan Kaufmann, pp. 221—228.
[28]	T. Velden, K.W. Carsten (2007). Person Perception in Negotiation: When Perceiving is (Not) for Doing (February 2, 2007). IACM 2007 Meetings Paper, Working Paper Series.
[29]	N. Vulkan N.R. Jennings (2000). Efficient Mechanisms for the Supply of Services in MultiAgent Environments, Int. Journal of Decision Support Systems, 28 (1-2). pp. 5-19.
[30]	L. Wang, X. Fu (2005). Data Mining with Computational Intelligence, Springer-Verlag Berlin Heidelberg.
[31]	M. Wooldridge (2005). An introduction to Multiagent Systems, John Wiley & Sons, ltd.
[32]	I. Zelic, I. Kononenko, N. Lavrac, V. Vuga (1997). Induction of decision trees and Bayesian classification, Journal of Medical Systems, Volume 21, Number 6, Springer Netherlands, pp. 429-444(16).
[33]	D. Zeng, K. Sycara, (1997). Benefits of Learning in Negotiation, in Proc. of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), Providence, RI, pp. 36-41.