A formal framework for reasoning about agents' independence in self-organizing multi-agent systems

Self-organization is a process where a stable pattern is formed by the cooperative behaviour between parts of an initially disordered system without external control or influence. It has been introduced to multi-agent systems as an internal control process or mechanism to solve difficult problems spontaneously. However, the complex link between local agent behaviour and system level behaviour in a self-organizing multi-agent system makes it difficult to predict the global behaviour of the system from the behaviour of the agents we design deductively, and thus implementation becomes the usual way of correctness evaluation for such a type of systems. Moreover, the complex link also makes it difficult to reconfigure the system when it is needed to change the results and predict the change to the global system behaviour under interventions. Therefore, it is important to have a logic-based framework that allows us to verify a self-organizing multi-agent system offline and reason about agents' independence in terms of the properties they bring about. This paper proposes a logic-based framework of self-organizing multi-agent systems, where agents communicate with each other and behave by following their prescribed local rules. The independence between coalitions of agents regarding the properties they will bring about is reasoned about from the dimensions of agents'collective actions and communication. We then illustrate the applicability of our framework using a real-world case, where a self-organization-based approach is used to form user communities. Finally, we show that the computational complexity of verifying whether a coalition of agents is fully independent with respect to a system property in a self-organizing multi-agent system is in exponential time.