Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Negotiating contracts with multiple interdependent issues, which may yield non-monotonic, highly uncorrelated preference spaces for the participating agents, is specially challenging because its complexity makes traditional negotiation mechanisms not applicable (López-Carmona et al., 2012). In this chapter, we will review key concepts about multi-attribute negotiation and the most relevant works in the field, and then we focus on the main recent research lines addressing complex negotiations in uncorrelated utility spaces. Finally, we describe CPMF (de la Hoz et al., 2011), a Consensus Policy Based Mediation Framework for multi-agent negotiation which allows to search for agreements following predefined consensus policies, which may take the form of linguistic expressions.

2 Multi-attribute Negotiation

Multi-attribute negotiation may be seen as an interaction between two or more agents with the goal of reaching an agreement about a range of issues which usually involves solving a conflict of interest between the agents. This kind of interaction has been widely studied in different research areas, such as game theory (Rosenschein and Zlotkin, 1994), distributed artificial intelligence (Faratin et al., 1998) and economics.

Multi-attribute negotiation is seen as an important challenge for the multi-agent system research community (Lai et al., 2004), and there is a great variety of negotiation models and protocols intended to address different parts of this challenge. These models may be classified according to different criteria (Buttner, 2006), such as their structure, the dynamics of the negotiation process, or the different constraints imposed on the problem (e.g. deadlines, information availability…). According to the theoretical foundations of the negotiation models, we can find approaches based on game theory, heuristic approaches (Klein et al., 2003; Gatti and Amigoni, 2005; Lai et al., 2006; Ros and Sierra, 2006; Ito et al., 2008) and argumentation-based approaches (Rahwan et al., 2003, 2007; Jennings et al., 1998; Amgoud et al., 2000).

Regardless of the theoretical approach involved, different authors agree that there are three key components in a negotiation model (Kraus, 2001b; Jennings et al., 2001; Fatima et al., 2006):

  • An interaction protocol, which defines the rules of encounter among the negotiating agents, including what kind of offer exchange is allowed and what kind of deals may be reached and how they are established.

  • The preference sets of the different agents, which allow them to assess the different solutions in terms of gain or utility and to compare them.

  • A set of decision mechanisms and strategies, which govern agents’ decision making, allowing them to determine which action will be the next one under a given negotiation state.

The most-widespread interaction protocol for negotiation is based on the exchange of offers and counter offers, which are expressed as an assignment of values to the different attributes. This kind of negotiation protocols are known as positional bargaining. A particular protocol family for multi-lateral negotiations are auction-based protocols, where negotiating agents send their offers (also called bids) to a mediator, which then decides the winning deal (Teich et al., 1999). Auction-based protocols allow one-to-many and many-to-many negotiations to be dealt with efficiently. Another important division regarding interaction protocols is between one-shot protocols and iterative protocols. In one-shot protocols, there is a single interaction step between the agents. In iterative protocols, on the other hand, agents have the opportunity to refine their positions in successive protocol iterations (Osborne and Rubinstein, 1990).

Preference sets express the absolute or relative satisfaction for an agent about a particular choice among different options (Keeny and Raiffa, 1976). Cardinal preference structures are probably the most widely used in complex negotiations. In particular, it is usual to define agent preferences by means of utility functions. The most basic form to represent a utility function is to make an enumeration of the points in the solution space which yield a non-zero utility value. It is easy to see that, although this representation for utility functions is fully expressive, its cardinality may grow greatly with the number of issues or with the cardinality of each issue’s domain. Because of this, more succinct representations for utility functions are used in most cases. Examples of such representations which are widely used in the negotiation literature are linear-additive utility functions (Faratin et al., 2002) or k-additive utility functions (Grabisch, 1997).

Another widely used way to represent preferences and utility functions is the use of constraints over the values of the attributes: either hard, soft, probabilistic or fuzzy constraints (Luo et al., 2003b; Lin, 2004; Ito et al., 2008). A particular case of constraint-based utility representation which has been used to model complex utility spaces for negotiation are weighted constraints. There is a utility value for each constraint, and the total utility is defined as the sum of the utilities of all satisfied constraints. This kind of utility functions produces nonlinear utility spaces, with high points where many constraints are satisfied, and lower regions where few or no constraints are satisfied.

Finally, the main challenge in an automated negotiation scenario is to design rational agents, able to choose an adequate negotiation strategy. In negotiations among selfish agents, negotiation mechanisms should motivate the agents to act in an adequate way, since if a rational, selfish agent may benefit from taking a strategy which is different to the one expected by the protocol, it will do so. This problem is closely related to the notion of equilibrium and strategic stability defined in game theory. In an equilibrium, each player of the game has adopted a strategy that they have no rational incentive to change (because it is the best alternative, given the circumstances). There are different equilibrium conditions which can be defined, like dominant strategies (Kraus, 2001a), Nash equilibrium or Bayes-Nash equilibrium (Harsanyi, 2004).

A potential threat to mechanism stability is strategic revelation of information. In incomplete information scenarios (Jonker et al., 2007), since the agents’ beliefs about the preferences of a given agent may influence the decision mechanisms they use, an agent may use as a strategy to lie about its own preferences in order to manipulate the decision mechanisms of the rest of the agents to its own benefit. It would be desirable to design protocols which are not prone to be manipulated through insincere revelation of information. Incentive-compatibility is defined as the property of a negotiation mechanism which makes telling the truth the best strategy for any agent, assuming the rest of the agents also tell the truth. An example of an incentive-compatible protocol is the Clarke tax method (Clarke, 1971).

3 Related Research on Automated Negotiation in Complex Utility Spaces

Klein et al. (2003) presented, as far as we are aware, the first negotiation protocols specific for complex preference spaces. They propose a simulated annealing-based approach, a refined version based on a parity-maintaining annealing mediator, and an unmediated version of the negotiation protocol. Of great interest in this work are the positive results about the use of simulated annealing as a way to regulate agent decision making, along with the use of agent expressiveness to allow the mediator to improve its proposals. However, this expressiveness is somewhat limited, with only four possible valuations which allow the mediator to decide which contract to use as a parent for mutation, but not in which direction to mutate it. On the other hand, the performed experiments only consider the bilateral negotiation scenario, though the authors claim that the multiparty generalization is simple. Finally, the family of negotiation protocols they propose are specific for binary issues and binary dependencies. Higher-order dependencies and continuous-valued issues, common in many real-world contexts, are known to generate more challenging utility landscapes which are not considered in their work.

Luo et al. (2003a) propose a fuzzy constraint based framework for multi-attribute negotiations. In this framework a buyer agent defines a set of fuzzy constraints to describe its preferences. The proposals of the buyer agent are a set of hard constraints which are extracted from the set of fuzzy constraints. The seller agent responds with an offer or with a relaxation request. The buyer then decides whether to accept or reject an offer, or to relax some constraints by priority from the lowest to highest. In Lopez-Carmona and Velasco (2006) and Lopez-Carmona et al. (2007) an improvement to Luo’s model is presented. They devise an expressive negotiation protocol where proposals include a valuation of the different constraints, and the seller’s responses may contain explicit relaxation requests. This means that a seller agent may suggest the specific relaxation of one or more constraints. The relaxation suggested by a seller agent is based on utility and viability criteria, which improves the negotiation process.

Another interesting approach to solve the computational cost and complexity of negotiating interdependent issues is to simplify the negotiation space. Hindriks et al. (2006) propose a weighted approximation technique to simplify the utility space. They show that for smooth utility functions the application of this technique results in an outcome that closely matches the outcome based on the original interdependent utility structure. The method is evaluated for a number of randomly generated utility spaces with interdependent issues. Experiments show that this approach can achieve reasonably good outcomes for utility spaces with simple dependencies. However, an approximation error that deviates negotiation outcomes from the optimal solutions cannot be avoided, and this error may become larger when the approximated utility functions become more complex. The authors acknowledge as necessary future work the study of which kind of functions can be approximated accurately enough using this mechanism. Another limitation of this approach is that it is necessary to estimate a region of utility space where the actual outcome is expected to be (i.e. it is assumed that the region is known a priori by the agents).

In Robu et al. (2005) utility graphs are used to model issue interdependencies for binary-valued issues. Utility graphs are inspired by graph theory and probabilistic influence networks to derive efficient heuristics for non-mediated bilateral negotiations about multiple issues. The idea is to decompose highly non-linear utility functions in sub-utilities of clusters of inter-related items. They show how utility graphs can be used to model an opponent’s preferences. In this approach agents need prior information about the maximal structure of the utility space to be explored. The authors argue that this prior information could be obtained through a history of past negotiations or the input of domain experts.

There are several proposals which employ genetic algorithms to learn the opponent’s preferences, according to the history of the counter-offers, based upon stochastic approximation. In Choi et al. (2001) a system based on genetic algorithms for electronic business is proposed. Lau et al. (2004) have also reported a negotiation mechanism for non-mediated automated negotiations based on genetic algorithms. The fitness function relies on three aspects: an agent’s own preference, the distance of a candidate offer to the previous opponent’s offer, and time pressure. In this work, the agents’ preferences are quantified by a linear aggregation of the issue valuations. However, non-monotonic and discontinuous preference spaces are not explored.

In Yager (2007) a mediated negotiation framework for multi-agent negotiation is presented. This framework involves a mediation step in which the individual preference functions are aggregated to obtain a group preference function. The main interest is focused on the implementation of the mediation rule where they allow a linguistic description of the rule using fuzzy logic. A notable feature of their approach is the inclusion of a mechanism rewarding the agents for being open to alternatives other than simply their most preferred. The negotiation space and utility values are assumed to be arbitrary (i.e. preferences can be non-monotonic). However, the set of possible solutions is defined a priori and is fixed. Moreover, the preference function needs to be provided to the mediation step in the negotiation process, and pareto-optimality is not considered. Instead, the stopping rule is considered, which determines when the rounds of mediation stop.

Fatima et al. (2009) analyze bilateral multi-issue negotiation involving nonlinear utility functions. They consider the case where issues are divisible and there are time constraints in the form of deadlines and discounts. They show that it is possible to reach Pareto-optimal agreements by negotiating all the issues together, and that finding an equilibrium is not computationally easy if the agents’ utility functions are nonlinear. In order to overcome this complexity they investigate two possible solutions: approximating nonlinear utilities with linear ones; and using a simultaneous procedure where the issues are discussed in parallel but independently of each other. This study shows that the equilibrium can be computed in polynomial time. An important part of this work is the complexity analysis and estimated approximation error analysis performed over the proposed approximated equilibrium strategies. Heuristic approaches have generally the drawback of the lack of a solid mathematical structure which guarantees their viability. This raises the need of an exhaustive experimental evaluation. An adequate complexity analysis and establishing a bound over the approximation error contribute in giving the heuristic approaches part of the technical soundness they usually lack. We also point out that this work is focused on symmetric agents where the preferences are distributed identically, and the utility functions are separable in nonlinear polynomials of a single variable. This somewhat limits the complexity of the preference space.

Finally, combinatorial auctions (Xia et al., 2005; Giovannucci et al., 2010) can enable large-scale collective decision making in nonlinear domains, but only of a very limited type (i.e. negotiations consisting solely of resource allocation decisions). Multi-attribute auctions, wherein buyers advertise their utility functions, and sellers compete to offer the highest-utility bid (Parkes and Kalagnanam, 2005; Teich et al., 2006) are also aimed at a fundamentally limited problem (a purchase negotiation with a single buyer) and require full revelation of preference information.

In summary, in the existing research nearly all the models which assume issue interdependency rely on monotonic utility spaces, binary valued issues, low-order dependencies, or a fixed set of a priori defined solutions. Simplification of the negotiation space has also been reported as a valid approach for simple utility functions, but it cannot be used with higher-order issue dependencies, which generate highly uncorrelated utility spaces. Therefore, new approaches are needed if automated negotiation is to be applied to settings involving non-monotonic and highly uncorrelated preference spaces.

4 New Directions on Multiparty Negotiation Protocols: Consensus Policy Based Negotiation Framework

Most research in multiparty automated negotiation has been focused on building efficient mechanisms and protocols to reach unanimous agreements, which optimize some kind of social welfare measurement like the sum or product of utilities (Klein et al., 2003; Lai and Sycara, 2009). They normally avoid considering situations where unanimous agreements are neither possible nor desired. We believe that the type of consensus employed to reach an agreement should be taken into consideration as an integral part when building multiparty negotiation protocols. We describe here CPMF (de la Hoz et al., 2011), a Consensus Policy Based Mediation Framework for multi-agent negotiation. This framework allows the search for agreements following predefined consensus policies (which may take the form of linguistic expressions) in order to satisfy system requirements or to circumvent situations where unanimous agreements are not possible or not desirable.

The basic protocol of the proposed negotiation process in an scenario with n agents and m issues under negotiation is as follows:

  1. 1.

    The mediator proposes a set of points (mesh) around an initial random contract x(1) using a step-length parameter △ 1. The points are generated according to the expression x + (k) = x(k) ± △ k e j , j ∈ { 1, …, m}, where e j is the jth standard basis vector in the m-dimensional space. We will use the notation x  + o(k) to designate the mesh at round k including the current point x(k) (Fig. 22.1).

  2. 2.

    Each agent provides the mediator their preferences for each on of the contracts in the current mesh x  + o, in terms of a mapping S i : X → [0, 1] such that for example S i (x e j (k)) indicates agent i’s support for the alternative x e j (k). An agent does not know the other agents’ support for the contracts.

  3. 3.

    For every point in the mesh, the mediator computes an aggregation of the individual agents’ preferences. Each aggregation represents the group preference for the corresponding contract in the mesh. We shall refer to this as the aggregation of preferences step.

  4. 4.

    The mediator decides which is the preferred contract in the mesh according to the group preferences for the different contracts.

  5. 5.

    Based on the preferred contract, the mediator decides to generate a new set of points to evaluate, either expanding or contracting the mesh using the procedure outlined in step 1 but using a new step-length parameter △ 2. Should a contraction make △ k small enough, the negotiation ends, otherwise mediator goes to step 2.

Fig. 22.1
figure 1

Set of points or mesh for a two-dimensional preference space

Full size image

We assume that the negotiation process is such that a solution from X is always obtained. At each stage of the process an agent provides a support measure determined by its underlying payoff function and any information available about the previous stages of the negotiation.

One of the key points in the protocol is the process that the mediator uses to aggregate the individual support for the contracts in the mesh at round k. We assume each agent has provided at round k her preference S i (x  + o(k)) over the set of points under evaluation (x  + o(k)) such that it indicates the degree to which each agent A i supports each contract. The mediator objective in this mediation step is to obtain a group preference function G : x  + o → [0, 1] which associates with each alternative x e j (k) ∈ x  + o(k) a value G(x e j (k)) = M(S 1(x e j (k)), …, S n (x e j (k))).

Here M is the mediation rule and describes the process of combining the individual preferences. The form of M can be used to reflect a desired mediation imperative or consensus policy for aggregating the preferences of the individual agents to get the mesh group preferences. M will guide the mediator in the expansion-contraction decisions in order to meet the desired type of agreements for the negotiation process. The aggregation takes the form of a OWA operator (Yager and Kacprzyk, 1997). OWA operators provide a parametrized class of mean type aggregation operators. In the OWA aggregation the weights are not directly associated with a particular argument but with the ordered position of the argument. If ind is an index function such that ind(t) is the index of the tth largest argument, then we can express using OWA as M(S 1 …, S n ) = ∑ t = 1 n w t S ind(t). Examples of OWA operators are the max operator, which, in our case would give us the aggregation Max i [S i ], the min operator, which would give us the aggregation min i [S i ] or the avg operator, which would give us the average \( \frac{1}{n} \) ∑ i = 1 n S i .

The final objective is to define consensus policies in the form of a linguistic agenda. For example, the mediator could make decisions following mediation rules like “Most agents must be satisfied by the contract”. These statements are examples of quantifier guided aggregations. Under the quantifier guided mediation approach a group mediation protocol is expressed in terms of a linguistic quantifier Q indicating the proportion of agents whose agreement is necessary for a solution to be acceptable. The quantifiers all, any and at least α shown at Fig. 22.2 are examples of this. First, we will express the mediation rule using Q and then we will derive the OWA weights from Q de la Hoz et al. (2011). Figure 22.3 shows an example. Finally, let us describe the search process used by the mediator to decide whether to generate a new mesh in order to continue with a new negotiation round, or to finish the negotiation process. This process starts just after any aggregation of preferences process, when the mediator has determined the group preferred contract x e  ∗ (k). The mediator generates a new mesh in order to continue the search process. If the preferred contract is the previous mesh centre (x(k)), the step-length △ k + 1 used to generate the new mesh is halved. Otherwise, the step-length △ k + 1 is doubled.

Fig. 22.2
figure 2

Functional form of typical quantifiers: all, any, at least, linear, piecewise linear Q Z β and piecewise linear Q Z α

Full size image
Fig. 22.3
figure 3

Example of how to obtain the weights from a quantifier for n = 5 agents

Full size image

In order to avoid getting stuck in local optima, we use a probabilistic process in the search procedure. The principle of this approach is analogous to the simulated annealing technique (Klein et al., 2003) without reannealing.

5 Conclusions

Automated negotiation can be seen from a general perspective as a paradigm to solve coordination and cooperation problems in complex systems, providing a mechanism for autonomous agents to reach agreements on, e.g., task allocation, resource sharing, or surplus division. Although a variety of negotiation models have been proposed according to the many different parameters which may characterize a negotiation scenario, the consensus type by which an agreement meets in some specific manner the concerns of all the negotiators is not usually taken into account. Most of the works focus only on unanimous agreements. Such solutions do not fit well on every environment. We believe that the consensus type should be considered as an integral part of multiparty negotiation protocols. We propose a multiagent negotiation protocol where the mediation rules at the mediator may take the form of a linguistic description of the type of consensus needed using OWA operators and quantifier guided aggregation. This protocol performs a distributed exploration of the contract space in a process governed by the mediator that aggregates agent preferences in each negotiation round applying the type of consensus desired. This negotiation framework opens the door to a new set of negotiation algorithms where consensus criteria will play an important role. A possible scenario for this algorithms is consortium building in brokerage events where the linguistic expressed mediation rules could be of great utility for guiding the set partitioning process and the identification of high-valued consortia.