An Agent Architecture for Multi-Attribute Negotiation

1 Introduction

In [Gutman and Maes, 1998] the difference between competitive and co-operative negotiation is discussed. Guttman and Maes state that the competitive negotiations in retail markets are unnecessarily hostile to customers and offer no long-term benefits to merchants. Essentially, in competitive negotiations the merchant is pitted against the customer in price-tug-of-wars. Based on [Forrester, 1997], in [Gutman and Maes, 1998] it is concluded that merchants often care less about profit on any given transaction and care more about long-term profitability, which implies customer satisfaction and long-term customer relationships. Their analysis makes a strong case for co-operative negotiation for the retail market:

"...the multi-attribute utility theory (MAUT) [Keeny and Raifa, 1976], can help customers make complex buying decisions taking into account multiple factors including merchants' unique added value (e.g., extended warranty options, delivery options, etc.)."

Their argument is supported by [Rosenschein and Zlotkin, 1994], which makes clear that co-operative negotiation can be described as a non-zero-sum game where, as the values along multiple dimensions shift in different directions, it is possible for all parties to be better of. Thus co-operative negotiation is a win-win type of negotiation.

The Consumer Buying Behaviour Model (CBB) (see [Gutman and Maes, 1998]) consists of six main stages: Need Identification, Product Brokering, Merchant Brokering, Negotiation, Purchase and Delivery, and Service and Evaluation. The model discussed in this paper addresses the first four of these stages, where the product brokering is an integrated part of the entire brokering process and overlaps with the need identification. This is in line with normal procedures, as "CBB stages often overlap and migration from one to another is sometimes non-linear and iterative". The buyer contacts the broker agent, the broker agent provides the buyer with forms in order to determine the wishes of the buyer. Then the broker matches products and suppliers against the wishes of the buyer presenting him with the best three options. The buyer can then select one of these proposals. A special buyer representative agent negotiates with the representative agent of the supplier to obtain the best configuration of the selected option. The different attributes of the object under negotiation, the possible values for each of those attributes, and the different wishes (profiles) of consumer and provider, allow for co-operative negotiation: co-operative negotiation can be seen as a decision-making process of resolving a conflict involving two or more parties over multiple interdependent, but non-mutually exclusive goals; cf. [Lewicki et al., 1997].

The multi-agent system in which the negotiation agent can be and has been applied consists of the following types of agents: Human Buyers, Human Dealers, Buyer Representative agents, Dealer Representative agents, Broker agent. Moreover, to model retrieval of information from databases, a number of components is used; one of them is the External World from which Buyer Representative agents can retrieve third party information (consumer organisations like the AA of the US and the Dutch ANWB). Furthermore, specific Dealer-dependent Dealer Databases for all Dealers are included, from which the Dealer Representative agent can retrieve information about the cars offered by that particular Dealer. Because of space limitation, this paper focuses on the negotiation process within this overall architecture. The generic agent architecture for multi-attribute negotiation was designed and formally specified using DESIRE, as a refinement of the Generic Agent Model GAM [Brazier et al., 2000].

In this paper, in Section 2 the most sophisticated component within the agent architecture, Cooperation Management, which models the negotiation process, is described in more detail. In Section 3 the prototype system developed on the basis of the agent architecture is discussed; example results are shown. Section 4 concludes the paper by a discussion.

2 The Negotiation Model

In multi-attribute negotiation a bid has the form of values assigned to a number of attributes. For example, if the negotiation is about cars, and the relevant attributes are cd player, extra speakers, airco, tow hedge, price, then a bid consists of an indication of which CD player is meant, which extra speakers, airco and tow hedge, and what the price of the bid is. In the current section the generic negotiation model is described; for instantiations, see Section 3.

To assess a bid of the other party, it is important to have evaluation methods. Evaluation can be done at two levels: the level of each of the specific attributes (attribute evaluation), and the level of the bid as a whole (overall bid utility). Taking this into account, some characteristics of the multi-attribute negotiation model presented here are:

• explicit reasoning about the negotiation strategy and co-ordination of the negotiation process
• evaluation of a bid takes into account both the attributes separately and the overall utility of the bid
• planning of a new bid takes into account both the overall utility level and the level of attributes separately

In particular, in the model it is possible to work on two levels: the level of the overall bid, and the level of each of the attributes separately. The negotiation model has been specified as a compositional structure within the component Cooperation Management of GAM [Brazier et al., 2000]. Globally speaking, the process runs as follows:

• For each negotiation round, first evaluations of the attributes of the previous bids are determined.
• Then these evaluations are aggregated into overall utilities of these previous bids.
• Next, it is determined which concession step is made for the next bid, expressed in terms of the overall utility; this provides a target utility.
• To obtain the next bid, given the target utility, first according to some distribution over attributes, target attribute evaluation values are determined (chosen in such a manner that they aggregate exactly to the target utility)
• Finally, for each of these target attribute evaluation values, an attribute value is chosen that has an evaluation value as close as possible to the target evaluation value for the attribute.

In the last step, if only discrete attribute values exist, it may be the case that the target utility is not reached. However, if at least one of the attributes has continuous values, then this attribute can be chosen to compensate for differences that are created due to the mapping to discrete values for the other attributes. In our application, the price attribute is such a continuous attribute, and chosen to compensate for differences. In this manner bids are created that exactly match the target utilities. To realise the compositional process structure sketched above, at its top level the component Cooperation Management is composed of the five components in Figure 1: Negotiation Coordination, Attribute Evaluation, Bid Utility Determination, Utility Planning, and Attribute Planning. Each of these components is discussed in more detail.

2.1 Negotiation Coordination

Within the component Negotiation Coordination the negotiation process state is analysed (component Process Analysis) and the process is controlled (component Process Control). Process Analysis determines which of the following are true and which are false:

1. Repetition of steps takes place: steps without enough progress (depending on the impatience factor (p) which specifies the acceptable number of steps in which nothing changes)
2. A utility gap (larger than some threshold w) remains; i.e., a significant difference between the utility of the own bid and that of the other agent's bid.
3. A configuration mismatch (larger than some threshold n) remains between the own bid and the other agent's bid.

Here a configuration mismatch means that for at least one attribute, between the two values (in the two bids) a significant difference exists. Depending on the outcome of the analysis within component Process Control the following actions can be decided upon:

1. Start a next negotiation round
2. Contact the user to discuss whether the concession factor (g) can be changed.
3. Contact the user to discuss whether the configuration tolerance (t) can be changed.
4. Communicate to the user that an agreement has been reached.
5. Communicate to the user that the negotiation has failed (only when the user is unwilling to change the characteristics).

2.2 Attribute Evaluation

Evaluation of the attributes is made on the basis of the evaluation functions that are part of the user profile maintained within component Maintenance of Agent Information of the agent. Component Attribute Evaluation evaluates the attributes of available objects based on the preferences of the user represented by the agent.

The evaluation functions either have a table form or another specific function description. A table form is used for discrete attributes such as accessories. Specific function descriptions are used for continuous attributes such as mileage or price. The form of specific function descriptions are of a type such as 'linear', or 'uphill'. For the attributes for which a specific (non-table) type of evaluation function is given, depending on this type, knowledge is specified to obtain the object evaluations. Currently, only specific function types are used that consist of linear parts, cut off between 0 and 1: linear function, normal distribution function, downhill function, uphill function.

If desired, in all evaluations and utilities, the model supports that two aspects can be modelled separately and integrated: ease evaluation and ease utility EU and financial evaluation and financial utility FU. The latter aspect covers the financial rationality in the agent's behaviour. The former aspect models all other aspects within the decision making such as a resistance against more complicated transactions (even if in terms of economic gain they are more favourable). The balance between these two aspects within the overall evaluations is defined by the financial rationality factor r. If this factor is 1, then only the financial utility is taken into account (completely financially driven), if it is 0, only the ease utility (completely ease driven). Any factor in between 0 and 1 defines the relative weight of the economic aspect compared to the ease aspect in the decision making. For example, for a certain accessory the financial aspect of the evaluation value is the cost it takes to provide it (both the price of the accessory and the cost of installing it).

2.3 Bid Utility Determination

Within the model, the utility UB of a bid B is taken as a weighted sum of the attribute evaluation values EB,j for the different negotiant attributes denoted by j.

Here the weights w j are relative importance factors based on the importance factors pk for the different attributes:

If a financial utility is used separately, then the above utility (called the ease utility EUB) is determined on the basis of all attributes except price. Financial utility FUB is based on the financial balance gB for a given bid B:

where b denotes the basic costs (the cost of the object without additional accessories) and aB denotes the additional costs of bid B, and pB price within bid B.

that is based on the financial evaluations (FEB,j) of the values of the different attributes j. However, to be able to relate FUB to the ease utility EUB, FUB is the normalisation of the financial balance to a number between 0 and 1:

The fraction d is the fraction of the basic cost that is maximally additionally (to be) earned (e.g. 0.3, a maximum margin of 30%). Some notes can be made.

• The financial utility FU is defined on the interval between 0 and 1 in such a manner that financial utility 1 means cost price plus maximal margin (b + db + aB).
• Let B0 be the initial bid of the seller, then by taking price pB0 = b + db + aB0, the financial utility of this bid is

• By setting d properly, the seller makes sure that (s)he is not asking unrealistic prices.
• The financial utility is defined on the interval between 0 and 1 in such a manner that FUB = 0 implies pB = b + aB, i.e., the cost price. So, if a buyer makes a bid B with pB < b + aB, then FUB < 0 from the perspective of the seller.

On the basis of the ease utility and the financial utility, the overall utility is determined as a weighted sum. Here the weights are based on the financial rationality factor r (part of the dealer profile).

2.4 Utility Planning

For determination of the target utility TU the following formula is used within the model:

with UBS the utility of the own bid, and the concession step CS determined by

where UBO is the utility of the other agent's bid. In this formula the factor UBO - UBS expresses the current utility gap. The factor (1 - m / UBS) expresses that the concession step will decrease to 0 if the UBS approximates the minimal utility m. This ensures UBS ‡ m. The factor b stands for the negotiation speed. The minimal utility is taken as m = 1 - g with g the concession factor, expressing a measure in how far concessions can be made. Determination of the target utility can also address the ease and financial aspect separately (indicated by E or F added to the parameters). For each of these aspects the same model is used. For example, for the ease aspect the following formula is used:

In this formula bE is the negotiation speed factor for the ease part, and mE is the minimal ease utility. Similarly, for the financial aspect the target utility is:

The speed factors bE for ease and bF for financial parts are based on the negotiation speed factor b and the financial rationality factor r as follows

The minimal ease utility is taken as mE = 1 - g. The minimal financial utility is taken as mF = e / d where e is the minimal financial margin. The explanation is as follows. If the minimal margin is achieved, then the price minP is

Given minP, the minimal acceptable financial utility can be calculated as follows:

For example, if d = 0.2 (20%) and e = 0.1 (10%), then mF = 0.5, i.e., the dealer is not willing to sell with a financial utility lower than half of its maximal financial utility (based on the maximal margin); a financial utility of 0 means selling against the cost price, i.e., no margin at all, a financial utility of 1 means selling with a margin of 20% on the cost price.

2.5 Attribute Planning

The Attribute Planning process uses as input the target utility and determines as output the configuration for the next (own) bid in the following two main steps:

• First, within the component Target Evaluation Determination, for each attribute a target evaluation is determined.
• Next, given these target evaluations per attribute, within the component Configuration Determination, a configuration for the next bid is determined.

Target Evaluation Determination

Target evaluations per attribute TEj are determined in the model in two steps. First a basic target evaluation per attribute BTEj is determined in such a way that S j w j BTEj = TU. Then the target evaluations TEj are combinations of the BTEj with the evaluations of the attributes in the bid of the negotiation partner. The basic target evaluation per attribute BTEj is determined according to the following format:

Here the aj can be chosen arbitrarily, and N is a normalisation factor. Factor N is defined as the weighted sum of the a's with the relative importance factors as weights: N = S j w j aj. Due to this normalisation factor, the utility determined as a combination of the target evaluations leads to exactly the target utility:

The choice for the a's is made as: aj = (1 - w j) (1 - EBS, j). The first factor expresses the influence of the user's own importance factors (similar to the choice made in [Benn, et al., 1999]); the second factor takes care that the target evaluation values remain scaled in the interval between 0 and 1. Besides the influence on the target attribute evaluations as described, also a concession to the opponent's attribute evaluations is made. This depends on the configuration tolerance t, as follows:

If the configuration tolerance is 0, then only the user's importance factors are taken into account. If the configuration tolerance is 1, then with respect to the configuration maximal concession to the negotiation partner is made.

Configuration Determination

To determine a configuration for the next bid the following three steps are made.

• First, for each attribute, given the target evaluation, attribute values are determined with an evaluation that is as close as possible to the target evaluation value.
• Next, a partial configuration (price attribute not yet filled) is determined based on these closest values.
• Finally, to complete the configuration for the next bid, also the price attribute value is determined.

The partial configuration is selected from the closest attribute values. If more than one choice with closest value is possible, then, if it is among the options, the value in the opponent's bid is chosen, otherwise the choice is made in a random manner. The partial configuration is completed by determining the price attribute value in such a manner that the overall target utility is achieved.

Within the Dealer Representative agent a simple possibility would be to take the target financial utility as the aim to be achieved. However, due to the discrete values of the accessory attributes, the ease utility will probably not be exactly achieved. The choice has been made that this difference is compensated in the financial utility. For example, if the ease utility of the partial configuration is lower than the target ease utility, then the Dealer Representative agent aims at a financial utility which is (in proportion) higher than the target financial utility.

First the ease utility of the partial configuration is determined. Next the financial utility that has to be achieved (AFU) is determined, as the (weighted) difference between overall target utility and the realised ease utility:

where UP, E is the ease utility of the partial configuration P. Finally, the price attribute value is determined, as the sum of all costs and the fraction of the maximum margin given by the financial utility aimed for:

3 Implementation: Example

A trace was generated on the basis of the data presented in the Tables 2 to 5. In these tables, "buyer representative" is abbreviated to BR, similarly DR stands for dealer representative. Basic negotiation parameters are depicted in Table 2 above. The buyer representative only uses the (ease) evaluations and utilities; therefore, the special financial factors are not applicable in Table 2. In Table 3 the importance factors are depicted. In Table 3, for the dealer representative the price attribute has no value, since it is only part of the financial utility function. Within financial terms the importance factors are irrelevant.

In Table 4 below the evalution descriptions for the different attributes are depicted.

Furthermore, the dealer representative also needs the financial evaluation descriptions for the different accessories and it needs to know the basic costs of the car under negotiation (in this case the basic costs are 13000). The dealer representative's financial evaluation descriptions are depicted in Table 5 below.

A trace of the negotiation process is depicted in the Tables 6 and 7 below. The buyer representative's bid, his opinion of his bid and his opinion of the bid of the dealer representative in the previous round are presented in Table 6 below.

The dealer representative's bid, his opinion of his bid, and his opinion of the bid of the buyer representative in the same round are presented in Table 7 below.

Note that the price attribute is monotonically increasing for the buyer' s bids, but for the dealer' s bids it does not monotonically decrease: from round 3 to 4 it increases (appearantly to compensate for a change in the CD player attribute from ' none' to ' good' ). The overall utilities attributed to the own bids for both buyer and dealer are monotonic, as may be expected from the negotiation model. However, this may not be true for the utility attributed by one of the parties to the other party' s bid. Actually, from the perspective of the buyer, the dealer bid is getting a lower utility in round 4. What is perceived as a concession from one party' s perspective can provide a worse bid in the perception of the other party.

Note that the values in round 12 are such that, to the buyer representative's opinion, the utility gap has disappeared, and also the configuration gap is gone. The buyer representative, therefore, concludes after round 12 has been completed (that is: the dealer representative's reaction to his bid in round 12 has been received) that a match has been found, and asks the buyer he represents permission to close the deal instead of continuing with round 13. Given the permission of his user, the buyer representative does not call out round 13, but sends to the dealer representative an acceptance of the previous bid of the dealer representative. The dealer representative now also asks his user (the dealer) to close the deal. Given permission, the dealer representative finishes the deal with an acceptance.

Initially, the dealer asked 17,290 for the car without any accessories. For him, this would be ideal, scoring a 30% gain on the car. However, this bid is unacceptable to the buyer, who starts to negotiate. The agents quickly converge on the preferred values for tow hedge, airco, extra speakers, and cd-player, but hagle a few rounds over the price. In the final round, the buyer accepts the offer of the dealer having a car with a meager tow hedge, meager airco, good extra speakers, and good cd-player for 18,884 guilders. Based on the consumer organisations prices for such accessories, the buyer payed 2,600 for accessories, and therefore, 16,284 for the car without accessories. This means that the buyer was able to negotiate a reasonable price for himself. From the dealer' s point of view the deal is reasonable as well. He was able to sell a good CD player which he had in stock, and although he had to order the other accessories, the price still gives him a profit of 3,284 (= price - basiccost - sum of accessories = 18,884 - 13,000 - 2,600). This corresponds to a financial utility of 0.84 = profit / max financial margin * basiccost = 0.3 * 13,000). The reason that his total utility is lower (0.581) is due to the low ease utility (it takes him rather some work to do equip the car). All in all, both are satisfied.

4 Discussion

In [Gutman and Maes, 1998] a number of criteria and benefits are discussed of some different approaches to negotiation. For example, in the competitive negotiation system Kasbah three negotiation strategies are mentioned: anxious (linear increase of bids over time), cool-headed (quadratic), and frugal (exponential). In the model presented here, these strategies can be used to determine the negotiation speed. Another important issue discussed in [Gutman and Maes, 1998] is the argument for co-operative negotiation that merchants often care less about profit on any given transaction and care more about long-term profitability, which implies customer satisfaction and longterm customer relationships. That argument supports the importance of the following factors in our model for negotiation: configuration tolerance (consumer satisfaction), concession factor (profit), minimal financial margin (profit), and financial rationality (profit). Furthermore, the remark that co-operative negotiation is a win-win type of negotiation is supported by our model in that consumers and providers both have an extensive multiattribute profile (importance factors, evaluation descriptions) that influence the outcome of the negotiation aiming to satisfy both parties.

A main difference of our work to the work described in [Benn et al., 1999] is that in our approach it is possible to specify heuristics both for the overall utilities and for separate attributes (with their values and evaluations). In their approach no overall view is made; a compensation matrix is used to compensate a concession in one attribute by other attributes. In our approach it is possible to decide about the overall concession (in terms of the overall utility) in a negotiation step, independent of specific concessions for separate attributes. Moreover, in their approach a neural (Hopfield) network is used to find the compensations for attributes by an approximation process. In contrast, our approach uses explicit knowledge to determine the attributes of a new bid, which makes it more transparent and better explainable.

In [Sierra, et al., 1998] an argumentation-based approach to negotiation is put forward. One of the issues that was left open is how the argumentation-based approach relates to utilities. This is in contrast to our approach where utilities play a main role.

Both a design description, formally specified in DESIRE, and a prototype implementation of the architecture has been constructed and tested by a group of users. Due to the various parameters making up a very detailed profile, the multi-attribute negotiation architecture for agents that is presented in this paper is more flexible with respect to user preference modelling than the existing approaches. A drawback may be, however, that to acquire such a detailed profile users may need some patience. An issue for further research is to develop automated support for this acquisition process, for example, on the basis of information acquired by monitoring the user.

The model respects the privacy of both parties (since profile information is kept local) and still is capable of adjusting to the profile of the opponent if such is desired by the user. The model allows for flexible heuristics both for the overall utilities and for the attribute evaluations. An issue for further study is how relationships between evaluations of different attributes can be exploited, for example to express that a buyer only has a high evaluation value for speakers if a CD player is present.