POPPONENT: Highly accurate, individually and socially efficient opponent preference model in bilateral multi issue negotiations (Extended Abstract)

1 Introduction

Negotiation is the science and art of resolving any kind of disputes and reaching consensus among human parties. In an automated bilateral multi-issue version of negotiations, intelligent computer agents engage in a cooperative process on behalf of their beneficiaries with different and sometimes contradicting interests, with the objective of achieving an agreement on one or more issues. Recently, with the emergence of ANAC (an annual international Automated Negotiating Agents Competition) [Baarslag et al., 2012; Fujita et al., 2013], many new negotiation strategies have been developed. Most of the existing sophisticated negotiation strategies typically consist of a set of fixed modules. In general, three main components are distinguished in a negotiating agent which work together within a BOA framework to accomplish the whole negotiation task [Baarslag et al., 2014]: Bidding Strategy (BS), which decides which offer will be sent to the opponent as the next proposal, Opponent Model (OM), which constructs a model of the preference profile of the opponent through a learning technique, and Acceptance Strategy (AC), which receives the incoming offer from the opponent and the outgoing offer chosen by the bidding strategy component, and determines whether the incoming offer is acceptable for the agent or not.

∗This paper is an extended abstract of an article in the Artificial Intelligence journal [Zafari and Nassiri-Mofakham, 2016b].

Despite the variety in opponent modelling techniques, most of the current models rely on a small and common set of learning techniques [Baarslag et al., 2016]. Moreover, since in a single negotiation session all bids (i.e., training examples) are not available at the same time, traditional learning techniques are not easily applied. An opponent model that is able to learn incrementally and update itself once the new training examples (i.e., offers) arrive during a negotiation session is of necessity. Another problem in the negotiation setting is that the training instances lack the output variable (i.e., the variable which contains the utility values of the received bids in the opponent's view). Therefore, specific opponent models are required that are capable of modeling the preferences of the opponent with no need for the value of the output variable. In order to overcome this limitation, all the existing opponent models use a subset of assumptions to extract the preferences of the opponent [Zafari and NassiriMofakham, 2016b]. Another difficulty with modeling an opponent's preferences in bilateral negotiations is related to the time factor. The post event analysis of ANAC tournaments also confirms that the computational complexity of the opponent models and the poor accuracy are the two main factors that degrade the performance of the agents applying these models [Baarslag, 2016]. In particular, the time factor is of paramount importance in online opponent models. In these models, the participating agents usually exchange a limited number of offers before the negotiation deadline is met, therefore, they do not contain enough information to accurately train an opponent model [Hindriks and Tykhonov, 2008;

Sycara and Zeng, 1997]. Consequently, the ability of the model to extract the most information possible from the training bids it receives is highly essential. Therefore, a proper opponent model should function based on the least assumptions, be efficient, extract the most information fromminimum number of bids, and embrace incremental training capability. To learn the issue weight values and individual utility function captured by opponent models, a two layered architecture would be essential. To overcome the aforementioned difficulties, in this paper, a new opponent preference model based on perceptron units is proposed in bilateral multi issue negotiation domains. Moreover, to be more applicable in real world negotiations, fewer and more realistic assumptions than those of the state of the art models are applied in this study. This is obtained by proposing an opponent model named POPPONENT, based on an adapted version of the standard gradient decent search [Zafari and Moser, 2016; Zafari and Moser, 2017b; Zafari and Moser, 2017a] (named the Multi Bipartite Gradient Decent Search). The model shows great success in the practical AI area of modelling the opponent preferences in bilateral multi issue negotiations with incomplete information, and the proposed Multi Bipartite Gradient Decent Search method used to train the model can be conveniently adopted in the similar AI problems.

2 Negotiation Setting

The negotiation setting here is in accordance with the setting employed by the state of the art models in the field of bilateral automated negotiations and the setting of the ANAC 2010-2013 [Baarslag et al., 2012; Fujita et al., 2013; Lin et al., 2014; Baarslag et al., 2013; Yaakov and Ilany, 2015; Zafari et al., 2015] 1 . Automated agents alternatively exchange offers and compete against each other to reach a joint agreement on a set of issues in bilateral negotiations. The issues and possible values for each issue constitute a domain. For each domain there could be two preference profiles (one for each side of the negotiation) which together with the domain construct a negotiation scenario. The interaction between negotiating parties is regulated by a negotiation protocol that defines the rules of how and when proposals can be exchanged. In this setting, the alternating offers protocol is applied [Rubinstein, 1982]. Negotiation is bilateral, that is, exactly two parties are negotiating over one or a set of issues. Each issue is associated with a set of possible values. The agents repeatedly exchange offers in successive rounds, so as to reach a mutually acceptable outcome. The negotiation deadline is reached after a specified number of N rounds are passed. This type of negotiation setting is commonly referred to as a round based setting. Each agent tries to take advantage of the other party for gaining a maximum utility for its own. A negotiation break-off causes both negotiating parties to obtain their reservation values. Therefore, the agents try to reach an agreement before the deadline. A negotiation session takes place in a negotiation scenario, which consists of a negotiation domain (or, alternatively, an outcome space) and two preference profiles (or, alternatively, utility space) one for each negotiating agent. The negotiation domain W specifies all possible offers -→w that the agents can send or receive. Each offer or possible outcome is a vector < w1, ...,wn >, where each component is the mapping of every issue i to a value wi ∈ {vi1, ,vimi }, where, mi is the number of possible values for issue i, i = 1, ...,n [Fujita et al., 2013]. A preference profile {< -→w ,U(-→w ) > |-→w ∈ W}, on the other hand, consists of a utility function U(-→w ) which maps each possible offer -→w ∈ W to a value in the [0,1] range based on the overall relative value of that offer for the agent. In multi-issue negotiations, the common assumption is that the utility of an offer can be computed as a weighted sum of the utilities associated with the values for each issue [Nassiri-Mofakham et al., 2008; Nassiri-Mofakham et al., 2009]. Accordingly, in the negotiation setting here, the agents use the linear additive utility function shown in Equation (1) , defined by a set of weights wi, and the corresponding evaluation functions or evaluation values evali(wi), i = 1, ...,n for the issue value wi of a given offer -→w .

1 In 2014, another setting has been added for negotiations under nonlinear utilities and in ultra large domains [Zafari and NassiriMofakham, 2016a]. ANAC 2015 and 2016 considered multi-party negotiations

Unlike the negotiation domain which is publicly known for both the negotiating parties, the preference profile is private for each agent, so the agents are not aware of the weights and evaluation values associated with the preference profile of one another. This negotiation setting is online, meaning that the agent is only allowed to use the offers exchanged during a single negotiation session to model the preferences of the opponent. Unlike offline opponent models, where negotiation information from different negotiation sessions is used, in online models [van Krimpen et al., 2013] no history of the previous negotiations is provided for the opponent model.

3 POPPONENT Algorithm

The preference profile of the opponent in linear scenarios is learnt using the multi bipartite incremental gradient descent search [Zafari and Nassiri-Mofakham, 2016b]. This algorithm learns the issue priorities or weight values w OP 1 through w OP n and the evaluation values eval OP i (wi) for all possible values wi ∈ vi1, ...,vimi (where, mi is the number of possible values for issue i) and all negotiation issues i (i = 1, ...,n) in that negotiation domain.

This proposed algorithm implements the multi bipartite incremental gradient descent search and applies two parameters of h and N as the input. Parameter h represents the learning rate which determines the step size in the gradient descent search. Parameter N represents the number of training repeats for each training instance. This algorithm includes two separate functions of initializer and updater. The first function is invoked just once when the model is generated and the essential parameters of the proposed model, most importantly the preference profile of the opponent (that is, the issue weights w OP i and evaluations eval OP i (wi) for issue values) is initialized. By trying different initial points, it is realized that 0.5, the midpoint in the hypothesis space, is the best point for initializing eval OP i (wi) values for each wi ∈ vi1, ...,vimi , i = 1, ...,n

(Algorithm: line 13). Similarly, for the weight values wi, equal weights 1 n are chosen for all issues (Algorithm: line 14). The second function receives an offer vector -→w which specifies the issue values for all the negotiation issues of a new offer recently received from the opponent. That is, as soon as a new offer is received from the opponent, this function is invoked to update the model based on this newly received bid. It updates the estimated preference profile of the opponent by adjusting eval OP i (wi) and wi values (Algorithm: Lines 18 and 21). Whenever a new offer is received from the opponent, the perceptron learning delta rules (Algorithm: lines 18 and 21) are repeated N times. The EstimatedUtility OP (w) is a function which receives an offer as the input and returns the estimated utility value of that offer in the opponent's utility space as the output. In this algorithm, instead of updating each eval OP i (wi) and w OP i value after calculating all Dwi and Deval OP i values when all training examples are met, each eval OP i (wi) and w OP i value is modified using training delta rules right after each single training instance is met in an incremental manner (Algorithm: Lines 18, 21). Therefore, this algorithm can easily be applied in more realistic negotiation scenarios in which training examples (opponent offers) are gradually met one at a time. The POPPONENT algorithm is as follows:

This proposed model is a supervised algorithm, thus it needs output labels for training instances. The problem of preference modelling in bilateral multi issue negotiations through supervised learning methods can be separated into two sub-problems: 1) estimating the utility values of the opponent's offer history (the history of the offers received from the opponent through the negotiation session) and 2) extracting the estimated utility function (or the preference profile) of the opponent from the opponent's offer history. By solving the first problem, now the opponent's offer history contains all the estimated offer utilities for each offer in the opponent's offer history. The EstimatedUtility OP (-→w ) function which deals with the first sub-problem, can be estimated according to the perceived bidding behavior of the opponent. In this article, four different values - three constant (0.6, 0.8, and 1) and one adaptive method (named P6, P8, P1, AP, respectively) are applied in order to estimate the utilities of the offers proposed by the opponent. For the fourth value, we use the adaptive method where the agent estimates the bids that the opponent will offer in future, based on the opponent's bid history [Ikrashi and Fujita, 2014; Witten et al., 2016]. The computational complexity of POPPONENT Algorithm is linear (O(n)).

4 Experiments

To evaluate the proposed model, two separate experimental settings are applied for assessing its accuracy and performance, in real world negotiation examples, compared to the available opponent models from Genius repository [Lin et al., 2014]. In the following sections, we present the experimental results obtained in these two experimental settings (for the details, please see [Zafari and Nassiri-Mofakham, 2016b]). The models used in these experiments are abbreviated in Table 1.

4.1 Experiment I

The first setting evaluates the accuracy of POPPONENT model through the Pearson Correlation measure. The experimental setting applied by [Baarslag et al., 2013] for automated bilateral multi issue negotiations is applied to evaluate the accuracy of POPPONENT model versus the state of the art opponent models. According to this setting, 5 variations of POPPONENT are compared with a total of 15 opponent models. In this experiment, the agents employing these opponent models negotiate against a category of opponent agents with different bidding strategies in a number of negotiation domains. The average accuracies of top performing opponent models against all opponent agents are depicted in Fig. 1, where at the perfect information state (PP), the proposed model outperforms the state of the art models by a large margin. As observed, the other three variations of POPPONENT (i.e., P6, P8, and P1 except PP) outperform the state of the art models with respect to the average accuracy over all opponents.

4.2 Experiment II

In the second Experiment, the proposed model is evaluated by measuring the real performance of the agents applying this model in 7 domains (Table 2) of real world experimental negotiation scenarios. A similar setting to the one applied by the ANAC organizers [Baarslag et al., 2013] is designed here. To accomplish this, a BOA framework is applied to embed each opponent model into an agent framework, the bidding strategy of which (together with its associated acceptance strategy) is chosen from the state of the art agents. In this setting, two sets of negotiation agents compete with each other in a tournament. The first set of agents are constructed using the top performing ANAC agents and some of the classic agents without an opponent component, and the second set is comprised of the same set of agents, except that they are equipped with one of the opponent models from Table 1. Then, the average performance of each opponent model is assessed by measuring the average performance of the agents that employed that opponent model. Six performance measures of Avg. utility, Avg. time of agreement, Avg. Pareto Distance of Agreement, Avg. Kalai Distance of Agreement, Avg. Nash Distance of Agreement and Avg. Percentage of Pareto Bids are applied for this purpose. The results of the Experiment II indicate that POPPONENT is the most accurate model compared with other models available. This is consistent with the results of the first experiment, where it is found that the accuracy of POPPONENT exceeds state of the art models. Moreover, we also found that POPPONENT (AP) and IXF models are the only two models which can outperform all other models in at least one domain with respect to all performance/accuracy measures. Both Experiments I and II reveal that POPPONENT is undoubtedly the most accurate model among all its counterparts. The experiments also revealed that POPPONENT achieves the highest performance in the Grocery domain for the average utility measure (through AP), the highest performance in the Travel and ItexVsCypress domains for the average time of agreements measure (through AP), the highest performance in the ItexVsCypress for the Nash and Kalai distance measures (through AP), the highest performance in the Grocery domain for the Pareto distance measure (through AP), the best performance in the Supermarket, Travel, Thompson, Energy, Camera, and ItexVsCypress, for the Pearson Correlation measures (through P1), and the best performing model in the Thompson domain for the percentage of Pareto bids measure (through P1). These results are tabulated in Tables 2 and 3.

(e)

Table 3: Average performance of models in terms of a) Utility, b) Nash Distance, c) Kalai Distance, d) Pareto Distance, and e) Pearson Correlation in Experiment II

5 Conclusion

In this paper, a new opponent preference model called POPPONENT is proposed. The experiments also reveal that the accuracy of P1, P6, and P8 exceeds the accuracy of the most accurate state of the art model. Evaluating the performance of POPPONENT also indicated that it overcomes the most accurate state of the art opponent models. In particular, the results indicated that POPPONENT works better in medium to large and more distributed negotiation domains and overcomes all the state of the art models in at least one domain for all the measures.