A heuristic model for concurrent bi-lateral negotiations in incomplete information settings

1 Introduction

Automated negotiation is a key form of interaction in agent­ based systems. Such negotiations exist in many different forms including one-to-one, one-to-many and many-to-many. Generally speaking, however, the latter two cases are dealt with using some form of auction protocol (be it single-sided or double-sided, respectively), while the former are often tackled using some form of heuristic method. Here we fo­ cus on the one-to-one case, in which one agent wants to pur­ chase a service 1 from another. Moreover, we consider com­ petitive situations in which the agents have no a priori knowl­ edge about the preferences of their opponents. In such cases, the agents exchange proposals, representing acceptable solu­ tions, until either an agreement is reached or the negotiation terminates with a failure.

To date, one of the inherent drawbacks ofbi-lateral negoti­ ation models is that the agent has to a priori identify a single partner to interact with. However, this is inefficient in an un­ certain setting where there are multiple providers of the ser­ vice that each have different characteristics. In this case, there are two alternatives: (1) negotiate sequentially with all the providers or (2) negotiate concurrently with them. The for­ mer has the disadvantage that it may result in lengthy negotia­ tion encounters, but has the advantage that it is comparatively easy to use the outcome of one negotiation to dictate behavior in subsequent ones. The latter case has the advantage of tak­ ing less time, but the disadvantage that coordinating behav­ iors among the various negotiation threads is more difficult.

*Department ofElectronics and Computer Science, University of Southampton, UK. Email: {tdnOlr, nrj}@ecs.soton.ac.uk

1 A service is here viewed an abstract representation of the capa­ bility of an agent.

Since we are interested in situations in time-constrained do­ mains (such as e-commerce and grid computing), we concen­ trate on the concurrent case and develop a coordinated bid­ ding model in which the various negotiation threads mutually influence one another. By mutually influence, we mean that the progress and agreement in one negotiation thread is used to alter the behavior of the agent in another thread for the same service. For example, having obtained a good deal in one thread, the agent may adopt a tougher stance in its other threads, to see if it can get an even better deal than the one it already has 2 ·

2 The concurrent negotiation model

The agent that wishes to purchase the service is called the buyer and the agents that offer the service are called the sell­ ers. Service agreements (contracts) are assumed to be multi­ dimensional (covering issues such as price, quality, quantity, etc.). The buyer has a deadline tmax by when it must con­ clude its negotiations for the service. Similarly, each seller i has its own negotiation deadline timax. All the agents have their own preferences about the service and this information is private (as are the strategies the individual agents follow) . The agents follow an alternating sequential protocol, in which the illocutions are offer (a proposal made by one agent to the other), counter-offer (a counter proposal from an agent in re­ sponse to a proposal it received), accept (accept a proposed offer),jinalize (secure a deal with the chosen seller), decline (reject the previously accepted offer) and withdraw (terminate the negotiation thread). The difference between an accept and finalize is necessary in this work to deal with the problem of concurrent encounters. If the buyer accepts an offer from a seller then this is viewed as binding on the seller (for a spec­ ified period of time that is assumed to be longer than tmax). However, it is not binding on the buyer. Thus, the buyer may accept several offers from multiple sellers in any one negoti­ ation episode. However, when it has completed all the nego­ tiations, the buyer will .finalize one of the accepted deals with one of the sellers and decline the others (thus freeing them from their commitment to the proposal). This two phase pro­ cess is necessary so that the buyer can use accepted deals as a base line for the subsequent concurrent negotiations. 3

2 This model differs from a one-to-many auction in that it allows direct interaction between the agent requiring the service and the providers offering it. This ability to exchange unmediated counter­ offers enables the participants to indicate their preferences and con­ straints directly to one another.

In more detail, the model for the buyer agent consists of two main components: a coordinator and a number of nego­ tiation threads (see figure 1). The negotiation threads deal directly with the various sellers (one per seller) and are re­ sponsible for deciding what counter-offers to send to them and what proposals to accept. For maximum flexibility, we assume that the buyer agent may adopt different strategies in each of its threads. We adopt separate semi-independent threads for reasons of modularity and coherence. The alter­ native of having every single negotiation move centrally co­ ordinated and intercepting all the bids received from all the sellers, is viewed as a computational bottleneck for the time­ constrained environments we are targeting.

Each negotiation thread inherits the preferences from the main buyer agent, including the acceptable ranges of values for each negotiation issue, the deadline of the negotiation and the current reservation value (the lowest utility value of an of­ fer that the agent considers acceptable). The coordinator de­ cides the negotiation strategies for each thread. After each ne­ gotiation round, the threads report back their status to the co­ ordinator. If a thread reaches a deal with a particular seller, it terminates its negotiation. Based on the coordination schema it is using (see section 2.1 for more details), the coordinator will then notify all other negotiation threads of the new reser­ vation value and it may change the negotiation strategy of some of them. The detailed working of the two components are described below.

2.1 The coordinator

The coordinator is responsible for coordinating all the nego­ tiation threads and choosing an appropriate negotiation strat­ egy for each thread.

As a first step, the coordinator acts like a blackboard for shared information about the ongoing encounters. It receives the current status from the various negotiation threads (in­ cluding the proposal's values), keeps a list of agreements reached and notifies the threads about any changes in their reservation values. Second, and more importantly, the coordinator decides the negotiation strategy for each thread ini­ tially and whether this should change over time to reflect any agreements that have been made to date.

3 This model is obviously biased in favor of the buyer and future work will look at relaxing this constraint so that sellers can also renege on deals.

To ground our model, at this time we consider the set of strategies S to be composed of the class of time dependent strategies advocated in [Faratin, 2001] for bi-lateral negotia­ tions in uncertain environments with time constraints. These strategies fall into three categories, namely: conceder (Sc), linear (SL) and tough (St) where S = Sc U S1 U St. All of the strategies start with the same initial value that is gener­ ated in relation to the deadline and the reservation value. The conceder strategy quickly lowers its value until it reaches its reservation value. The linear strategy drops to its reservation value in a steady fashion. Finally, the tough strategy keeps its value until the deadline approaches, then it rapidly drops to its reservation value.

In his empirical analysis of the behavior of negotiating agents that adopted these strategies, Faratin showed that if it is possible to approximate the type of the opponent then the agent can alter its strategy to be more effective. Given this observation, the coordinator attempts such a classifica­ tion. Specifically, at time t: 2 < t ~ tmax, called the analysis time, the coordinator tries to determine if a given seller is a conceder or a non-conceder. In particular, assume o; is the value of the offer that seller agent i made at time j : 0 ~ j ~ t. Then seller i is considered a conceder if Oi-Oi Vk E [2, t] : 0 , k -~· 1 > a where a is the threshold value k-1 k-2 set on concessionary behavior. There is a similar characterization of non-conceders and if the agent falls into neither category, it is judged not classified.

Let the set of conceder and non-conceder agents be rep­ resented by Ac and An, respectively. Now, given the set of strategies S = {Sc, S1, St} and the set of agents A = {A c, An}, the coordinator changes the strategy for each ne­ gotiation thread based on the type of the agent it is negotiat­ ing with, in order to try and obtain better outcomes. Agents belonging to the set A c are willing to concede in order to end up with agreements. Therefore, if the agent negotiates toughly with some of them (keeping its offer consistent), it may obtain a deal that has higher value than if it continues negotiating in its present manner. However, if the agent ne­ gotiates in this way with all the agents, it may not obtain any deals at all. Therefore, for reasons of balance, the agent will negotiate in a tough manner with a subset of the agents in Ac, specifically with a percentage (Pte%) of them. For there­ mainder of the agents in Ac, the strategy remains unchanged. Similarly, if the agent believes a particular agent is in the set An then in order to make sure it obtains a deal with some of them, it makes some of its own strategy more conciliatory. Specifically, for the agents belonging to the set An, a fixed percentage (P~%) of them will have their behavior made con­ ciliatory, while the remainder have their strategies unchanged. There is no change to agents whose behavior cannot be clas­ sified.

2.2 The negotiation threads

An individual negotiation thread is responsible for dealing with an individual seller agent on behalf of the buyer. Each such thread inherits its preferences from the buyer agent and has its negotiation strategy specified by the coordinator.

In each thread (see figure 2), there are three main subcom­ ponents; namely communication (represented by the dotted lines), process (represented by the bold lines) and strategy. The communication subcomponent is responsible for com­ municating with the coordinator. Before each round, it checks for incoming messages from the coordinator and if there are any, it passes them to the process subcomponent. After each round, it reports the status of the thread (including proposed proposals and the deal's value if an agreement is reached) back to the coordinator. The process subcomponent processes messages from the communication subcomponent. This can either be changing the reservation value or changing the strat­ egy. The strategy subcomponent is responsible for making offers/counter-offers, as well as deciding whether or not to accept the offer made by the seller agent. It uses the reser­ vation value as the basis for deciding whether to accept the seller's offer; in this case any offer with a value greater than this is accepted, otherwise a counter-proposal is made (unless the deadline has passed in which case a decline is sent).

3 Empirical evaluation

Having defined the model, the next step is to evaluate it. Given the aims of our work, we are interested in operational performance and so we decided to evaluate it empirically. In particular, we posed a number of hypotheses and evaluated them in different types of environment.

Our concurrent model is compared against a sequential ne­ gotiation model based on [Faratin, 2001]. In this model, all the agents' preferences, as well as the allocation of the strate­ gies, are drawn from the same distributions as the concurrent ones. The only difference with [Faratin, 2001] is that if the buyer agent reaches an agreement of value p in negotiation i, then in all subsequent negotiations, p will be its new reserva­ tion value.

We now tum to specific hypotheses. Due to the limitation of space, we cannot show the corresponding graphs to sup­ port our claims (see [Nguyen and Jennings, 2003] for more details), but, nevertheless we can summarize our main find­ mgs:

Result 1 The time to complete the negotiation is less for the concurrent model than for the sequential one .

Result 2 The number of proposals that are made in the con­ current model is less than the number made in the sequential model.

Result 3 To realize the benefits of concurrent negotiations, the buyer agent's deadline must not be too short.

Result 4 The final agreements reached by the concurrent model have, on average, higher or equal utility for the buyer than those of the sequential model (assuming the deadline is not too short).

Result 5 Changing the strategy in response to the agent's as­ sessment of the ongoing negotiation is equal or better than not doing so.

Result 6 To improve the performance of the concurrent model, the analysis time should be moderately early (to have time to have some effect) but not too early (so it is reasonably accurate).

Result 7 When dealing with sellers in Ac, the tougher the buyer negotiates the better the overall outcome it obtains.

4 Conclusions and future work

This paper has developed a heuristic model for managing concurrent negotiations in time-constrained settings where agents have no prior knowledge of their opponents or their types. Through empirical evaluation, we showed how the model leads to better deals, more quickly than its sequential counterpart. We also highlighted the importance of the time when the opponents' negotiation strategies are classified and on the response to this assessment in terms of the degree of toughness adopted.

There are, however, a number of areas that still require fur­ ther work. First, the means by which negotiation opponents are classified as being conceder or non-conceder needs to be refined so that this monitoring can be made on an ongoing basis (rather than as a one-off decision). Second, we need to allow for the possibility of sellers decommitting and then having these commitment changes feedback into the buyer's negotiation behavior. Third, we wish to extend the implemen­ tation so that the coordinator and the negotiation threads also embody fundamentally different models of bi-lateral negoti­ ation (e.g. based on constraint-satisfaction, game-theory or any other method that is likely to be effective). In this case, the key challenge is in designing the coordinator so that it can select, monitor and modify these strategies in line with the agent's overarching negotiation objectives.