  In this paper, we consider a form of multi-issue negotiation where a shop
negotiates both the contents and the price of bundles of goods with his
customers. We present some key insights about, as well as a procedure for,
locating mutually beneficial alternatives to the bundle currently under
negotiation. The essence of our approach lies in combining aggregate
(anonymous) knowledge of customer preferences with current data about the
ongoing negotiation process. The developed procedure either works with already
obtained aggregate knowledge or, in the absence of such knowledge, learns the
relevant information online. We conduct computer experiments with simulated
customers that have_nonlinear_ preferences. We show how, for various types of
customers, with distinct negotiation heuristics, our procedure (with and
without the necessary aggregate knowledge) increases the speed with which deals
are reached, as well as the number and the Pareto efficiency of the deals
reached compared to a benchmark.
