Multi-Agent Based Negotiation Research

Negotiation is a key form of interaction in systems composed of multiple autonomous agents. It is so important because the agents are autonomous (that is, they decide for themselves what actions they should perform, at what time, and under what terms and conditions ) and can have conflicting preferences over state of the world. Given the facts that such agents have no direct control over one another and there are often interdependencies between their actions, conflicts need to be resolved by the process of making proposals and/or trading offers, with the aim of finding a mutually acceptable agreement, in short, by negotiating. More specifically, we view negotiation as a bargaining process by which a joint decision is made by two parties. The parties first verbalize contradictory demands and then move towards agreements.In recent years, there has been a surge of interest in automated negotiation systems that are populated with artificial agents. This is due to both a technology push and an application pull. The technology push is mainly from a growing standardized communication infrastructure (e.g., the Semantic Web and the Grid) which allows distributed and heterogeneous entities to interact flexibly. The application pull is from domains (e.g., supply chain management, telecommunication network management, virtual organizations and electronic trading systems) that require self-interested software entities, representing different stakeholders, to interact in a flexible manner. So, multi-agent based negotiation is important for both theory research and real world practice.In this context, I have investigated several aspects of negotiation such as protocol and strategy and so on.First, I have surveyed the recent research progresses in auctions and multi-attribute negotiation, which are two hot research points in multi-agent negotiation.AI technology in auction mainly focuses on the decision making and coordination of multiple agents, such as the bid decision problem in multiple auctions and double auctions, Winner Determination Problems (WDP) in combinatorial auctions and coordination problems in multiple auctions. Towards WDP problems, people have proposed branch-and-bound search methods, supply and demand curves methods and atom proposal methods. Towards the bid determination problems in double auctions, people have designed some strategies, the two important ones are ZI and ZIP strategies. Other strategies include: GD,FM,CP,FL and RB strategies. Up to now, most works are about single issue auctions, only little ones are about multi-attribute. Compared with single issue auctions, multi-attribute auctions are more complicated and more challenging. Because: 1) Agents have complex preferences to multiple attributes; 2) The result space has n (n>1) dimensions. 3) There are'win-win'results. So, the future research direction is to find bid strategies and methods for multi-attribute auctions.Multi-attribute negotiation has been researched for many years, but has obtained little progress and has been paid more attentions in recent years. AI researches in multi-attribute negotiation are mainly to design negotiation models and strategies, to propose some research methods. Negotiation models include: package deal negotiation models and sequential negotiation models; negotiation strategies include: offer generation strategies, offer evaluation strategies and tradeoff strategies. Research fruits are: reactive negotiation models, reactive and deliberative negotiation models, reactive and deliberative and meta strategy negotiation models, non-linear evaluation function based negotiation models and constraint based negotiation models; Negotiation strategies include: time dependent strategy, resource dependent strategy, behavior dependent strategy, meta strategy, hill-climbing strategy, annealing strategy, and tradeoff strategy; Research methods include: fuzzy logic method, annealing method, set method, Markov decision method and game theory; Fatima have proved that among package deal negotiation , simultaneous negotiation and sequential negotiation, package deal negotiation can obtain optimal results. Existing problems are: 1) Most models use linear function to evaluate offers and this has three shortcomings; 2) In non-linear function complex contract research, there is prisoner dilemma; 3) In sequential negotiation models, interdependencies among attributes are ignored. Future research directions are: 1) Investigating new negotiation models; 2) Combining the advantages of package deal negotiation models and sequential negotiation models, to gain possibility of inheriting their advantages and so to complement their shortcomings.Second, I have proposed a bilateral negotiation based one to many negotiation protocol-OMN.This protocol uses emergent coordination method to coordinate multiple negotiation threads to resolve the existing problems in extant protocols, such as central node problem and synchronized negotiation problems. As a result, the distribution and dynamic scanning properties of negotiation systems are improved. Comparing with extant protocols, protocol OMN has following properties: 1) It can emit the central node in these protocols to improve the distribution of protocol; 2) It can support dynamic multi-thread negotiation to improve the scanning property of negotiation systems; 3) The function of time in negotiation is not only to end negotiation, but also to improve agreement chances to Agents; 4) It can support many forms of negotiation.Third, I have proposed a bilateral multi-attribute negotiation strategy. Using this strategy, negotiation agenda is the combination of exogenous agenda and endogenous agenda. Exogenous agenda uses n step agenda method, and endogenous agenda uses partial acceptance strategy. Partial acceptance strategy can generate local deal, when local deal changes to global deal, negotiation procedure completes. When there is some attributes which can not be agreed on, then negotiation procedure fails. Negotiation procedure under this strategy can obtain balanceable and Pareto optimal results, whose time complexity is O (n). Comparing with existing strategy, this strategy has following properties: 1) It can get over the local constraint violation instance; 2) It can conquer the local deal degeneration cases; 3) It can avoid the problem of important issues neglecting; 4) It can avoid the Prisoner's Dilemma problem; 5) It can fit in with both linear and non-linear functions; 6) It can reflect the interdependences between attributes; 7) It has lower time complexity.Fourth, I have proposed a new linear programming problems optimization method, i.e., the multi-agent negotiation based method. This method uses vote negotiation and the voting procedure has several rounds. First agents which have unsatisfied states propose their plans, then, all the agents select a plan to act, after acting the plan, each agent calculates its current value, updates its state and goes into the next round. When all the agents in a negotiation system have gotten satisfied states, we obtain the optimal result, otherwise, when partial agents have satisfied states, partial agents have unsatisfiable states, and there is no unsatisfied agents, then we obtain a reference result. Experiments show: with problems that have optimal solutions, this algorithm can convergent to an optimal result; with problems that don't have optimal solutions, the results obtained by this algorithm is better than that of goal programming. It can also be applied to constraint satisfaction problems and non-linear programming problems with little improvements. Future work: 1) To investigate the evaluation criteria of negotiation protols;2) To use learning mechanisms in negotiation strategy; 3) To investigate the using of negotiation method in constraint satisfaction problem and non-linear programming problems.