The Complexity of Norm Synthesis and Revision

Conference paper (2022)

Authors

Natasha Alechina Universiteit Utrecht
Fabiano Dalpiaz Universiteit Utrecht
Mehdi Dastani Universiteit Utrecht
M. Löffler Universiteit Utrecht
Brian Logan University of Aberdeen, Universiteit Utrecht
Copyright: © 2022 D. Dell'Anna, Natasha Alechina, Fabiano Dalpiaz, Mehdi Dastani, Maarten Löffler, Brian Logan
DOI: https://doi.org/10.1007/978-3-031-20845-4_3
More Info
expand_more

Published Date

2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

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.

Files

978_3_031_20845_4_3.pdf
(pdf | 0.394 Mb)
- Embargo expired in 01-07-2023
Unknown license