The Complexity of Data-Driven Norm Synthesis and Revision
This addresses the difficulty of designing norms for coordinating agents when objectives and norm languages are mismatched, but it is incremental as it focuses on computational complexity rather than practical solutions.
The paper tackles the problem of synthesizing norms from labeled behavior traces in multi-agent systems, showing that this norm synthesis problem is NP-complete.
Norms have been widely proposed as a way of coordinating and controlling the activities of agents in a multi-agent system (MAS). A norm specifies the behaviour an agent should follow in order to achieve the objective of the MAS. However, designing norms to achieve a particular system objective can be difficult, particularly when there is no direct link between the language in which the system objective is stated and the language in which the norms can be expressed. In this paper, we consider the problem of synthesising a norm from traces of agent behaviour, where each trace is labelled with whether the behaviour satisfies the system objective. We show that the norm synthesis problem is NP-complete.