A Heuristic Approach to Proposal-Based Negotiation with Applications in Fashion Supply Chain Management

We reconsider and improve the formal, executable framework for automated multi-issue negotiation between two autonomous competitive software agents proposed by Cadoli, who introduced a proposal-based process of negotiation, which he modeled as a distributed constraint satisfaction problem (DCSP). His model is based on the view of negotiation spaces, representing the admissible values of the goods involved in the process, as convex regions: i.e., all points included in each agent’s individual region (or “area”) correspond to acceptable agreements. However, in order to speed-up the negotiation process and guarantee convergence, there was the assumption/limitation that, for one of the two agents, only vertices of individual negotiation space were considered as admissible offers. Therefore, only those vertices included in the intersection of the two areas where actual potential agreements. In this article, we present and assess experimentally an extension to Cadoli’s approach where, in particular, interaction is no longer vertex-based, or at least not necessarily. I.e., we allow both agents to potentially make offers that are an internal point of its negotiation space and then try to approach the opponent’s counter-proposal “step-by-step”. The algorithm presented here overcomes some problems of the original one, such as the asymmetry among the parties and the limitation to polyhedral negotiation areas. Also, the extension can be usefully integrated to Cadoli’s framework, thus obtaining a new algorithm that may be effective in many practical cases by introducing “local search,”, for instance around “best-preferred” vertices. We present and discuss a number of experiments, aimed at assessing how parameters influence the performance of the algorithm, and they relate to each other. We report that the extended approach works properly, and in several cases yields a better solution than the original proposal, while the interaction complexity remains acceptable. We discuss its applicability in relevant application fields, such as for instance supply chain management in the fashion industry, which is a field of growing importance in economy and e-commerce.