Automatic Synthesis of Dynamic Norms for Multi-Agent Systems

Natasha Alechina, Giuseppe De Giacomo, Brian Logan, Giuseppe Perelli

Research output: Contribution to conferenceUnpublished paperpeer-review


We consider the problem of synthesising and revising the set of norms in a normative MAS to satisfy a design objective expressed in Alternating Time Temporal Logic (ATL∗). ATL∗is a well-established language for strategic reasoning, which allows the specification of norms that constrain the strategic behaviour of agents. We focus on dynamic norms, that is, norms corresponding to Mealy machines, that allow us to place different constraints on the agents’ behaviour depending on the state of the norm and the state of the underlying MAS. We show that synthesising dynamic norms is (k + 1)-EXPTIME where k is the alternation depth of quantifiers in the ATL∗ specification. We also study the problem of removing existing norms to satisfy a new objective, which we
show to be 2EXPTIME-complete.
Original languageEnglish
Publication statusPublished - 30 Nov 2022
EventAIxIA 2022: 21st International Conference of the Italian Association for Artificial Intelligence - University of Udine, Udine, Italy
Duration: 28 Nov 20222 Dec 2022
Conference number: 21st


ConferenceAIxIA 2022
Internet address


  • Synthesis
  • Multi-Agent Systems
  • Normative Systems
  • Temporal Logics
  • Reasoning About Actions
  • Strategic Reasoning


Dive into the research topics of 'Automatic Synthesis of Dynamic Norms for Multi-Agent Systems'. Together they form a unique fingerprint.

Cite this