EFFECTIVE AUTOMATED NEGOTIATION BASED ON ISSUE DENDROGRAMS AND PARTIAL AGREEMENTS  

作　　者：ShinjiKakimoto Katsuhide Fujita 

机构地区：[1]Institute of Engineering, Tokyo University of Agriculture and Technology

出　　处：《Journal of Systems Science and Systems Engineering》2018年第2期201-214,共14页系统科学与系统工程学报（英文版）

摘　　要：Negotiation is both an important topic in multi-agent systems research and an important aspect of daily life. Many real-world negotiations are complex and involve multiple interdependent issues, therefore, there has been increasing interest in such negotiations. Existing nonlinear automated negotiation protocols have difficulty in finding solutions when the number of issues and agents is large. In automated negotiations covering multiple independent issues, it is useful to separate out the issues and reach separate agreements on each in turn. In this paper, we propose an effective approach to automated negotiations based on recursive partitioning using an issue dendrogram. A mediator first finds partial agreements in each sub-space based on bids from the agents, then combines them to produce the final agreement. When it cannot find a solution, our proposed method recursively decomposes the negotiation sub-problems using an issue dendrogram. In addition, it can improve the quality of agreements by considering previously-found partial consensuses. We also demonstrate experimentally that our protocol generates higher-optimality outcomes with greater scalability than previous methods.Negotiation is both an important topic in multi-agent systems research and an important aspect of daily life. Many real-world negotiations are complex and involve multiple interdependent issues, therefore, there has been increasing interest in such negotiations. Existing nonlinear automated negotiation protocols have difficulty in finding solutions when the number of issues and agents is large. In automated negotiations covering multiple independent issues, it is useful to separate out the issues and reach separate agreements on each in turn. In this paper, we propose an effective approach to automated negotiations based on recursive partitioning using an issue dendrogram. A mediator first finds partial agreements in each sub-space based on bids from the agents, then combines them to produce the final agreement. When it cannot find a solution, our proposed method recursively decomposes the negotiation sub-problems using an issue dendrogram. In addition, it can improve the quality of agreements by considering previously-found partial consensuses. We also demonstrate experimentally that our protocol generates higher-optimality outcomes with greater scalability than previous methods.

关 键 词：Multi-issue negotiation issue dendrogram partial agreement 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] F279.241[自动化与计算机技术—控制科学与工程]