Addressing Complexity in Multi-Issue Negotiation via Utility Hypergraphs

There has been a great deal of interest about negotiations having interdependent issues and nonlinear utility spaces as they arise in many realistic situations. In this case, reaching a consensus among agents becomes more difficult as the search space and the complexity of the problem grow. Nevertheless, none of the proposed approaches tries to quantitatively assess the complexity of the scenarios in hand, or to exploit the topology of the utility space necessary to concretely tackle the complexity and the scaling issues. We address these points by adopting a representation that allows a modular decomposition of the issues and constraints by mapping the utility space into an issue-constraint hypergraph. Exploring the utility space reduces then to a message passing mechanism along the hyperedges by means of utility propagation. Adopting such representation paradigm will allow us to rigorously show how complexity arises in nonlinear scenarios. To this end, we use the concept of information entropy in order to measure the complexity of the hypergraph. Being able to assess complexity allows us to improve the message passing algorithm by adopting a low-complexity propagation scheme. We evaluated our model using parametrized random hyper- graphs, showing that it can optimally handle complex utility spaces while outperforming previous sampling approaches.