S t u d y o n I n t e l l i g e n t N e g o t i a t i o n u s i n g G e n e t i c N e t w o r k
P r o g r a m m i n g E v o l v i n g b a s e d o n A g r e e m e n t C o n d i t i o n s
Md. Tofazzal HOSSAIN
Graduate School of Information, Production and Systems Waseda University
Waseda University Doctoral Dissertation
June, 2013
2
Abstract
In recent years, much research has been done to solve and optimize the problems in Multiagent systems (MASs). However, the strategies of agents in MASs are usually predetermined, therefore, may not obtain the optimal solution in complex real-world problems. For example, in a simple two-party price negotiation, agents try to maximize inherently conflicting objectives regarding the price of a product. Generating an intelligent and optimal solution that would be acceptable by both the agents is often difficult, time-consuming and inefficient under such conditions. Therefore, it is expected that the negotiation system should adopt intelligent decision support systems, so that the negotiating agents can intelligently determine the optimal or near optimal solutions automatically in the complex real world negotiation situations. In this respect, the application of advanced methods and algorithms such as Evolutionary Computing (EC) method has a lot of promise in supporting these negotiations. Therefore, in this research advanced, automated and intelligent negotiation solutions are obtained considering possible complex and practical real-world negotiation situations and using a newly developed Evolutionary Computation, named Genetic Network Programming (GNP), which has the directed graph-type gene structures to develop and design the required intelligence decision making mechanism for agents. As a result, GNP is considered to be well-suited for optimization problems of agents of MASs. Toward these objectives, in the first step, a basic / common bilateral negotiation system has been designed and developed with a view to realize the intelligent decision making ability of agents preciously and concretely. On the other hand, intelligent and automated decision making ability of agents cannot be realized in the negotiation using the conventional approaches of MASs. This is because the conventional methods do not consider the problem environments using the advanced methods and techniques, instead conventional methods usually use mathematical, statistical or economical calculation to solve the problems. The proposed negotiation systems are designed and developed utilizing Genetic Network Programming (GNP). The main objective of this bilateral negotiation system is to examine the intelligent decision making ability of agents preciously and concretely in the negotiation through GNP evolution.
3
In a different negotiation situation, the possibility is that more than two negotiators may participate in the negotiation in a multilateral negotiation environment. This is because, in real-world situations, negotiations often are multilateral by nature.
Therefore, the previous study on bi-lateral negotiation is extended and a multilateral negotiation system is proposed, where more than two agents can participate in the negotiation. In usual cases, the study on multilateral negotiations, where many buyers and sellers participate in the negotiations, is applied to auctions. It is found that the negotiation process of auctions is different from the pure multilateral negotiation, because in auctions, the offers and counter offers of the buyers and sellers are open to all. As a result, the privacy of the negotiators is lost. Moreover, the competition between buyers and sellers in auctions is hard to realize, because the negotiation is done in public, therefore, the buyers and sellers can follow what the other buyers and sellers proposed in the previous rounds. In the proposed multilateral negotiation system, the competitive attitude between negotiating agents is realized, because when one agent wins, the opponent loses and vice versa. In the proposed systems, the negotiation is done pair wise until the agreement is made, where the offers and counter offers of one pair of negotiating agents are not open to the other pair of negotiating agents. As a result, real competition can be realized in the negotiation, which cannot be realized in the auctions.
In the automated and intelligent negotiations, much research has been done dealing with a single issue, usually price, in a bilateral negotiation. In practical life, multi-issue negotiation is very common. Moreover, it is regarded that the price alone cannot satisfy the demand of the parties, where other issues are also relatively important while buying or selling goods or products. Therefore, a multi-issue negotiation model is proposed, in which multi issues are a part of the negotiation. In some recent studies on the multi- issues, agents usually propose a combined offer on multi issues (i.e., a single offer combining multi issues), or settle the negotiation issue by issue. It is found that the combined offer on multiple issues is like a single-issue negotiation. Issue-by-issue settlement can be considered as a series of single issue negotiations. On the other hand, the proposed system is not like a single issue settlement or combined offer on multi issues. An agent can propose any issue in each negotiation round, and finally an
4
agreement will be made when agents meet the agreement condition. In the proposed system, 3 issues, i.e., the price, delivery and warranty are considered, although it is possible to add more issues using the proposed system. Finally, to evaluate the performance of the proposed system concretely, the results of the proposed system are compared with those of the conventional, i.e., common negotiation systems (where agents are not intelligent). In the conventional system, the negotiation concept of prominent Monotonic Concession Protocol (MCP) is used. The performance of agents is compared in both systems in detail.
In usual cases, agents in conventional Multiagent Systems (MASs) consider their own benefits only; as a result, the strategy of agents is limited or one-sided. Masbiole (Multiagent Systems with Symbiotic Learning and Evolution) has been proposed as a new methodology in conventional Multiagent Systems (MASs) based on symbiosis in the ecosystem. In Masbiole, agents evolve considering not only their own benefits and losses, but also the benefits and losses of opponent agents. As a result, agents can change their strategies more flexibly. Therefore, in this study, a negotiation model is proposed and developed using Masbiole as well as GNP, with the aim to study the effectiveness and efficiency of Masbiole in dynamic problems. In the proposed system, it has been realized how 6 kinds of symbiotic relations of Masbiole system can be utilized in various business strategies between the organizations considering the symbiotic relations toward others. Therefore, the proposed system can show that Masbiole could be a business model, where various strategies are considered according to the benefits and losses of the self agent and opponent agent. From the proposed system, it has been realized that symbiotic relations of Masbiole can be applicable directly to the negotiation depending on the objectives and the problem nature, which cannot be realized in the conventional MASs approaches. The results obtained by Masbiole are compared with the results obtained by GNP. It is found from the simulation results that Masbiole can obtain better results than GNP. In addition, Masbiole could be applied to various situations considering the objective of the self agent and opponent agent. As a result, it has been confirmed from this study that Masbiole is an effective tool for solving complex problems with respect to symbiosis, which could not be solved by the conventional MASs.
