Learning about the opponent in automated bilateral negotiation: a comprehensive survey of opponent modeling techniques

Negotiation is a process in which parties interact to settle a mutual concern to improve their status quo. Negotiation is a core activity in human society, and is studied by various disciplines, including economics [147, 158], artificial intelligence [69, 91, 106, 107, 118, 182], game theory [19, 69, 91, 118, 120, 147, 172], and social psychology [170].

Traditionally, negotiation is a necessary, but time-consuming and expensive activity. Therefore, in the last two decades, there has been a growing interest in the automation of negotiation and e-negotiation systems [18, 71, 91, 99, 107], for example in the setting of e-commerce [20, 79, 105, 126]. This attention has been growing since the beginning of the 1980s with the work of early adopters such as Smith’s Contract Net Protocol [186], Sycara’s persuader [189, 190], Robinson’s oz [164], and the work by Rosenschein [168] and Klein [102]. The interest is fueled by the promise of automated agents being able to negotiate on behalf of human negotiators and to find better outcomes than human negotiators [20, 55, 89, 121, 126, 149, 192].

The potential benefits of automation include reduced time and negotiation costs resulting from automation [33‐35, 126], a potential increase in negotiation usage when the user can avoid social confrontation [27, 126], the ability to improve the negotiation skills of the user [80, 121, 125], and the possibility of finding more interesting deals by exploring more promising portions of the outcome space [80, 126].

One of the key challenges for a successful negotiation is that usually only limited information is available about the opponent [143]. Despite the fact that sharing private information can result in mutual gains, negotiators are unwilling to share information in situations with a competitive aspect to avoid exploitation by the other party [50, 75, 81, 158]. In an automated negotiation, this problem can be partially overcome by deriving information from the offers that the agents exchange with each other. Taking advantage of this information to learn aspects of the opponent is called opponent modeling.¹

Having a good opponent model is a key factor in improving the quality of the negotiation outcome and can further increase the benefits of automated negotiation, including the following: reaching win-win agreements [90, 123, 206]; minimizing negotiation cost by avoiding non-agreement [151, 153, 183, 184]; and finally, avoiding exploitation by adapting to the opponent’s behavior during the negotiation [57, 85, 199]. Experiments have shown that by employing opponent models, automated agents can reach more efficient outcomes than human negotiators [22, 124, 149].

Besides improving the quality of the negotiation process, opponent models are essential for the transition of automated negotiation from theory to practice. It has been shown that non-adaptive agents are exploitable given a sufficiently large negotiation history as their behavior becomes predictable [24, 135]. The risk of exploitation can be minimized by creating adaptive agents that use opponent models to adapt their behavior.

Despite the advantages of creating an opponent model and two decades of research, there is no recent study that provides either an overview of the field, or a comparison of different opponent modeling techniques. Therefore, in order to stimulate the development of efficient future opponent models, and to outline a research agenda for the field of opponent modeling in negotiation, this survey provides an overview of existing opponent models and their underlying concepts. It discusses how to select the best model depending on the negotiation setting, and identifies a number of problems that are still open. One of our major findings is that despite the variety in opponent modeling techniques, most current models rely on a small, common set of learning techniques. Furthermore, it turns out that there are only four types of opponent attributes that are learned by these techniques.

Apart from employing different techniques to build an opponent model, different benchmarks have been used to test the effectiveness of opponent models. This makes it particularly difficult to compare present techniques. An additional contribution of this work is to give an exhaustive overview of measures that are used throughout the literature. We distinguish two types of measures, and we recommend which measures to use to reliably quantify the quality of an opponent model.

The opponent modeling techniques discussed in this work are applicable to a large diversity of negotiation protocols. Protocols may differ in many aspects, including the domain configuration, the number of agents, state of issue(s), and availability of information. Table 1 provides an overview of the scope of this survey; distinguishing the main parameters of negotiation protocols as defined by Lomuscio et al. [126] and Fatima et al. [65].

Finally, note that the problems involved in automated negotiation are very different from human negotiation. In negotiation sessions between humans, only as little as ten bids may be exchanged, whereas negotiating agents may exchange thousands of bids in less than a minute. Humans may compensate for this lack of information exchange by explicitly communicating information about their preferences, both verbally and nonverbally. To delimit our scope, we do not discuss attributes that are relevant in human negotiations but are not yet used in automated negotiation, such as emotions [54, 100].

The remainder of our work is organized as follows. We start by providing an overview of related surveys in Sect. 2. Section 3 sets out the basic concepts of bilateral negotiation. Section 4 describes the fundamentals underlying the learning methods that have been applied to construct an opponent model. Different opponent models are created to learn different negotiation aspects; we introduce our taxonomy of the various concepts that are learned, and how they are learned, in Sect. 5. Section 6 provides recommendations on how to measure the quality of an opponent model. Finally, in Sect. 7 we cover the lessons learned, we examine the latest trends, and we provide directions for future work.

The field of automated negotiation has produced over 2000 papers in the last two decades. This work covers the period from the first opponent models introduced around 1997 (cf. [205]) to the latest models developed in 2014 (cf. [37, 46, 76, 77, 92]). During this period, several surveys have been conducted that are related to our work, including surveys by Beam and Segev [18], Papaioannou et al. [152], Masvoula et al. [134], Yang [203], and Chen and Pu [42]. Our work incorporates all techniques for bilateral negotiations covered in these surveys, as we consider various types of opponent models based on multiple different learning techniques, including Bayesian learning and artificial neural networks. In comparison to these surveys, we discuss a larger body of research and categorize the opponent models based on the aspect of the opponent they aim to model. Furthermore, we provide an overview of measures used to quantify the quality of opponent models, and provide guidelines on how to apply these metrics.

Beam and Segev surveyed the state of the art in automated negotiation in 1997 [18]. Their work describes machine learning techniques applied by intelligent negotiation agents, mainly discussing the potential of genetic algorithms to learn an effective negotiation strategy. Their survey naturally misses out on more recent developments, such as on-line opponent modeling techniques used in one-shot negotiations, as for example introduced by Buffett and Spencer [31, 32] and Hindriks and Tykhonov [83]. More recently, Papaioannou et al. surveyed learning techniques based on neural networks to model the opponent’s behavior in both bilateral and multilateral negotiations [152]. Masvoula et al. also surveyed learning methods to enhance the strategies of negotiation agents [134]. One of the strengths of their survey is that it provides a comprehensive overview of learning methods. The modeling techniques are divided based on the type of strategy in which they are applied. Finally, Chen and Pu survey preference elicitation methods for user modeling in decision support systems [42]. The goal of these systems is to capture the user’s preferences in a setting in which the user is willing to share their preferences, or at least does not try to misrepresent them. While the goal of decision support systems differs from opponent modeling in automated negotiation, similar learning techniques—such as pattern matching—are used to estimate the user’s or opponent’s preferences.

A number of surveys have been conducted on the general topic of automated negotiation, for example by Jennings et al. [91], Kraus [107], Braun et al. [25], and Li et al. [118]. Jennings et al. argue that automated negotiation is a main concern for multi-agent system research [91]; and Kraus examines economic theory and game-theory techniques for reaching agreements in multi-agent environments [107]. Braun et al. review electronic negotiation systems and negotiation agents, concisely describing how learning techniques have been used to learn characteristics of the opponent [25]. Li et al. distinguish different types of negotiation, and briefly discuss opponent modeling [118]. Despite the wide scope of all of the surveys above, their discussion of opponent modeling is limited.

Negotiation is also studied as an extensive-form game within the game theory literature [118], a field of study founded on the work by Nash [141] and Raiffa [157]. In cooperative game theory, the aim is to jointly find a solution within the outcome space that satisfies particular axioms, an example being the Nash outcome (see also Sect. 6.1 on accuracy measures, p. 36) that satisfies the Nash axioms [141]. Non-cooperative game theory is concerned with identifying rational behavior using the concept of strategy equilibrium: the state in which for every agent it is not beneficial to change strategy assuming the other agents do not switch their tactic [148].

The game theory literature on the topic of negotiation is vast. For an overview we refer to Binmore and Vulkan [19]; Li and Giampapa [118]; and Chatterjee [40]. One prominent example of game theoretic negotiation research is by Rubinstein [172], who considers an alternating offers negotiation protocol without deadline in which two agents negotiate about the division of a pie. Another example is the work by Zlotkin and Rosenschein [208], which investigates a monotonic concession strategy that results in a strategy equilibrium. As outlined in [64], agents do not typically perform opponent modeling in the game theoretic model, but instead determine their strategy through theoretical analysis, which is possible because of the assumption of perfect rationality. The assumption of common knowledge—an assumption typically made in cooperative game theory—can lead to difficulties in practice [40, 41, 64, 118] as competitive agents aim to not share information to prevent exploitation [50, 75, 81, 158]. Other practical issues include the computational intractability of full agent rationality [40, 41, 91, 118] and the applicability of game theoretical results to specific negotiation settings only [19, 91, 118]. Despite these concerns, several authors have promoted the application of game theory results in the design of heuristic and learning negotiation strategies [91, 118]. For instance, evolutionary game theory (EGT) is a framework to describe the dynamics and evolution of strategies under the pressure of natural selection [178]. In this approach, negotiating agents can learn the best strategy through repeated interactions with their opponents. This has just started to make its impact on research into the negotiation dynamics of multi-agent bargaining settings [10, 43]. In Sect. 6.2, we discuss EGT as a way to quantify the robustness of a negotiation strategy to exploitability in an open negotiation environment.

An interesting area, although out of scope of this paper, is that of user modeling in general (see e.g., [136] for a survey by McTear on the topic), and in particular that of using machine learning of dialogue-management strategies by Schatzmann and colleagues [180]. McTear’s work surveys artificial intelligence techniques applied to user modeling and is by now 20 years old (a newer one has not been published to date). Characteristics of users modeled by AI techniques include goals, plans, capabilities, attitudes, preferences, knowledge, and beliefs. The relevant parts with respect to our survey are the preference profiling and the distinction between learning models of individual users versus models for classes of users, and between models for one session and models maintained and updated over several sessions.

A survey on preference modeling is by Braziunas and Boutilier [26] and focuses on direct elicitation methods; i.e., by asking direct questions to the user and is therefore not in the scope of this paper. Schatzmann’s survey [180] addresses systems and methods to learn a good dialogue strategy for which automatic user simulation tools are essential. The methods to learn these strategies can be relevant for argumentation-based negotiation systems.

Another related area of research is the topic of machine learning techniques in game playing; e.g., checkers, rock-paper-scissors, scrabble, go, and bridge. Fürnkranz argues that opponent modeling has not yet received much attention in the computer games community [67]—take for example chess, in which opponent modeling is not a critical component. However, it is essential in others, such as computer poker [171]. This is due to the fact that, as in negotiation, maximizing the reward against an effectively exploitable opponent is potentially more beneficial than exhibiting optimal play [171]. These surveys make several distinctions that we do, such as offline and online learning, and they employ many techniques that can also be used in negotiation, such as Bayesian learning and neural networks.

Before we discuss opponent models, we first introduce the terminology used throughout the paper. The defining elements of a bilateral negotiation are depicted in Fig. 1. A bilateral automated negotiation concerns a negotiation between two agents, usually called A and B or buyer and seller. The party that is negotiated with is also called the partner or opponent.

The negotiation setting consists of the negotiation protocol, the negotiating agents, and the negotiation scenario. The negotiation protocol defines the rules of encounter to which the negotiating agents have to adhere. The negotiation scenario takes place in a negotiation domain, which specifies all possible outcomes (the so-called outcome space). The negotiation agents have a preference profile, which expresses the preference relations between the possible outcomes. Together, this defines the negotiation scenario that takes place between the agents. The negotiation scenario and protocol specify the possible actions an agent can perform, given the negotiation state.

An extensive set of learning techniques have been applied in automated negotiation. Below we provide an introduction to the most commonly used underlying methods. Those that are already familiar with these techniques can skip to the next section.

The first two sections discuss Bayesian Learning (Sect. 4.1) and Non-linear Regression (Sect. 4.2). Both methods have mainly been applied as an online learning technique, because they do not require a training phase to produce a reasonable estimate, and because their estimates can be improved incrementally during the negotiation.

In contrast, the other two methods, Kernel Density Estimation (Sect. 4.3) and Artificial Neural Networks (Sect. 4.4), generally require a training phase, and are mainly applied when a record of the negotiation history is available. With these methods, it is computationally inexpensive to take advantage of the learned information during the negotiation.

A bilateral negotiation may be viewed as a two-player game of incomplete information where both players aim to achieve the best outcome for themselves. In general, an opponent model is an abstracted description of a player (and/or its behavior) during the game [193]. In negotiation, opponent modeling often revolves around three questions:These questions are often highly related. For example, some form of preference estimation is needed in order to understand how the opponent has acted according to its own utility. Then, by adequately interpret the opponent’s actions, we may deduce its strategy, which in turn can help predict what the agent will do in the future.

Constructing an opponent model may alternatively be viewed as a classification problem where the type of the opponent needs to be determined from a range of possibilities [179]; one example being the work by Lin et al. [124]. Here the type of an opponent refers to all opponent attributes that may be modeled to gain an advantage in the game. Taking this perspective is particularly useful when a limited number of opponent types are known in advance, which at the same time is its main limitation.

Note that our definition excludes work in which a pool of agents are tuned or evolved to optimize their performance when playing against each other, without having an explicit opponent modeling component themselves. For readers interested in this type of approach we refer to Liang and Yuan [120], Oliver [145], Sánchez-Anguix et al. [175], and Tu et al. [191].

Opponent modeling can be performed online or offline, depending on the availability of historical data. Offline models are created before the negotiation starts, using previously obtained data from earlier negotiations. Online models are constructed from knowledge that is collected during a single negotiation session. A major challenge in online opponent modeling is that the model needs to be constructed from a limited amount of negotiation exchanges, and a real-time deadline may pose the additional challenge of having to construct the model as fast as possible.

Opponent modeling can be performed at many different levels of granularity. The most elementary of preference models may only yield a set of offers likely to be accepted by the opponent, for instance by modeling the reservation value. A more detailed preference model is able to estimate the acceptance probability for every outcome (e.g. using a probabilistic representation of the reservation value). An even richer model can involve the opponent’s preference order, allowing us to rank the outcomes. We can achieve the richest preference representations with a cardinal model of preferences, yielding an estimate of the opponent’s full preference profile. The preferred form of granularity depends not only on the complexity of the negotiation scenario, but also on the level of information required by the agent. For instance, if the agent is required to locate Pareto optimal outcomes in a multi-issue domain, it will require at least an ordinal preference model.

Note that in most cases, comparing different approaches is impossible due to the variety of quality measures, evaluation techniques and testbeds in use; we will have more to say on how to evaluate the different approaches in Sect. 6.

Even though there are large differences between the models, a common set of high level motivations behind their construction can be identified. We found the following motivations for why opponent models have been used in automated negotiation:We found that existing work on opponent models can fulfill any of the goals above by learning a combination of four opponent attributes, which we have listed in Table 2. The remainder of this section discusses, for each attribute, the applicable opponent modeling techniques, following the order of Table 2.

In the previous section, we provided an overview of several learning methods for each opponent attribute. A natural question with regard to agent design is: which of the depicted models is best for each attribute? Unfortunately, it is impossible to provide a conclusive answer to this, as most authors evaluated their opponent model in their own setting, and relative to their own baseline. A valuable direction for future work is therefore to compare the quality of these models in a common setting, or in any case, to use the existing models as baselines when designing new learning techniques.

In general, we found that the quality of an opponent model can be measured in two main ways: accuracy measures (Sect. 6.1), which measure how closely the opponent model resembles reality; and performance measures (Sect. 6.2), which measure the performance gain when a negotiation strategy is supplemented by a model. We provide an overview in Tables 3 and 4 of both types of quality measures. Moreover, based on this overview, we recommend in Sect. 6.3 which measures to use to evaluate an opponent model given a specific modeling aim.

The research field of opponent modeling in negotiation is constantly evolving, driven by more than twenty years of interest in automated negotiation and negotiation agent design in particular. In this work, we survey opponent modeling techniques used in bilateral negotiations, and we discuss all possible ways in which opponent models are employed to benefit negotiation agents. There are essentially two main opponent model categories: models that learn what the opponent wants, in terms of its reservation value, deadline, and preference order, and secondly, models that learn what the opponent will do, in terms of the opponent’s bidding strategy and acceptance strategy. In this comprehensive survey, we create a taxonomy of currently existing opponent models, based on what opponent attributes are learned, which specific methods are used to model the attribute, and finally, what general learning techniques are applied in each case.

There exists a clear relation between every opponent attribute and the corresponding learning techniques. Bayesian learning is the most popular technique, and can be applied to learn any of the four opponent attributes we distinguish in our exposition. Time series forecasting and regression techniques are the second most popular techniques, and can be used whenever a trend can be established in the opponent’s behavior, which holds true for almost all learning tasks, except preference profile estimation. Other techniques, such as reinforcement learning, have not been used so far, but this might be only a matter of time. Learning what the opponent will do is even more challenging than finding out what the opponent wants, because the former depends on the latter. This is why the most advanced machine learning techniques are required for this case, ranging from artificial neural networks to signal processing techniques.

The many different approaches and assumptions of the opponent modeling literature raise the additional challenge of pinpointing gaps in current research. Based on our analysis, we found a number of additional directions for future research:

Development of accuracy metrics for models estimating the reservation value, deadline, and acceptance strategy. As we discussed in Sect. 6, accuracy measures are still lacking for these three types of models. The first two types could be calculated as the distance between the actual and estimated value, but more advanced methods are not yet determined. Formulating an accuracy measure for the acceptance strategy may be the most challenging of all, and could be an important step towards more advanced strategies for multi-session negotiations.

Finally, we focused on learning about the opponent, and not so much on the reverse problem: what the opponent learns, or should learn, about us; i.e., second order opponent models. On the one hand, we might actively attempt to keep the opponent from learning about us to avoid exploitation, but there is a balance to be maintained as well; it is, after all, also important for both parties to jointly explore the outcome space to reach a win-win agreement. Models that quantify the opponent’s knowledge about us can act as an essential link in combining different opponent modeling techniques. For example, we could employ a well-established preference estimation method to assess how the opponent acted according to its own utility. Then, we can apply one of the regression or forecasting techniques we have discussed to deduce the opponent’s strategy according to its own utility. In combination with what the opponent knows about us, this can predict what the agent will do in the future, this time according to our utility. In such a setting, it may be worthwhile to study techniques that are able to reveal exactly the right kind of information in order to reach the most beneficial outcome.