Competitive Belief Propagation to Efficiently Solve Complex Multi-agent Negotiations with Network Structure

摘要

This paper focuses on enabling the use of negotiation for complex system optimisation, whose main challenge nowadays is scalability. Although multi-agent automated negotiation has been studied for decades, it is still a challenge to handle in a scalable and efficient manner negotiation problems involving many issues with complex inter-dependencies. This is a clear obstacle for the use of automated negotiation in complex networks. This paper proposes a novel perspective on the negotiation process as a competitive belief propagation process, where the whole negotiation is modelled as a factor graph and distributed belief propagation techniques (BP) are used to yield a solution. We show that the model adequately suits both simple and complex negotiation settings in the literature, and we validate its efficiency and scalability in a challenging, network structured, channel negotiation setting.