Efficient Methods for Multi-agent Multi-issue Negotiation: Allocating Resources

In this paper, we present an automated multi-agent multi-issue negotiation solution to solve a resource allocation problem. We use a multilateral negotiation model, by which three agents bid sequentially in consecutive rounds till some deadline. Two issues are bundled and negotiated concurrently, so win-win opportunities can be generated as trade-offs exist between issues. We develop negotiation strategies of the agents under an incomplete information setting. The strategies are composed of a Pareto-optimal-search method and concession strategies. An important technical contribution of this paper lies in the development of the Pareto-optimal-search method for three-agent multilateral negotiation. Moreover, we present the identification of agreements and Pareto-optimal outcomes achieved by our methods in mathematical proof. We show through computer experiments that using the tractable heuristic of Pareto-optimal-search combined with well-designed concession strategies by agents results in (near) Pareto-optimal outcomes