Multi-issue negotiation protocol for agents: exploring nonlinear utility spaces

Abstract

Multi-issue negotiation protocols have been studied widely and represent a promising field since most negotiation problems in the real world involve in-terdependent multiple issues. The vast majority of this work has assumed that negotiation issues are independent, so agents can aggregate the util-ities of the issue values by simple summation, pro-ducing linear utility functions. In the real world, however, such aggregations are often unrealistic. We cannot, for example, just add up the value of car’s carburetor and the value of car’s engine when engineers negotiate over the design a car. These value of these choices are interdependent, result-ing in nonlinear utility functions. In this paper, we address this important gap in current negotia-tion techniques. We propose a negotiation protocol where agents employ adjusted sampling to gener-ate proposals, and a bidding-based mechanism is used to find social-welfare maximizing deals. Our experimental results show that our method substan-tially outperforms existing methods in large non-linear utility spaces like those found in real world contexts. 1