A Deep Reinforcement Learning Approach to Concurrent Bilateral Negotiation

1 Introduction

We are concerned with the problem of learning a strategy for a buyer agent to engage in concurrent bilateral negotiations with unknown seller agents in open and dynamic e-markets such as E-bay 1 . Previous work in this context has mainly focused on heuristic strategies [Nguyen and Jennings, 2004; Mansour and Kowalczyk, 2014; An et al., 2006], some of which adapt to changes in the environment [Williams et al., 2012]. Different bilateral negotiations are managed in such strategies either through a coordinator agent [Rahwan et al., 2002] or by coordinating multiple dialogues internally [Alrayes and Stathis, 2013], but do not support learning which is our main focus. Other approaches use learning based on Genetic Algorithms (GA) [Oliver, 1996; Zou et al., 2014], but they require a huge number of trials for obtaining a good strategy, which makes them infeasible for online settings. Reinforcement Learning (RL)-based negotiation typically employ Q-learning [Papangelis and Georgila, 2015; Bakker et al., 2019] which does not support continuous actions. This is an important limitation in our setting because we want to learn how much to concede e.g. on the price of an item for sale, which naturally leads to a continuous action space. Consequently, the design of autonomous agents capable of learning a strategy from concurrent negotiations with other agents is still an important open problem.

∗Contact Author

1 https://www.ebay.com/

We propose, to the best of our knowledge, the first Deep Reinforcement Learning (DRL) approach for one-tomany concurrent bilateral negotiations in open, dynamic and unknown e-market settings. Our DRL-inspired model ANEGMA (Adaptive NEGotiation model for e-MArkets) allows the buyer to develop an adaptive strategy to effectively use against its opponents. Such opponents use fixed but unknown to the agent strategies during negotiations, giving rise to an environment with incomplete information. We choose deep neural networks as they provide a rich class of strategy functions to capture the complex decisions-making required.

Since RL approaches need a long time to find an optimal policy from scratch we pre-train our deep negotiation strategies using supervised learning (SL) from a set of examples. To overcome the lack of real-world data for the initial training, we generate synthetic datasets using the simulation environment in [Alrayes et al., 2016] and two well-known strategies for concurrent bilateral negotiation described in [Alrayes et al., 2018] and [Williams et al., 2012] respectively.

With this work, we empirically demonstrate three important benefits of our deep learning framework for automated negotiations: 1) existing negotiation strategies can be accurately approximated using neural networks; 2) evolving a pretrained strategy using DRL with additional negotiation experience yields strategies that even outperform the teachers, i.e., the strategies used for supervision; 3) buyer strategies trained assuming a particular seller strategy quickly adapt via DRL to different (and unknown) sellers' behaviours.

In summary, our contribution is threefold: we propose a novel agent model for one-to-many concurrent bilateral negotiations based on DRL and SL; we extend the simulation environment [Alrayes et al., 2016] to generate data and perform experiments that support agent learning for negotiation; and we run extensive experiments showing that our approach outperforms the existing strategies and produces adaptable agents that can transfer to a range of e-market settings.

2 RelatedWork

RL has been proposed as a learning mechanism for negotiation environments with incomplete information. A number of approaches use Q-learning, e.g. in contract negotiation [Rodriguez-Fernandez et al., 2019], however the state/action space in that work is not continuous as in ours. The work of [Bakker et al., 2019] uses tabular Q-learning to learn the bidding strategy by discretizing the continuous state/action space (not optimal for large state/action spaces as it may lead to the curse of dimensionality and loss of relevant information about the state/action domain structure). We avoid these issues by using a model-free actor-critic RL approach [Lillicrap et al., 2016].

The work of [Lewis et al., 2017] combines SL (Recurrent Neural Network (RNN)) and RL (REINFORCE [Williams, 1992]) to learn a strategy and linguistic skills by being trained on human negotiation dialogues. We also combine SL and RL but with the main focus to train the agent learn a bidding strategy from agent interactions governed by a negotiation protocol. In addition, we use Artificial Neural Network (ANN) for SL and the actor-critic model called DDPG [Lillicrap et al., 2016] for RL.

Independently of the approach, numerous works in the domain of bilateral negotiation rely on the Alternating Offers protocol [Rubinstein, 1982] as the negotiation mechanism, which, despite its simplicity does not capture many practical bargaining scenarios. We will be adopting the CONAN negotiation protocol shown in Fig. 1, that can support a wider range of practical negotiation applications.

3 The ANEGMAModel

3.1 Negotiation Environment

We consider e-marketplaces like E-bay where the competition is visible, i.e. a buyer can observe the number of competitors that are dealing with the same resource from the same seller. We assume the environment to be a single e-market m with P agents, with a non-empty set of buyers Bm and a nonempty set of sellers Sm - these sets need not be mutually exclusive. For a buyer b ∈ Bm and resource r, we denote with St b,r ⊆ Sm the set of sellers from market m which, at time point t, negotiate with b for a resource r (over a range of issues I). The buyer b uses |St b,r | negotiation threads, in order to negotiate concurrently with each seller ∈ St b,r . We assume that no agent can be both buyer and seller for the same resource at the same time, that is, ∀b, r, t. s ∈ St b,r =⇒ Sts,r = ∅. C t b,r = {b′ ̸= b ∈ Bm | St b′ ,r ̸= ∅} is the set of competitors of b, i.e. those agents negotiating with the same sellers and for the same resource r as that of b. However, it is possible that a seller, whom a buyer b is negotiating with, to accept a deal from a competitor buyer b′ ∈ C t b,r .

The class of concurrent bilateral negotiations that we study is governed by the negotiation protocol of Fig. 1. This protocol assumes an open e-market where agents can enter or leave the negotiation at their own will. A buyer b always starts the negotiation by making an offer whose start time is tstart . Any negotiation is for a resource r, since we index the negotiation thread with the seller's name s and the resource r, and can last for up to time tb, the maximum time b can negotiate for. The deadline for b is, thus, tend = tstart + tb, which for simplicity we assume for all resources being negotiated. Information about the deadline tb, Initial Price IPb and Reservation Price RPb is private to each b ∈ Bm. Each seller s also has its own Initial Price IPs, Reservation Price RPs and maximum negotiation duration parameter ts (which are not visible by other agents). The protocol is turn-based and allows agents to take actions from a pool Actions at each negotiation state (S1 to S5 - see Fig. 1), where Actions = {offer (x ), reqToReserve , reserve , cancel , confirm, accept , exit}. In S1, s can accept current b's offer and move to S3, or make a counter-offer and move to S2. In S2, b can accept s's offer (success), make a counter-offer and move to S1, or request to reserve and move to S4. In S3, b can confirm its offer (success), or request to reserve and move to S4. In S4, s can reserve and move to S5. In S5, b can accept (success). Either agent can exit the negotiation at any state.

3.2 ANEGMA Components

Our proposed agent negotiation model supports learning during concurrent bilateral negotiations with unknown opponents in dynamic and complex e-marketplaces. In this model, we use a centralized approach in which the coordination is done internally to the agent via multi-threading synchronization. This approach minimizes the agent communication overhead and thus, improve the run-time performance. The different components of the proposed model are shown in Fig. 2 and explained below.

Physical Capabilities

The sensors of the agent enable it to access an e-marketplace. They allow a buyer b to perceive the current (external) state of the environment st and represent that state locally in the form of internal attributes as shown in Table 1. Some of these attributes (NSr, NCr) are perceived by the agent using its sensors, some of them (IPb, RPb, tend) are stored locally in its knowledge base and some of the them (Sneg , Xbest , Tleft ) are obtained while interacting with other seller agents during a negotiation. At time t, the internal agent representation of the environment is st, which is used by the agent to decide what action at to execute using its actuators. Action execution then changes the state of the environment to st+1.

Learning Capabilities

The foundation of our model is a component providing learning capabilities similar to those in the Actor-Critic architecture as in [Lillicrap et al., 2016]. It consists of three subcomponents: Negotiation Experience, Decide and Evaluate.

Negotiation Experience stores historical information about previous negotiation experiences which involve the interactions of an agent with other agents in the market. Experience elements are of the form 〈st, at, rt, st+1〉, where st is the state of the e-market environment, at is action performed by b at st, rt is scalar reward or feedback received from the environment and st+1 is new e-market state after executing at.

Decide refers to a negotiation strategy which helps b to choose an optimal action at among a set of actions (Actions) at a particular state st. In particular, it consists of two different functions fc and fr. fc takes state st as an input and returns a discrete action among counter-offer, accept, confirm, reqToReserve and exit, see (1). When fc decides to perform a counter-offer action, fr is used to compute, given an input state st, the value of the counter-offer, see (2). From a machine learning perspective, deriving fc corresponds to a classification problem, deriving fr to a regression problem.

Evaluate refers to a critic which helps b learn and evolve the strategy for unknown and dynamic environments. It is a function of K (K < N) past negotiation experiences randomly selected. The learning process of b is retrospective since it depends on the feedback (or scalar rewards) obtained during classification (i.e. rt using (3)) and regression (i.e. r′t using (4)) from the e-market environment by performing action at at state st These rewards evaluate the discrete and continuous action of Decide respectively at time t . Our design of reward functions accelerate agent learning by allowing b to receive rewards after every action it performs in the environment instead of at the end of the negotiation.

In (3) and (4), Ub(x, t) refers to the utility of offer x (generated using (2)) at time t and calculated using Initial Price

(IPb), Reservation Price (RPb), agreement offer (x) and temporal discount factor (dt ∈ [0, 1]) [Williams et al., 2012] as defined in (5), assists b to negotiate without delay. The reward function r′t in (4) helps b learn that it should not offer more than what active sellers have already offered it. Ot is a list of preferred offers received from sellers s ∈ St b,r at time t, which b maintains during negotiation. In (3), "No Deal" means that the agent chooses to quit the negotiation.

In our experiments, the value of dt is set to 0.6. Higher the dt value, higher is the penalty due to delay.

4 Materials andMethods

4.1 Data Set Collection

In order to collect the dataset to train the ANEGMA agent using an SL model, we have used a simulation environment [Alrayes et al., 2016] that supports concurrent negotiations between buyers and sellers. The buyers use the strategies presented in [Alrayes et al., 2018] and [Williams et al., 2012], whereas the sellers use the strategies described in [Faratin et al., 1998]. We could have also collected training data using other buyer strategies for concurrent negotiation in the same setting as ours, or any real-world market data; however, to the best of our knowledge none of these were readily available. We have selected the input features of our dataset manually, and this set of features correspond to the agent's state attributes in Table 1. To avoid choosing overlapping features, we have applied the Pearson Correlation coefficient [Lee Rodgers and Nicewander, 1988] and ensured no correlation (with all correlation coefficients between -0.16 and 0.16; most are closer to 0) between the selected features.

4.2 Performance EvaluationMeasures

To successfully evaluate the performance of ANEGMA and compare it with other negotiation approaches, it is necessary to identify the appropriate performance metrics. For our experiments, we have used the following widely adopted metrics [Williams et al., 2012; Faratin et al., 1998; Nguyen and Jennings, 2004; Alrayes et al., 2018]: Average utility rate (Uavg), Average negotiation time (Tavg) and Percentage of successful negotiations (S%), which are described below:

• Uavg : Sum of all the utilities of the buyer averaged over the successful negotiations. (Ideal value: High(1.0))
• Tavg: Total time taken by the buyer (in milliseconds) averaged over all successful negotiations to reach the agreement. (Ideal value: Low(≈ 1000ms))
• S%: Proportion of total negotiations in which the buyer reaches an agreement successfully with one of the concurrent sellers. (Ideal value: High(100%))

Our main motive behind calculating the Uavg is to calculate the agent profit over only successful negotiations, hence we exclude the unsuccessful ones in this metric. We capture the (un)successful negotiations in a separate metric called S%.

4.3 Methodology

During our experiments, sellers and competitor buyers use fixed strategies that are initially unknown to the buyer. As these strategies are fixed, they will be learned by ANEGMA later, after a number of simulation runs. Thus after a number of negotiation simulation runs our environment can be considered fully-observable. Given our dynamic (i.e. agents leave and enter the market at any time) and episodic (i.e. the negotiation terminates at some point) environment, we use a model-free, off-policy RL approach which generates a deterministic policy based on the policy gradient method to support continuous control. Specifically, we use the Deep Deterministic Policy Gradient algorithm (DDPG), which is an actor-critic RL approach and generates a deterministic action selection policy for the buyer (see [Lillicrap et al., 2016] for more details). We consider a model-free RL approach because our buyer is more concerned with determining which action to take for a particular state rather than predicting a new state. This is because the strategies of sellers and competitor buyers are unknown. On the other hand, we consider the off-policy approach for efficient and independent exploration of continuous action spaces. Furthermore, instead of initializing the RL policy randomly, we use a policy generated by an ANN [Goodfellow et al., 2016] due to its compatibility with DRL in order to speed up and reduce the cost of the RL process. To reduce over-fitting and generalization errors, we apply regularization techniques (dropout) during the training of ANN.

5 Experimental Setup and Results

Our experiments are based on the following hypotheses.

Hypothesis A: The Market Density (MD), the Market ratio or Demand/Supply Ratio (MR), the Zone of Agreement (ZoA) and the Buyer's Deadline (tend) have a considerable effect on the success of negotiations. Here,

• MD is the total agents in the e-market at any given time dealing with the same resource as that of our buyer.
• MR is the ratio of the total number of buyers over the sellers in the e-market.
• ZoA refers to the intersection between the price ranges of buyers and sellers for them to agree.

In practice, buyers have no control over these parameters except the deadline, which can be decided by the user or constrained by a higher-level goal the buyer is trying to achieve.

Hypothesis B: The ANEGMA buyer outperforms SL, CONAN, and Williams' negotiation strategies in terms of Uavg , Tavg and S% in a range of e-market settings.

Hypothesis C: An ANEGMA buyer if trained against a specific seller strategy, still performs well against other unknown seller strategies. This shows that the ANEGMA agent behaviour is adaptive in that the agent transfers knowledge from previous experience to unknown e-market settings.

5.1 Design of the Experiments

To carry out our experiments, we have extended the simulation environment RECON [Alrayes et al., 2016] with a new online learning component for ANEGMA.

Seller Strategies

For the purpose of training our SL model and conducting large-scale quantitative evaluations, we have used two groups of fixed seller strategies developed by Faratin et al. [1998]: Time-Dependent (Linear, Conceder and Boulware) and Behaviour-Dependent (Relative tit-for-tat, Random Absolute tit-for-tat and Averaged tit-for-tat). During experimentation, the same private deadlines were used for both sellers and buyer. Other parameters such as IPs and RPs are determined by the ZoA parameter, as shown in Table 2.

Simulation Parameters

We assume that the buyer negotiates with multiple sellers concurrently to buy a second-hand laptop (r = Laptop) based only on a single issue Price (I = {Price}). We stress that the single-issue assumption is not unrealistic for e-markets like e-Bay, where sellers advertise a product with a fixed set of issues (e.g. Lenovo, 16GB RAM, 250GB HDD, i7 processor) and the only issue being negotiated is price. The simulated market allows the agents to enter and leave the market at their own will. The maximum number of agents allowed in the market, the demand/supply ratio, the buyer's deadline and the ZoAs are simulation-dependent.

As in [Alrayes et al., 2018], three qualitative values are considered for each parameter during simulations, e.g., High (H), Average (A) and Low (L) for MD or Long (Lg), Average (A) and Short (Sh) for tend. Parameters are reported in Table 2. The user can select one of such qualitative values for each parameter. Each qualitative value corresponds to a set of three quantitative values, of which only one is chosen at random for each simulation (e.g., setting H for parameter MD corresponds to choosing at random among 30, 40, and 50). The only exception is parameter ZoA, which maps to a range of uniformly distributed quantitative values for the seller's initial price IPs and reservation price RPs (e.g., selecting A for ZoA leads to a value of IPs uniformly sampled in the interval [580, 630]). Therefore, the total number of simulation settings is 81, as we consider 3 possible settings for each of MD, MR, tend , and ZoA (see Table 2).

5.2 Empirical Evaluation

Hypothesis A (MD, MR, ZoA and tend Have Significant Impact on Negotiations)

We experimented with 81 different e-market settings over 500 simulations using the CONAN buyer strategy. Both timedependent and behaviour-dependent seller strategies were considered for each setting. These experiments suggest that MD and ZoA have a considerable effect on S% (Fig. 3). We observe that the agents reach more negotiation agreements when MD is low. Also, there is not much difference in the agreement rate for 60% and 100% ZoA when MD is low. The small number of successful negotiations for 10% ZoA is not unexpected since only a minority of agents is willing to concede more in such a small ZoA. On the other hand, MR and tend have, according to our experiments, a comparably minor impact on the negotiation success (only some effect of MR on S% is observed under low MD against behaviour-dependent strategies) 2 . Moreover, we performed significance tests (i.e. Z-tests for independent proportions) for all the relevant pairwise comparisons. All the differences in the proportions of successful runs were found significant at p < 2.12E - 13. 3

2 See [Bagga et al., 2020] for detailed results on MR.

3 For each ZoA=H,A,L, we tested (MD=H vs MD=A) and (MD=A vs MD=L). For each MD=H,A,L, we tested (ZoA=L vs

Hence, these results support our hypothesis.

Hypothesis B (ANEGMA Outperforms SL and CONAN)

We performed simulations for our ANEGMA agent in low MD, 60% ZoA4 , high MR and a long tend because these settings yielded the best performance in terms of S% in our experiments for Hypothesis A. We used these settings against Conceder Time Dependent and Relative Tit for Tat Behaviour Dependent seller strategies.

Firstly, we collected training data for ANN using two distinct strategies for supervision, viz. CONAN [Alrayes et al., 2018] and Williams [Williams et al., 2012]. Both were run for 500 simulations and with the same settings. Table 3 compares the performances of CONAN's and Williams' models. CONAN outperforms Williams' strategy in these settings.

Then, the resulting trained ANN models - called ANN-C and ANN-W respectively - were used as the initial strategies in our DRL approach (based on DDPG), where strategies evolved using negotiation experience from additional 500 simulations. In the remainder, we will abbreviate this model by ANEGMA(SL+RL).

Finally, we used test data from 101 simulations to compare the performance of such derived ANEGMA(SL+RL) buyers against CONAN, Williams' model, ANN-C, ANN-W, and the so-called ANEGMA(RL) model, which used DDPG but initialized with a random strategy.

According to our results shown in Table 4, the performance of ANN-C is comparable to that of CONAN (see Table 3). We observe the same for ANN-W and the William's strategy. So, we conclude that our approach can successfully produce ANN strategies which are able to imitate the behaviour and performance of the CONAN and Williams' models (the training accuracies were in the range between 93.0% and 98.0%).

Even more importantly, the results demonstrate that ANEGMA(SL+RL)-C (i.e. DDPG initialized with ANNC) and ANEGMA(SL+RL)-W (i.e. DDPG initialized with ANN-W) improve on their respective initial ANN strategies obtained by SL, and outperform ANEGMA(RL) initialized at random, see Table 4. This proves that both the evolution of the strategies via DRL and the initial supervision are beneficial. Furthermore, ANEGMA(SL+RL)-C and ANEGMA(SL+RL)-W also outperform the existing "teacher strategies" (CONAN and Williams) used for the initial supervision and hence can improve on them, see Table 3.

ZoA=A) and (ZoA=L vs ZoA=H).

4 See [Bagga et al., 2020] for more results with 100% ZOA.

Hypothesis C (ANEGMA is Adaptable)

In this final test, we evaluate how well our ANEGMA agents can adapt to environments different from those used at training-time. Specifically, we deploy strategies trained using Conceder Time Dependent opponents into an environment with Relative Tit for Tat Behaviour Dependent opponents, and vice-versa. The ANEGMA agents use experience from 500 simulations to adapt to the new environment. Results are presented in Table 5 and show clear superiority of the ANEGMA agents over the ANN-C and ANN-W strategies which, without online retraining, cannot maintain their performance in the new environment. This confirms our hypothesis that ANEGMA agents can learn to adapt at run-time to different unknown seller strategies.

Further Discussion

Pondering over the negative average utility of ANEGMA(RL) (Table 4), recall that we define utility as in Equation (5) but without the discount factor. Therefore, if an agent concedes a lot to make a deal, it will collect negative utility. This is precisely what happens to the initial random (and inefficient) strategy used in ANEGMA(RL). The combination of SL and DRL prevents this problem as it uses an initial pre-trained strategy which is much less likely to incur negative utility. For the same reason, we observe a consistently shorter Tavg for ANEGMA(RL) caused by a buyer that concedes more to reach the agreement without negotiating for a long time with the seller. Hence, a shorter Tavg alone does not generally imply a better negotiation performance. An additional advantage of our approach is that it alleviates the common limitation of RL, namely, that an RL agent needs a non-trivial amount of experience before reaching satisfactory performance.

6 Conclusions and FutureWork

We have proposed ANEGMA, a novel agent negotiation model supporting agent learning and adaptation during concurrent bilateral negotiations for a class of e-markets. An ANEGMA agent derives an initial neural network strategy via supervision from well-known negotiation models, and evolves the strategy via DRL. We have empirically evaluated the performance of an ANEGMA buyer agent against fixed but unknown to the agent seller strategies in different e-market settings. We have shown that ANEGMA outperforms well-known "teacher strategies", the strategies trained with SL only and those trained with DRL only. Crucially, our model has also exhibited adaptive behaviour in that it can transfer to environments with unknown sellers, viz., sellers that use different strategies from those used during training.

In the future, we will study complex domains with bilateral negotiations on multiple issues against adaptive opponents.

Acknowledgements

We would like to thank Emanuele Uliana, Benedict Wilkins, Joel Clarke, and the anonymous reviewers for their useful suggestions on a previous version of this paper.