Constructing utility models from observed negotiation actions

1 Introduction

Utility functions encode an agent's preference and risk-taking behavior, and in many negotiation scenarios they are often considered private information. Although various elicitation techniques for decision makers have been widely used (see for example [Keeney and Raiffa, 1976]), they are not readily applicable in the negotiation scenario. For example, an agent can not ask the the opposing party lottery questions to assess its utility function . The use of learning mechanisms in nego­ tiation has been investigated in several recent studies, see for example [Bui eta!., 1999; Zeng and Sycara, 1998], and has been shown to be an effective tool in handling uncertainty and incompleteness. None of the previous studies, however, have directly addressed the issue of utility elicitation. In many cases, value functions and utilities are assumed to be partially or completely known as shown in their experiments and eval­ uation. In this work, we assume that each party's utility is completely unknown to the other and no trusted third party exists. We describe how information provided by observed negotiation actions can be used to construct the utility model of an agent.

An important tool in eliciting utility functions is the use of lottery or gamble questions and the concept of certainty equivalence. Let D be a domain, U be a utility function over D, and let oi and Oj be outcomes in a gamble G where oi occurs with a probability p, Oj occurs with a probabil­ ity (1 - p), and Oi, Oj E D. A certainty equivalent is an amount i: such that the decision maker (DM) is indifferent between G and i:. Thus, U(i:) = pU(o;) + (1- p)U(oj) or i: = u- 1 [pU(o;) + (1- p)U(oj)].

2 Negotiation actions as gamble questions

We would like to construct a model that gives us preference and risk-taking information given a position x; and a gamble that insists on a position x j. A position is either an offer or a counter-offer. Due to space limitation, our discussion is re­ stricted to constructing the buyer's model. We use Zeuthen's concept of probability to risk a conflict [Zeuthen, 1930] as a basis for transforming negotiation transactions into gam­ ble questions. While Zeuthen assumes complete knowledge

Peter Haddawy

Asian Institute of Technology Pathumthani, Thailand 12120 haddawy@ait.ac. th

of utility functions, our approach attempts to build a utility model by observing negotiation actions.

A conflict occurs when both parties do not reach an agree­ ment. The probability that a party would risk a conflict is proportional to the difference between what the party wants and what it is offered. The closer the other party's offer is to what is desired, the smaller this probability should be. The farther away the other party's offer is from what is desired, the larger the readiness to risk a fight or conflict.

Definition 1 Let U B and Us be B 's (buyer) and S 's (seller) utility function, respectively. Let XB be B 's/!osition and xs be S 's position. The probability that B wi I risk a conflict, PB. and the probability that S will risk a conflict, ps. are defined as follows:

By computing the expected utility, B can decide whether to acceptS's offer or insist its own position. In particular, B counter-offers x 8 whenever the gamble has a utility higher than xs, i.e., U B (xs) < (1 - Ps)U B(XB) + psU B (conflict). B accepts xs if forB the expected utility of the gamble (1ps)U B (xB) + psU B (conflict) can not exceed U B(xs ). If the utility of a non-agreement (conflict) is higher than x s then the offer is rejected.

Without losing generality we will assume that U B is mono­ tonically decreasing while Us is monotonically increasing. The following theoretical results allow us to generate training instances implied by a counter-offer.

Theorem 1 Let XB be B 's counter-offer and xs be S 's offer. Furthermore,letG = (1-ps)UB(xB)+psUB(conflict) and leti:B beB 'scertaintyequivalentforG. Jf(G > Ua(xs) ) thenforanynondegenerateG, XB E (xB,xs).

Theorem 2 (Inferior Offers) Let XB be B 's counter-offer andxs beS'soffer. Furthermore,letG = (1-ps)Ua(xB)+ psU B (conflict) and Ps be S 's readiness to risk a conflict at x. xs < x . If(G > UB(xs)) then ((I- Ps)UB(xB) + PsUB(conflict)) > UB(x), V x such that xs < x.

By Theorem 1, if B decides to make a counter-offer xs to an offer xs by S, then B's certainty equivalent belongs to the interval ( x B , x s). Theorem 2 states that if B prefers the gamble to an offer of xs by S then B would also prefer to gamble than accept any offer by S higher than xs. Sym­ metrically, B prefers any offer lower than x B over a gamble. Counter-offers imply preference between a gamble and a spe­ cific offer. Although B's estimate of S's probability to risk a conflict, Ps, is not specifically known, B's counter-offers are in part based on PS· Hence, by learning B's actions, Ps val­ ues are indirectly incorporated into the model.

3 Utility model construction and evaluation

We ran experiments using two control utility functions : / l (x) = 1- e::;· (risk-averse, decreasing function) and 12 (x) = e- 0 · 0025 x (risk-prone, decreasing function). In each negotiation sequence, Ps is either generated randomly or is set using {0.50, 0.25, 0.60} as values. The negotiation using 1'1 (x) is over the domain D 1 = [50, 100] and that of 12 (x) is over D2 = [200, 700]. The value of conflict c is set at t~e maximum value of the domain. The buyer-seller negotia­ tiOn strategy, a, vary among Boulware-Conceder, Conceder­ Boulware, and Conceder-Conceder pairs. We define our Boulware strategy as one where the agent concedes only 10% of the time and a Conceder strategy as one where concession is frequent at 90% of the time. Whenever an agent concedes, concession is randomly chosen between 0-50% of the differ­ ence between both agents' most recent counter-offers.

The artificial neural network used in our experiments has one hidden layer with four nodes. The input layer contains three input nodes and the output layer contains two nodes. Data fed into the input layer are scaled so that values only range between 0 and 1. Negotiation sequences used for train­ ing, tuning, and testing are randomly generated using a cho­ sen strategy pair, a control utility function 1( x), a negotiation domain, and a constant conflict value. We used a k -1 cross validation method to train and tune the network, where k is the number of negotiation transactions (offer-counter pairs) in each negotiation sequence. Network training is stopped when either no improvement in performance is detected for a successive 2, 000 epochs or the number of epochs reaches 20, 000. Among the data generated using the intervals, 90% is used for training and 10% is used for tuning. We point out that although the generated data maybe learned usmg other t~chniques we have chosen to use neural networks for conve­ mence purposes.

We have randomly generated a total of 97 negotiation se­ quences, wherein each of B's counter-offer B's expected util­ ity of the gamble is greater than that of S's offer. The total number of negotiation transactions is 4 77 which gives an av­ erage of 5 transactions per negotiation sequence. The training instances are obtained by generating a total of 200 random data points for each observed negotiation transaction; 100 random data points for each of the region below and above the interval. The certainty equivalent, which is obtained from the control utility function, lies inside each interval. For each of the region below and above the certainty equivalent 100 test poi~ts are generated. We then evaluate the approach by companng how ~ell the model rerforms when trained using the mtervals agamst the test pomts from the control utility function.

Intuitively, not all negotiation transactions maybe useful. For example, an offer that is near the maximum domain value and a counter-offer that is near the minimum domain value has an interval width that is close to the width of the domain. Since we are using the interval to estimate the certainty equiv­ alent such a negotiation transaction would be less useful to one in which both the offer and counter-offer are closer to the certainty equivalent. Results of regression analysis suggest that useful interval widths are those that are about 50% of the domain width. We have used this result as a basis to eliminate data points that may not be useful in constructing the utility model.

To test the overall performance, negotiation sequences were grouped into subsets where normalized interval widths are no greater than 0.50, 0.45, 0.40, 0.35, and 0.30. The av­ erage interval wi~th for each subset is 0.35, 0.34, 0.31, 0.29, and 0.24, respectively. The average network performance of each of these respective subsets is shown in Figure l. The overall network performance increases as the average inter­ val width corresponding to the negotiation transactions de­ creases. The solid curve shows the performance of the util­ ity model in predicting whether an offer is preferred by B to a gamble using only implicit data points below the interval. This is important because B 's counter-offers only correspond to the lower limit of the interval. The dotted curve shows the accuracy of the model in predicting whether an offer is pre­ ferred by B to a gamble and whether B prefers a gamble to an offer. The mean accuracy is obtained by averaging the results using implicit data points below and above the interval. The results suggest that for intervals with average width of 0.24 the network can predict about 72% of the time whether an offer is preferred to a gamble by B. For intervals with aver­ age width ofless than or equal to 0.31, we are able to predict with more than 60% accuracy whether B prefers the offer to a gamble. In addition, the predictive accuracy of the model when implicit data points above and below the interval are used is better than a random guess. We ran four right-tailed z-tests and one right-tailed t-test using the following hypothe­ ses: Ho : f..t = 0.50 and Ha : f..t > 0.50. For the /-test the null hypothesis is rejected at a = 0.005. In each of the z-tests, the null hypothesis is rejected at a = 0.001.

In summary, we have outlined theoretical results that would allow us to construct utility models from negotiation actions. Results from our experiments suggest that our utility model provides significant predictive capability.