A Graph-Theoretical Perspective on Law Design for Multiagent Systems
This work addresses the challenge of efficient law design for multiagent systems, which is incremental as it builds on graph theory and complexity analysis.
The paper tackles the problem of designing minimal laws for multiagent systems to eliminate undesirable outcomes or ensure accountability, proving that finding such minimum laws is NP-hard even in simple scenarios, and shows that vertex cover approximation algorithms can efficiently approximate these laws.
A law in a multiagent system is a set of constraints imposed on agents' behaviours to avoid undesirable outcomes. The paper considers two types of laws: useful laws that, if followed, completely eliminate the undesirable outcomes and gap-free laws that guarantee that at least one agent can be held responsible each time an undesirable outcome occurs. In both cases, we study the problem of finding a law that achieves the desired result by imposing the minimum restrictions. We prove that, for both types of laws, the minimisation problem is NP-hard even in the simple case of one-shot concurrent interactions. We also show that the approximation algorithm for the vertex cover problem in hypergraphs could be used to efficiently approximate the minimum laws in both cases.