A new generic negotiation mechanism to coordinate decentralized planning of a group of independent and self-interested decision makers or agents, who are searching for an agreeable contract regarding multiple interdependent issues, in the case of asymmetric information is presented. The basic idea of the mechanism is that the group members carry out a joint search based on a mediated pheromone matrix. By means of the Borda maximin voting rule, the agents determine contract proposals in each round of the negotiation process which are then used for the adaptation of pheromones or the generation of new contracts, respectively. The new negotiation mechanism is applied to the problem of decentralized lot-sizing in a supply chain. The resulting solution approach for the multi-level uncapacitated lot-sizing problem (MLULSP) is evaluated on the basis of 40 benchmark problems taken from the relevant literature. The derived results come close to those results which are obtained by centralized planning. Moreover, the new mechanism is competitive with other negotiation approaches which have been presented in the literature so far.