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.

^*Corresponding author for this work

Sub Geometric Computing

Delft University of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › 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
Subtitle of host publication	International Workshop, COINE 2022, Virtual Event, May 9, 2022, Revised Selected Papers
Editors	Nirav Ajmeri, Andreasa Morris Martin, Bastin Tony Roy Savarimuthu
Publisher	Springer
Pages	38-53
Number of pages	16
ISBN (Electronic)	978-3-031-20845-4
ISBN (Print)	978-3-031-20844-7
DOIs	https://doi.org/10.1007/978-3-031-20845-4_3
Publication status	Published - 2022

Publication series

Name	Lecture Notes in Computer Science
Volume	13549
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Bibliographical note

Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Access to Document

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

978-3-031-20845-4_3Final published version, 294 KBLicence: Taverne

Cite this

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 (pp. 38-53). (Lecture Notes in Computer Science ; Vol. 13549). Springer. https://doi.org/10.1007/978-3-031-20845-4_3

Dell'Anna, Davide ; Alechina, Natasha ; Dalpiaz, Fabiano et al. / The Complexity of Norm Synthesis and Revision. 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. editor / Nirav Ajmeri ; Andreasa Morris Martin ; Bastin Tony Roy Savarimuthu. Springer, 2022. pp. 38-53 (Lecture Notes in Computer Science ).

@inproceedings{42efaecc4b3f4410a94a81c31055aeea,

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

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.",

year = "2022",

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

language = "English",

isbn = "978-3-031-20844-7",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "38--53",

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

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

}

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, AM Martin & BTR 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

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: International Workshop, COINE 2022, Virtual Event, May 9, 2022, Revised Selected Papers. ed. / Nirav Ajmeri; Andreasa Morris Martin; Bastin Tony Roy Savarimuthu. Springer, 2022. p. 38-53 (Lecture Notes in Computer Science ; Vol. 13549).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › 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.

UR - https://www.scopus.com/pages/publications/85144342025

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

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

M3 - Conference contribution

SN - 978-3-031-20844-7

T3 - Lecture Notes in Computer Science

SP - 38

EP - 53

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

A2 - Ajmeri, Nirav

A2 - Martin, Andreasa Morris

A2 - Savarimuthu, Bastin Tony Roy

PB - Springer

ER -

Dell'Anna D , Alechina N , Dalpiaz F , Dastani M , Löffler M , Logan B. The Complexity of Norm Synthesis and Revision. In Ajmeri N, Martin AM, Savarimuthu BTR, editors, 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. Springer. 2022. p. 38-53. (Lecture Notes in Computer Science ). doi: 10.1007/978-3-031-20845-4_3

The Complexity of Norm Synthesis and Revision.

Abstract

Publication series

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this