Using Graph Properties and Clustering Techniques to Select Division Mechanisms for Scalable Negotiations

Abstract

This paper focuses on enabling the use of negotiation for complex system optimisation, which main challenge nowadays is scalability. Our hypothesis is that analysing the underlying network structure of these systems can help divide the problems in subproblems which facilitate distributed decision making through negotiation in these domains. In this paper, we verify this hypothesis with an extensive set of scenarios for a proof-of-concept problem. After selecting a set of network metrics for analysis, we cluster the scenarios according to these metrics and evaluate a set of mediation mechanisms in each cluster. The validation experiments show that the relative performance of the different mediation mechanisms change for each cluster, which confirms that network-based metrics may be useful for mechanism selection in complex networks.