Multi-issue Negotiation Paper

Comparison of multi-issue negotiation techniques for constructing intelligent distributed systems João de Oliveira1, Marek Karczewski2 2

1 [email protected] TU Delft, 1391992 [email protected] TU Delft, 9422407

Abstract: This paper presents a comparative study of different techniques for multi-issue negotiations for constructing intelligent distributed systems. We discern two separate approaches to multi-issue negotiations; the game theoretical approach and the heuristics approach. For both approaches known techniques are exemplified, together with their relative strengths and limitations. The main purpose of this paper goes from providing a clear overview of the existing possibilities in multi-issue negotiation to giving the reader a firm understanding of the practical applicability, the practical problems and the practical solutions in the field of real world multi-issue negotiations. In particular we will focus on the computational difficulties encountered in nonlinear multi-issue negotiations. Keywords: Multi-issue Negotiations, Distributed Agent Based Systems, Automated Negotiations, Autonomous Agents, Game Theory.

1 Introduction Distributed agent based systems are computer systems consisting of autonomously operating entities, the so called agents. Typically, the agents operate on physically separated machines. However, the agents do interact with each other, in order to reach some common goal. The goal can be diverse in nature, but in all cases, the participating agents can benefit in some way from reaching a common goal or at least from concluding the negotiation. The negotiating agents are self-interested and will strive to reach an agreement which will maximise their own benefits. Negotiation is a key form of interaction in multi-agent systems. It is the process in which disputing agents decide how to divide the gains from cooperation. The simplest form of negotiation involves two agents and a single-issue. As an example, consider a scenario in which a buyer and a seller negotiate on the price of a good. To begin, the two agents are likely to differ on the price at which they believe the trade should take place, but through a process of joint decision-making they either arrive at a price that is mutually acceptable or they fail to reach an agreement. Since agents are likely to begin with different prices, one or both of them must move toward the other, through a series of offers and counteroffers, in order to obtain a mutually acceptable outcome. However, before the agents can actually perform such negotiations, they must decide the rules for making offers and counteroffers. That is, they must set the negotiation protocol. An example of a distributed multi-issue bargaining protocol with dependent issues is presented in [4].

The protocol specifies the rules of encounter between the negotiation participants. That is, it defines the circumstances under which the interaction between agents takes place, what deals can be made and what sequences of offers are allowed. In general, agents must reach agreement on the negotiation protocol to use before negotiation proper begins. Besides handling a single issue, a negotiation protocol can also be designed for handling multiple issues. In that case, we speak of multi-issue negotiations. If the issues are not independent of each other – as will often be the case in real world cases – then we speak of non-linear multi-issue negotiations. In this paper we will be focusing mostly on non-linear multi-issue negotiations. There are many ways possible in which the rules for negotiation can be set up and enforced. The two main approaches that are discerned in this paper are what we call “the game theoretical approach” and “the heuristics approach”. In the game theoretical case, the negotiation rules are designed to reach equilibrium, for instance by following an optimal bidding agenda[1]. Once the equilibrium is reached, it is unlikely that the agents will change their behaviour. The equilibrium can thus be seen as an end result of negations. The rules that lead to the equilibrium can be set up in order to reach a specific goal, for instance to maximise the value of all the deals reached by all the agents involved. This is known as “maximising social welfare” or “approaching pareto-optimality” which will also be addressed further on this paper more precisely in chapter 4.1. In the case of game heuristics, the agents are more flexible in their behaviour. They can adapt new bidding strategies, based on the information they learn during negotiation, for instance by using utility graphs [18]. In this case, the end result of the negotiation is not so much determined by the common “rules of the game”, as it is determined by the private behavioural rules of the different agents. Another important distinction is, that in case of heuristics, the information exchange between agents is often considered to be more restricted. Nevertheless, also using the heuristics approach, it is possible to conjure strategies for maximising social welfare. In [6] an example is given of the efficient use of incomplete preference information in automated multi-attribute negotiations, while approaching the pareto-efficient frontier. Besides setting the rules governing the negotiation, there is another important matter that must be settled for each agent before he can start negotiating. Every agent must answer the question “how much is a bid worth to me”. This is not a trivial question. In order to answer it, the agent must search its own utility space to find optima suitable for a bid. The utility space is determined by the utility function. The utility function describes a valuation to a contract, i.e. to a concrete set of issue values. In order to find contracts that are acceptable to itself, an agent must find optima in its utility space, which are above some predefined threshold value. Computationally, this can be a hard problem to solve [17]. As mentioned before, next to answering questions concerning the benefit of a single agent, we should also consider the question about the summed value of all the contracts of all the agents involved in the negotiations. In real world settings, we will often be interested in reaching such results, which maximise the social welfare for all the parities involved. In fact, this maximisation will often be the primary goal of multi-issue negotiation. The field of multi-issue negotiations is related to numerous other fields of computer science. Here is a list of the relations one can expect to find, when doing a study of this subject matter:

• Game Theory: game theory is in fact at the hearth of multi-issue negotiations. Game theory allows us to answers questions such as how a certain negotiation strategy will allow us to maximise the benefits of all the involved agents. • Artificial Intelligence: arriving at better bidding strategies or improving the optimisation algorithms for searching the utility space, might mean using techniques known from the field of artificial intelligence. As an example one can mention the use of genetic algorithms to do an efficient search of the utility space [23]. • Distributed Systems: a practical implementation of a multi-issue negotiation strategy will involve using techniques for constructing distributed systems. Matters such as mutual exclusion, election, message ordering, synchronisation, termination and deadlock detection might all have to be considered, in order to allow multi-issue negotiations to take place in practice. An example of architecture can be found in [9]. • Computability Theory: knowing the complexity of a given method for multi-issue negotiations is important for answering questions about its feasibility, scalability and time constraints in practice. • Optimisation Theory: many problems encountered in multi-issue negotiations are complex in nature. Searching through the utility space to find optimal contracts, can pose a hard problem to modern day computer hardware. By use of optimisation techniques, we can significantly reduce the time necessary to find the right answers. One example of the use of simulated annealing as an optimisation technique can be found in [15]. This paper is organised as follows. Section 2 focuses on “the game theoretical approach” to multi-issue negotiations. Section 3 focuses on “the heuristics approach”. In section 4 the basic problems encountered in non-linear negotiations are discussed. In section 5 we show some examples of the practical applicability of multi-issue negotiation systems for solving real world problems. The paper is concluded with section 6.

2 Game Theoretical Approach In Multi-issue negotiations, as mentioned in the introduction, there are two main protocols for negotiating issues. The first one as it’s stated already in the introduction is the “game theoretical approach”. This approach has received considerable attention from the scientific community over time. Due to its complexity, the game theoretical approach usually focuses on bilateral negotiations, that is, negotiations between two actors. We have two ways of doing bilateral multi-issue negotiations in the game theoretical approach. The first one is by negotiating all the issues together and the other one by negotiating them one-by-one by using an agenda. 2.1 Negotiating all issues at the same time Although a very appealing model, this approach carries very high computational and time costs. The appeal of this approach lies in the opportunity to explore trade-offs [1].

Usually this model for negotiation takes into account certain assumptions, like the fact that agents have limited knowledge of each other’s preferences and strategies. Another assumption is that negotiation tasks are costly in terms of computational space. Given the last assumption, some models opt for a distributed approach [1] where all the agents can participate in order to achieve a better computational effect. Another effect of such restrictions or assumptions is that in order to have an efficient model for negotiations, we have to consider the usage of heuristics algorithms [7], which we will see more in detail in the next section on heuristics. 2.2 Negotiating issues one by one In this approach, the issues have to be negotiated according to the order specified in the agenda. There are two ways to decide upon the agenda: 1st pre-decision before the negotiation rounds start; 2nd the next issue is decided by the agents one after the other [1]. Several studies have been conducted about the importance of the order of the issues to be negotiated. According to Fershtman, if for example we have two issues X1 and X2, then we can have one agent preferring an agenda with the order X1,X2 and the other X2, X1[5]. Another solution was proposed by Fatima et al, which tries to study the strategies of agents by defining an agenda that is decided by rounds. This means that there are k rounds where in each round you can decide upon the agenda for a set of issues. [2] The basic thought about this ordering of negotiation, and of deciding which issues to negotiate one-by-one, is that in certain scenarios the utility of both agents can be improved by negotiating in the correct order. However, since the information an agent has about the other agent is incomplete, the agents can have difficulty to find such scenarios. In order to solve this handicap [2] we can take advantage of the use of a mediator. 2.3 Restraints in Negotiation Real-life bargaining has characteristics that must be taken into account while studying multi-issues. An example of a characteristic sometimes discarded but that has significant importance is Time restraints. Examples of time restrains can be: 1) A product has an expiration date; 2) A seller is under pressure from part of the buyers to take a decision; 3) Buyers have products depending on a particular item, therefore they want to go on with the acquisition. In a simulated environment, in multi-issue negotiation, we should be able to take time-restraints into consideration. Take the example of [2]: 1. Deadline for the negotiation: both (the seller and buyer) need to ensure that the negotiation ends before a certain time; 2. Lost of utility over time: one of the intervenient, might be loosing utility, with time, as a result of not getting the service; 3. Gain of utility over time: one of the intervenient might gain utility with time, for example the seller by not selling the product right away.

From these examples we can see that time restraints, as well as other restraints can play an important role in negotiations. Another interesting effect that can be witnessed in real-life negotiations is the ‘attachment effect’. This term refers to the fact that human bidders often get ‘attached’ to certain outcomes of the negotiation and will sometimes behave irrationally to obtain these outcomes. For instance, if a bidder that has had the highest bid for some good for a prolonged time, he can become attached to the idea of owning this good. If somebody else outbids him, the bidder might feel inclined to raise his bid, even if the initial bid was already at the maximum of what he was willing to give for the good in question [22]. 2.4 Necessary knowledge from opponent The biggest disadvantage of the game theoretical approach is that usually the models have the assumption that actors can have “shared knowledge”. Shared knowledge stands for information that actors shared among themselves, from bidding preferences, negotiation tactics and their own utility functions. However, several theoretic models have been proposed, that do not require complete information about the opponent, only partial information. Examples of these models can be found by A. Rubinstein who has taken time preferences into account and has developed a model in which agents have incomplete information. Fudenberg et al. also analyses bilateral negotiations, in which reservation prices are uncertain, and Sandholm and Vulkan consider uncertainty over agent deadlines [2]. Fatima and Wooldridge also examine the influence of deadlines and draw the conclusion, that optimal outcomes are reached when the issues are negotiated together in one package[3]. Nevertheless, these models all focus on knowing the preferences á priori from the agents in the negotiation. A more realistic model can be found by Shaheen S. Fatima et al. [2], that also sees the need to have shared knowledge, but by acquiring it with experience, with time. Fatima states that only after a certain number of rounds it is legitimate to say that the actors can learn each other’s preferences. Some solutions in order to avoid the necessity of agents sharing common knowledge go on introducing a mediator. This solution is usually more comfortable then having the agents sharing the knowledge, giving that the mediator is usually a neutral agent with incentives to improve the welfare of the negotiation and to protect the privacy of the shared information.

3 Heuristics The second approach, the most studied nowadays and where our paper has more focus on, is the heuristics approach. In this approach the agents can learn progressively throughout time and adapt their strategy based on the acquired information. The main idea behind the heuristics approach in negotiations is the conjecture that the most efficient way to get a continuous improvement of the negotiation strategy used by the agents is to use heuristic algorithms. The efficiency of these algorithms will improve over time, based on the information that is learned during negotiation.

A basic assumption usually applied to these models, is that you don’t have to always wait for the perfect answer since this carries a high computational cost. Given this line of reasoning, the models try to use optimisation algorithms to find a suitable solution for the problem. Such a solution might not be the best one possible, but in many cases it can be proven, that it is within acceptable limits. Many of the research into heuristic models of negotiation has been focusing on linear issues. As mentioned previously, linear issues relates to when the negotiated issues are independent of each other. In case of non-linear issues, the complexity of the models grows rapidly since issues have dependencies which makes the negotiation much more complex. In the next sections we will explore the differences between linear and non-linear issues in the heuristics approach. 3.1 Linear Issues The term linear issues refer to cases when issues can be dealt independently, so that they do not influence each other. Take for example the case of a buyer purchasing articles to furnish the house, one can choose to just purchase articles that don’t have to match with each other. In case we would want the products to match with each other, we would be dealing with non-linear issues. Linear issues can be divided into “Linearly Additive Issues” (or “One-to-One”) and “One to Many Issues”. For example in the one-to-one cases, the agent opens a single channel to another agent and negotiates about one topic/issue. In the one-to-many case, it is common for multiple agents to negotiate with either a single or many other agents. The latter category is usually handled by models based on online auctions [10]. An interesting line of thinking was presented by Jennings and Nguyen [12]. It is suggested to let the buyer post proposals and counter-proposals in multiple concurrent negotiations. This approach enables the buyer to provide an indication of the regions of the utility space where he would like to see the agreements lie. The following figure illustrates the basic model of this approach. We can see that the controller governs many simultaneous negotiations.

Fig. 1. Figure taken from [12]. The figure gives a representation of a model of negotiating multiple contracts at the same time.

3.2 Non-Linear Issues In contrast with the case of linear issues, in this case the issues are not independent of each other. Non-linear issues account for the most complicated cases of negotiation. The study of non-linear issue negotiation generally focuses on binary issues and continuous issues. The difference between binary issues and continuous issues lies in the values that the issues can take. Binary Issues have the value “true” or “false” during negotiation. Take the example of a negotiation of furniture items, where the seller will offer them to the buyer. In case of binary issues we can assume that the negotiation takes a form like: “Do you want to buy a chair?” the buyer can reply “true” or “false”. In case of continuous issues the answer would be in the form “I will give 10 € for it”. Like mentioned in [14], many real-world contracts, are much more complex than just having a few independent issues. This is why algorithms for non-linear multiissue negotiations play such an important role. In section 4 we will go deeper into the problems associated with non-linear negotiations and present a number of solution to handle these problems. 3.3 Comparison of linear and non-linear issue negotiations The basic difference between the two types of negotiation is that in the non-linear case, we are dealing with interdependencies between issues. This implies that we cannot separate the negotiation of issue X from the negotiation of issue Y. Instead we have to negotiate issue X and Y at the same time. This basic problem brings the need to account for specific complexities in the negotiation. For example, given that the issues are negotiated at the same time, and that the outcome of Issue X can have an impact on the outcome of Issue Y, we have to be extra weary of time constraints. Time constraints will obviously have a stronger influence in the non-linear case, because they can apply to a number of issues simultaneously. This gives rise to more complex algorithms for determining the negotiation strategy. Another important difference between these two cases is the fact that different rules apply to the use of a mediator. For example, in case of non-linearity, the mediator has to acquire all the preferences at the same time from the agents, to know which combinations to make. One good method to deal with uncertainty about the preference of other agents is by using utility graphs [18, 19]. In short we may say, that non-linearity in negotiation brings a significant increase in computational complexity. It will often require more sophisticated methods for determining the negotiations strategy and reaching outcomes that approach the paretoefficient frontier.

4 Non-linear multi-issue negotiations In case of non-linear multi-issue negotiations, we must consider some serious obstacles. Examples such as the high need for computational power and the long duration of the negotiation make non-linear negotiations harder to handle. Perhaps

this is one of the reasons why up to this day the topic of non-linear negotiations has seen significantly less research than the linear case. One of the solutions normally pointed out to solve this type of negotiations is by using a mediator. However, this approach also brings some peculiarities with it. An interesting problem was found in the research on using a mediator [14, 15]. The authors studied the behaviour of agents using different negotiation strategies. According to the studies, strategic behaviour from an agent that takes into account the other agent’s strategy can bring a considerable advantage in the negotiation. A first model was proposed that involves understanding the other agent’s strategy or tactic. However with this model there is the problem of the time needed to discover the other agent's strategy. Another problem is that in the initial model, the architecture was such that an agent could easily push the mediator to go a bit more towards its preference by exaggerating on its real preferences. Another problem that challenges researchers in non-linear negotiations is that interdependencies between issues can not be disregarded. This means, that issues can't be decided by themselves. Consider the example of buying a chair. "Do you want to buy this chair?” A possible answer with interdependencies between issues: "Only if I can buy that other one for 5€ and this one for 6.5€”. We can see that in real life, deals are often made in the form of packages. In order to solve the previous problem, Valentin et al, came up with the solution to model the negotiation using utility graphs [18]. By resorting to utility graphs the negotiation model becomes scalable and the computational costs do not increase exponentially as the number of negotiated issues increases. Another big disadvantage of the non-linear case is that there exist a big number of negotiation mechanisms of good quality, that are well-suited for linear negotiations, but that unfortunately can not be applied to non-linear negotiations. This makes the study of this field significantly different than the studies made on linear issues. This is to say, in non-linear negotiations one cannot “recycle solutions” that work for linear cases. Taking the algorithm from [14, 15], we see another considerable disadvantage that is common for non-linear issue negotiations. Whenever the number of issues to be negotiated increases, the computational costs will also increase drastically. This increase is oftenly exponential. 4.1 Improving the global negotiation welfare The welfare that results from negotiation can be expressed as the reached utility values of the negotiated contracts. The global negotiation welfare is the combination of all the agents’ individual contract values. In a negotiation environment it is normal to find agents minding their own preferences, and striving to increase their own individual gain or welfare. There is a common interest to try to improve the social welfare of the negotiation since this would make the negotiation more fruitful for all the agents involved. and better prospects for the future negotiations, Having this goal in mind, several researchers tried to find ways of creating the right conditions to achieve a higher social welfare. An example of such case is the research done by Nicholas R. Jennings et al [8], which provides a study about using rewards in persuasive negotiation. Jennings

claims that by using the rewards system where the agents are evaluated by their offers and rewards throughout negotiation rounds, a better global welfare can be achieved. The model proposed by Jennings relates to the real-world where a compromise is achieved by the people negotiating, where future rewards are given and asked, as a result of the current negotiation. This model, also manages to use less messages to trade between agents. Another way of achieving a better social welfare is by changing the architecture of the negotiation. In the non-linear issue category Farantin, delights us with 2 papers [14,15] which by using an annealing mediator helps to achieve a higher welfare. The table presented bellow illustrates the benefits that this process brings. Agent 2 exaggerates Agent 1 exaggerates [.91] .79/.79 [.92] Agent 1 tells truth .81/.78 Table 1. This table is taken from annealing mediator can bring.

[14]

Agent 2 tells truth [.92] .78/.81 [.98] .84/.84

and shows the advantages that the model with the

As you can see from the table above, by changing the architecture of the negotiation Farantin creates the situation in which the agent actually gets benefits from revealing its true preferences or strategy. To do this, Farantin has architected a scheme for mapping the agent’s vote. Basically the agents have the choice to rate contracts in a range of “Strong Accept” to “Strong Reject” and then the mediator according to a map decides if the contract should be approved or not. The next table is taken from the paper and gives a better overview of the scheme used by the mediator. Strong accept (1) Weak Accept (0) Weak Reject (-1) Strong Reject (-2) Strong Accept (2) accept (1)

Accept (1)

Mixed accept (0)

Weak reject (-1)

Weak Accept (1) Accept (0)

Accept (0)

Weak reject (-1)

Medium reject (-2)

Weak Mixed accept (0) Reject (-1)

Weak reject (-1)

Medium reject (-2) Strong reject (-3)

Strong Weak reject (-1) Reject (-2)

Medium reject (-2) Strong reject (-3) Very strong reject (-4)

Table 2. This table is taken from decision about the contracts.

[15]

and illustrates the scheme used by the mediator to take

Another way to improve social welfare, is by usage of trade-offs [7] as mentioned in section 2.1. Most of the models of multi-issue negotiation do not study the possibility

of trade-offs. Each decision variable is treated independently, and the connections between issues that would allow to use trade-offs are not explored. One example of a model that tries to improve social welfare is the model by Farentin et al [7]. In this model two basic rules are proposed for negotiation: 1. Select a set of contracts that have the same value for agent A and send it to agent B 2. Agent B gives for these set of contracts a preference value. This model works well, since agent A has an interest in keeping a good contact with agent B for future negotiations. If a contract X is higher than Y for agent B but both have the same value for agent A, then it will result that agent A will choose contract X in order to get a better social welfare. Even though the basis idea is quite simple, this algorithm can get complicated as it operates in rounds and as it involves multi-issues. 4.2 Methods for handling complex utility spaces In the paper by Hindriks, Jonker and Tykhonov[24] an interesting proposal is made for dealing with the complexity arising in non-linear multi issue negotiations. The authors present a method for transforming a complex utility space based on interdependent issues, into a much simpler approximation of that space. The approximation can then be used as the basis for negotiation. This would allow for much lower computational costs for dealing with negotiations in which complex utility spaces are involved. Another approach is presented in the paper by Lau [23]. The author proposes the use of a genetic learning algorithm to help the agent decide upon the best negotiation strategy to be used in restrictive environments. Examples of restrictive environments include short negotiation times, big utility spaces, limited computational resources and so on. In such environments the algorithm outperforms a theoretically optimal negotiation mechanism. A bidding based approach that uses adjusted sampling is proposed by Hattori and Klein [16] for exploring large non-linear spaces. In this approach a sample is taken from the utility space that is then adjusted to find a local optimum yielding a higher utility value. If that optimal value is not above a certain threshold then another sample is taken and adjusted until a suitable contract is found that can be presented as a bid. This method works well for large utility spaces. We can find a similar approach in The paper by Fujita and Takayuki Ito [17]. Here the authors use a mechanism for adjusting the threshold value that determines whether the found contract can be presented as a bid to the other party. The usefulness of this approach lies in the fact that it reduces computational cost while maintaining enough optimality in finding good deals.

4.3 Methods for handling incomplete information As mentioned earlier, next to complex utility spaces that emerge in non-linear negotiations, we will also be faced with the problem of incomplete information. In real world settings it is quite obvious to assume, that the agents will not be willing to share too much of their preference information with their negotiation partners. In fact, it will often be desirable to share as little information as possible. In order to handle the problem of incomplete information a solution is proposed in the paper by Han La Poutré and Valentin Robu [19]. An assumption is made about the preferences of a buyer agent based on previous actions by that buyer. These preferences are modelled by an utility graph. The utility graph holds information about the view a buyer could have on different items. A buyer might find some items complementary, so that combinations of these items hold a high value for him. He might find other items substitutable, so the seller can change one item for another without decreasing the utility from the viewpoint of the buyer. By using utility graphs it is possible to reduce the number of negotiation steps necessary to find suitable contracts and to reach pareto-efficient solutions even in complex non-linear and multi issue negotiation settings.

5 Practical applicability of multi-issue negotiations The presented techniques for multi-issue negotiations can be applied in a number of practical settings. It is obvious to consider an agent based system incorporating multiissue negotiations in all those cases, where autonomous systems must exchange information in order to reach an agreement about the terms of cooperation. In this section we will therefore present the use multi-issue negotiations in a commercial setting. 5.1 E-commerce Perhaps the most prominent field of system interaction where multi-issue negotiations can be successfully applied is e-commerce. In a typical e-commerce setting, we are dealing with multiple parties that must undertake negotiations to settle the terms in the exchange of goods. The goods generally being the product sold and the amount of money exchanged for it. There are many different scenarios one can consider. There can be one buyer and many sellers. There can be one seller and many interested buyers. The negation can concern one good or many goods. In a complex scenario, buying one good might be dependent on selling another. Automatic negotiations between agent based systems can help in finding the most beneficial contracts for the parties involved, even within complex scenarios [21]. Also in case of e-commerce we should be weary of issue interdependency. If the value of contracts depends on the combinations of goods and not only on the values

that the goods have themselves, then we say, that the goods under negotiation are interdependent. This will in fact be the case in most real-world negotiations. As an example consider an agent negotiating the acquisition of computer software. If the seller proposes an application that runs on the Mac and in the same package he offers the Windows operating system, then the value of such a contract will be very low, as the application will not work under the proposed operating system. In many cases the value of the whole contract is dependent on the exact combinations of goods contained in it. Interdependency of negotiated issues leads to non-linear utility functions. Nonlinearity causes the utility space to become complex and we need to use optimisation techniques in order to find suitable optima [16]. Using techniques to find welfare maximising deals in multi-issue negotiations can lead to optimal contracts between business parties. Especially in complex settings, where there are many possible sellers and buyers, these techniques can lead to better business results, than traditional forms of information exchange and contract negotiation. In the paper by Gerding and La Poutré [20] for negotiation strategies that increase the efficiency of bargaining outcomes we can see this form of exchange. Another field of commerce in which multi-issue negotiations can prove very useful is logistics. Imagine a fleet of trucks negotiating the conditions for transporting loads of cargo from different depots to different destinations. Every depot and every truck could have an automated agent for doing the negotiations. Every depot could negotiate with a number of agents simultaneously, in order to find the best possible deal for having the cargo shipped. Although logistics seems similar to the e-commerce setting, there is an important difference. It lies in the fact, that moving the goods physically from place to place is a main aspect of negotiations. The distance that the goods will travel and the time it takes to ship them, could be important issues to be negotiated between the parties. An example of a setting in which agents are having simultaneous negotiations with multiple parties is presented in the paper by Nguyen and Jennings [11]. The main point of the paper is that in order to reach good results, it is necessary to have flexible rules for commitment and de-commitment of the deals made. Another similar example can be found in the paper by Gerding, Somefun, D. and La Poutre [13]. In this last paper, the authors present several one-to-many bargaining strategies for the seller agent, which are tested for effectiveness by means of an evolutionary algorithm.

6 Conclusions Much of the research up to date has been concentrating on linear issue negotiations. These kinds of negotiations are characterised by linear utility spaces with a single optimum that is easily computable. It is relatively easy to find good deals for the involved agents and to devise methods for maximising the social welfare. Unfortunately linear negotiations bear too little resemblance to real world negotiations. In the real world, most negotiations will show a dependency between the negotiated issues. “I will buy this car, but only if I get the air-conditioning system for free”. In fact most e-commerce settings – where multi issue negotiations can bring many benefits – will exhibit these kinds of issue dependencies.

When the value of one issue depends on the value of another, then we speak of interdependent issues. Interdependent issues lead to non-linear utility functions with multiple optima. In terms of computational cost, it is much harder to find suitable optima in such spaces. It is also harder to devise methods for maximising the social welfare of negotiating agents. In an e-commerce setting, this would mean that it becomes harder to find negotiation solutions that maximise the profits of all involved business parties. This brings the need for advanced algorithms to solve these kinds of problems. In this paper a number of algorithms from different authors have been presented. The proposed solutions range from optimisation algorithms for searching the utility space, through special negotiation settings like using a mediator, to increasing the efficiency of agents in finding good deals by using evolutionary algorithms or utility graphs. In very complex cases, a combination of these methods might be necessary. As the use of automated agent based multi-issue negotiations in concrete business settings can bring considerable advantages to involved parties, further research into efficient algorithms seems strongly recommended.

References [1] Optimal Agendas for Multi-Issue Negotiation [2003] (Shaheen S. Fatima, Michael Wooldridge, Nicholas R. Jennings) [2] An agenda-based framework for multi-issue negotiation [2003] (Shaheen S. Fatima, Michael Wooldridge, Nicholas R. Jennings) [3] Multi-Issue Negotiation with Deadlines [2002] (Shaheen S. Fatima, Michael Wooldridge, Nicholas R. Jennings) [4] A Decentralized Bargaining Protocol on Dependent Continuous Multi-Issue for Approximate Pareto Optimal Outcomes [2005] (Nicola Gatti, Francesco Amigoni) [5] C. Fershtman, The importance of the agenda in bargaining, Games and Economic Behavior [6] Automated Multi-Attribute Negotiation with Efficient Use of Incomplete [2004] (Catholijn Jonker, Valentin Robu) [7] Using similarity criteria to make issue trade-offs in automated negotiations [2002] (P. Faratin, C. Sierra, N.R. Jennings) [8] Negotiating using Rewards [2007] (Sarvapali D. Ramchurn, Carles Sierra, Lluis Godo, and Nicholas R. Jennings) [9] An Agent Architecture for Multi-Attribute Negotiation [2001] (Catholijn M. Jonker and Jan Treur) [10] A fuzzy constraint based model for bilateral, multi-issue negotiations in semi-competitive environments [2003] - (Xudong Luo, Nicholas R. Jennings, Nigel Shadbolt, Ho-fung Leung, Jimmy Ho-man Lee) [11] Managing commitments in multiple concurrent negotiations [2005] - (Thuc Duong Nguyen and Nicholas R. Jennings) [12] Coordinating multiple concurrent negotiations [2004] - (Thuc Duong Nguyen and Nicholas R. Jennings) [13] Automated Bilateral Bargaining about Multiple Attributes in a One-to-Many Setting [2004] (Gerding, E. H., Somefun, D. J. A. and La Poutre, J. A.) [14] Using an Annealing Mediator to Solve the Prisoners’ Dilemma in the Negotiation of Complex Contracts [2002] (Mark Klein, Peyman Faratin, and Yaneer Bar-Yam) [15] Negotiating Complex Contracts [2003] (Mark Klein, Peyman Faratin, Hiroki Sayama, Yaneer Bar-Yam)

[16] Multi-issue Negotiation Protocol for Agents: Exploring Nonlinear Utility Spaces [2007] (T Ito, H Hattori, M Klein) [17] A Preliminary Analysis of Computational Complexity of the Threshold Adjusting Mechanism in Multi-Issue Negotiations [] (Katsuhide Fujita and Takayuki Ito) [18] Modeling Complex Multi-Issue Negotiations Using Utility Graphs [2005] (Robu, V., Somefun, D.J.A., La Poutré J.A.) [19] Retrieving the Structure of Utility Graphs Used in Multi-Item Negotiation through Collaborative Filtering of Aggregate Buyer Preferences [2006] (Robu, V., Somefun, D.J.A., La Poutré J.A.) [20] Efficient Methods for Automated Multi-Issue Negotiation: Negotiating over a Two-Part Tariff [2006] (D. J. A., Gerding, E. H. and La Poutre, J. A.) [21] A Decentralized Model for Multi-attribute Negotiations with Incomplete Information [2006] (Guoming Lai and Katia Sycara and Cuihong Li) [22] Negotiation Fever: Loss Aversion in Multi-Issue Negotiations [2007] (Henner Gimpel) [23] Towards Genetically Optimised Multi-Agent Multi-Issue Negotiations [2005] (Raymond Y.K. Lau) [24] Eliminating Interdependencies Between Issues for Multi-issue Negotiation [2006] (Koen V. Hindriks, Catholijn M. Jonker, Dmytro Tykhonov)