The Complexity of Norm Synthesis and Revision.

Davide Dell'Anna; Natasha Alechina; Fabiano Dalpiaz; Mehdi Dastani; Maarten Löffler; Brian Logan

doi:10.1007/978-3-031-20845-4_3

The Complexity of Norm Synthesis and Revision.

Davide Dell'Anna, Natasha Alechina, Fabiano Dalpiaz, Mehdi Dastani, Maarten Löffler, Brian Logan

Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › Academic › peer-review

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.

Original language	English
Title of host publication	Coordination, Organizations, Institutions, Norms, and Ethics for Governance of Multi-Agent Systems XV
Editors	Nirav Ajmeri, Andreasa Morris Martin, Bastin Tony Savarimuthu
Pages	38-53
DOIs	https://doi.org/10.1007/978-3-031-20845-4_3
Publication status	Published - 2022
Externally published	Yes

Access to Document

10.1007/978-3-031-20845-4_3

Cite this

@inproceedings{03b58b7fd127425a81c43b844b046587,

title = "The Complexity of Norm Synthesis and Revision.",

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.",

author = "Davide Dell'Anna and Natasha Alechina and Fabiano Dalpiaz and Mehdi Dastani and Maarten L{\"o}ffler and Brian Logan",

year = "2022",

doi = "10.1007/978-3-031-20845-4_3",

language = "English",

isbn = "978-3-031-20845-4",

pages = "38--53",

editor = "Nirav Ajmeri and {Morris Martin}, Andreasa and Savarimuthu, {Bastin Tony}",

booktitle = "Coordination, Organizations, Institutions, Norms, and Ethics for Governance of Multi-Agent Systems XV",

}

The Complexity of Norm Synthesis and Revision. / Dell'Anna, Davide; Alechina, Natasha; Dalpiaz, Fabiano et al.
Coordination, Organizations, Institutions, Norms, and Ethics for Governance of Multi-Agent Systems XV. ed. / Nirav Ajmeri; Andreasa Morris Martin; Bastin Tony Savarimuthu. 2022. p. 38-53.

Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › Academic › peer-review

TY - GEN

T1 - The Complexity of Norm Synthesis and Revision.

AU - Dell'Anna, Davide

AU - Alechina, Natasha

AU - Dalpiaz, Fabiano

AU - Dastani, Mehdi

AU - Löffler, Maarten

AU - Logan, Brian

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-031-20845-4_3

DO - 10.1007/978-3-031-20845-4_3

M3 - Conference Article in proceeding

SN - 978-3-031-20845-4

SN - 978-3-031-20844-7

SP - 38

EP - 53

BT - Coordination, Organizations, Institutions, Norms, and Ethics for Governance of Multi-Agent Systems XV

A2 - Ajmeri, Nirav

A2 - Morris Martin, Andreasa

A2 - Savarimuthu, Bastin Tony

ER -

The Complexity of Norm Synthesis and Revision.

Abstract

Access to Document

Fingerprint

Cite this