Title
The Complexity of Norm Synthesis and Revision
Author
Dell'Anna, D. (TU Delft Control & Simulation) 
Alechina, Natasha (Universiteit Utrecht)
Dalpiaz, Fabiano (Universiteit Utrecht)
Dastani, Mehdi (Universiteit Utrecht)
Löffler, Maarten (Universiteit Utrecht)
Logan, Brian (Universiteit Utrecht; University of Aberdeen)
Contributor
Ajmeri, Nirav (editor)
Morris Martin, Andreasa (editor)
Savarimuthu, Bastin Tony (editor)
Date
2022
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.
To reference this document use:
http://resolver.tudelft.nl/uuid:4f847cc0-6010-46c9-9320-7a9b71c0a271
DOI
https://doi.org/10.1007/978-3-031-20845-4_3
Publisher
Springer
Embargo date
2023-07-01
ISBN
9783031208447
Source
Coordination, Organizations, Institutions, Norms, and Ethics for Governance of Multi-Agent Systems XV - International Workshop, COINE 2022, Revised Selected Papers
Event
International Workshop on Coordination, Organizations, Institutions, and Norms for Governance of Multi-Agent Systems, COINE 2022 co-located with 21st International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS 2022, 2022-05-09, Virtual, Online
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 0302-9743, 13549 LNAI
Bibliographical note
Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.
Part of collection
Institutional Repository
Document type
conference paper
Rights
© 2022 D. Dell'Anna, Natasha Alechina, Fabiano Dalpiaz, Mehdi Dastani, Maarten Löffler, Brian Logan