Affiliations: [a] Department of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute of Technology, Gokiso-cho, Showa-ku, Nagoya 466-8555, Japan | [b] Center for Coordination Science, Sloan School of Management, Massachusetts Institute of Technology, Three Cambridge Center, NE20-336, Cambridge, MA 02142, USA | [c] Department of Social Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501, Japan | [x] Hong Kong Baptist University, Kowloon, Hong Kong, China | [y] University of Wollongong, Wollongong, NSW 2522, Australia | [z] Nagoya Institute of Technology, Gokiso, Showa, Nagoya 466-8555, Japan
Abstract: Multi-Issue Negotiation protocols have been studied very widely and represent a promising field since most of negotiation problems in the real-world are complex ones including multiple issues. In particular, in reality issues are constrained each other. This makes agents’ utilities nonlinear. There have been a lot of work on multi-issue negotiations. However, there have been very few work that focus on nonlinear utility spaces. In this paper, we assume agents have nonlinear utility spaces. For the linear utility domain, agents can aggregate the utilities of the issue-values by simple linear summation. In the real world, such aggregations are unrealistic. For example, we cannot just add up the value of car’s tires and the value of car’s engine when engineers design a car. In this paper, we propose an auction-based multiple-issue negotiation protocol among nonlinear utility agents. Our negotiation protocol employs several techniques, i.e., adjusting sampling, auction-based maximization of social welfare. Our experimental results show that our method can outperform the existing simple methods in particular in the huge utility space that can be often found in the real-world. Further, theoretically, our negotiation protocol can guarantee the completeness if some conditions are satisfied.
Keywords: Multi-issue negotiation, non-linear utility, multi-agent systems
