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^* (Corresponding Author), Natasha Alechina, Fabiano Dalpiaz, Mehdi Dastani, Maarten Löffler, Brian Logan

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Published conference contribution

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, Revised Selected Papers
Editors	Nirav Ajmeri, Andreasa Morris Martin, Bastin Tony Savarimuthu
Place of Publication	Cham, Switzerland
Publisher	Springer Nature Switzerland AG
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 - 25 Nov 2022
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 - Virtual, Online Duration: 9 May 2022 → 9 May 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13549 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	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
City	Virtual, Online
Period	9/05/22 → 9/05/22

Access to Document

10.1007/978-3-031-20845-4_3Licence: Unspecified

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. Morris Martin, & B. T. Savarimuthu (Eds.), Coordination, Organizations, Institutions, Norms, and Ethics for Governance of Multi-Agent Systems XV : International Workshop, COINE 2022, Revised Selected Papers (pp. 38-53). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13549 LNAI). Springer Nature Switzerland AG. https://doi.org/10.1007/978-3-031-20845-4_3

The Complexity of Norm Synthesis and Revision. / Dell’Anna, Davide (Corresponding Author); Alechina, Natasha; Dalpiaz, Fabiano et al.
Coordination, Organizations, Institutions, Norms, and Ethics for Governance of Multi-Agent Systems XV : International Workshop, COINE 2022, Revised Selected Papers. ed. / Nirav Ajmeri; Andreasa Morris Martin; Bastin Tony Savarimuthu. Cham, Switzerland: Springer Nature Switzerland AG, 2022. p. 38-53 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13549 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Published conference contribution

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 Morris Martin & BT Savarimuthu (eds), Coordination, Organizations, Institutions, Norms, and Ethics for Governance of Multi-Agent Systems XV : International Workshop, COINE 2022, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13549 LNAI, Springer Nature Switzerland AG, Cham, Switzerland, pp. 38-53, 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, Virtual, Online, 9/05/22. https://doi.org/10.1007/978-3-031-20845-4_3

Dell’Anna D, Alechina N, Dalpiaz F, Dastani M, Löffler M, Logan B. The Complexity of Norm Synthesis and Revision. In Ajmeri N, Morris Martin A, Savarimuthu BT, editors, Coordination, Organizations, Institutions, Norms, and Ethics for Governance of Multi-Agent Systems XV : International Workshop, COINE 2022, Revised Selected Papers. Cham, Switzerland: Springer Nature Switzerland AG. 2022. p. 38-53. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2022 Nov 24. doi: 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, Revised Selected Papers. editor / Nirav Ajmeri ; Andreasa Morris Martin ; Bastin Tony Savarimuthu. Cham, Switzerland : Springer Nature Switzerland AG, 2022. pp. 38-53 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{709f3ef488d54ce881c7f52aa0e277a6,

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{\textquoteright}Anna and Natasha Alechina and Fabiano Dalpiaz and Mehdi Dastani and Maarten L{\"o}ffler and Brian Logan",

year = "2022",

month = nov,

day = "25",

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

language = "English",

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

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Nature Switzerland AG",

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

address = "Switzerland",

note = "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 ; Conference date: 09-05-2022 Through 09-05-2022",

}

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/11/25

Y1 - 2022/11/25

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 - http://www.scopus.com/inward/record.url?scp=85144342025&partnerID=8YFLogxK

UR - https://coin-workshop.github.io/coine-2022-auckland/papers/paper-8.pdf

UR - https://coin-workshop.github.io/coine-2022-auckland/technical_programme.html

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

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

M3 - Published conference contribution

AN - SCOPUS:85144342025

SN - 978-3-031-20844-7

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

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

PB - Springer Nature Switzerland AG

CY - Cham, Switzerland

T2 - 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

Y2 - 9 May 2022 through 9 May 2022

ER -