On the hardness of negotiations in multi-agent systems

In multi-agent negotiation the difficulty of the problem depends on how many issues are under negotiation and how complex agents´ utility functions are. In this paper we propose a framework for evaluating different techniques for solving negotiation problems and used it to show how hard a negotiation problem can become. We used mediated single text negotiation protocol with genetic algorithms mediator and hill climber agents. Negotiations were conducted over deals with binary issues presented as binary strings. Utility functions with binary and higher levels of dependency between issues were used. Our results show that size of problem does not affect performance, until higher levels of dependency between issues are presented in utility functions. Genetic algorithm method was able to solve the problem with relatively good performance in all levels of dependency that we tested.