The Complexity of Norm Synthesis and Revision.
Publication date
2022
Authors
Dell’Anna, Davide
Alechina, Natasha
Dalpiaz, Fabiano
Dastani, Mehdi
Löffler, M.
Logan, Brian
Editors
Ajmeri, Nirav
Martin, Andreasa Morris
Savarimuthu, Bastin Tony Roy
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
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 and several related problems are NP-complete.
Keywords
Taverne
Citation
Dell'Anna, D, Alechina, N, Dalpiaz, F, Dastani, M, Löffler, M & Logan, B 2022, The Complexity of Norm Synthesis and Revision. in N Ajmeri, A M Martin & B T R Savarimuthu (eds), Coordination, Organizations, Institutions, Norms, and Ethics for Governance of Multi-Agent Systems XV : International Workshop, COINE 2022, Virtual Event, May 9, 2022, Revised Selected Papers. Lecture Notes in Computer Science , vol. 13549, Springer, pp. 38-53. https://doi.org/10.1007/978-3-031-20845-4_3