Normative Multi-Agent Programs and Their Logics

Mehdi Dastani, Davide Grossi, John-Jules Ch. Meyer, Nick A. M. Tinnemeier

TL;DR

This paper introduces a novel programming language for building multi-agent systems that are regulated by "norm-based artifacts." These artifacts enforce rules and impose sanctions, moving beyond simple coordination to create more structured and predictable agent interactions. The authors also present a logic to formally specify and verify properties of these normative systems, enabling robust development and analysis.

What Problem Does This Paper Address?

Developing complex multi-agent systems (MAS) often requires coordinating the behavior of numerous autonomous and potentially heterogeneous agents. While some approaches focus on low-level synchronization, this paper tackles the challenge of regulating agent behavior through higher-level social concepts like norms. The authors aim to provide a formal framework for implementing "norm-based artifacts" – organizational structures that monitor, enforce, and sanction agent actions to ensure adherence to desired behaviors. This addresses the gap in existing MAS methodologies that often lack formal operational semantics for norm enforcement and sanctioning mechanisms, leading to less predictable and harder-to-manage systems.

Methods

The core contribution is a simplified programming language designed to implement norm-based artifacts. This language allows developers to specify:

  • Agent Behaviors: How individual agents act.
  • Norms: Rules that define desired or forbidden actions, often expressed as "counts-as" rules (e.g., "being on the platform without a ticket counts as a violation").
  • Sanctions: Actions taken when norms are violated (e.g., fines).
  • Effects: How agent actions change the shared environment.

The language is endowed with a formal operational semantics that defines how these components interact. Crucially, it incorporates:

  • Monitoring: Observing agent actions and their effects.
  • Regimentation: Preventing forbidden actions (e.g., using "viol" literals that halt execution).
  • Sanctioning: Applying penalties based on violations.

To enable verification, the authors develop a logic that extends Propositional Dynamic Logic (PDL). This logic allows for specifying and proving properties about the normative MAS programs, such as safety (e.g., "a violation never occurs") and liveness (e.g., "a sanction is eventually applied after a violation").

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and a programming language, illustrated with a conceptual example of a train station.

Key Insights and Ideas

  • Norms as Programmable Artifacts: The paper frames norms not just as abstract rules but as concrete, implementable components within a MAS architecture. This shifts the focus from agent-internal reasoning to external organizational enforcement.
  • Regimentation vs. Enforcement: The authors distinguish between preventing violations outright (regimentation) and responding to them (enforcement with sanctions). Their system supports both, offering flexibility in how norms are applied.
  • Formalizing Social Concepts: By providing syntax, semantics, and a logic, the paper offers a rigorous way to model and reason about social concepts like norms, violations, and sanctions in computational systems.
  • Bridging the Gap to Logic: The development of a PDL-based logic for these normative MAS programs is a significant step towards formally verifying the correctness and behavior of such systems.

Key Results

The paper presents a programming language with formal operational semantics for normative multi-agent systems. It also introduces a sound and weakly complete logic for specifying and verifying properties of these systems. The authors demonstrate the language with a train station example, illustrating how norms can regulate agent behavior and how violations can trigger sanctions. They also show how to express properties like "sanction follows violation" and "regimentation" within their logical framework.

Limitations and Future Work

The authors acknowledge several limitations and outline promising future directions:

  • Simplified Language: The presented language is a simplified version. Future work aims to extend it with constructs for a broader range of social concepts (roles, power structures, information flow) and more complex norm types (e.g., norms with deadlines).
  • Closed Systems: The current framework primarily addresses "closed" multi-agent systems. Future research will focus on developing similar formal semantics for "open" multi-agent systems.
  • Norm Awareness: The current model assumes agents are not necessarily aware of the norms. Future work will explore incorporating norm-awareness into agent designs.
  • Ought-to-Be vs. Ought-to-Do: The focus has been on "ought-to-be" norms (preferable states). The framework will be extended to handle "ought-to-do" norms (preferable actions).
  • Proof Checker: The authors are working on a semi-automatic proof checker to aid in verifying normative MAS programs.
  • Interpreter: An interpreter for the normative MAS programming language is under development.

Summary updated

Abstract

Multi-agent systems are viewed as consisting of individual agents whose behaviors are regulated by an organization artefact. This paper presents a simplified version of a programming language that is designed to implement norm-based artefacts. Such artefacts are specified in terms of norms being enforced by monitoring, regimenting and sanctioning mechanisms. The syntax and operational semantics of the programming language are introduced and discussed. A logic is presented that can be used to specify and verify properties of programs developed in this language.
BibTeX
@inproceedings{dastani2009normative,
  author = {Mehdi Dastani and Davide Grossi and John-Jules Ch. Meyer and Nick A. M. Tinnemeier},
  title = {{Normative Multi-Agent Programs and Their Logics}},
  booktitle = {Normative Multi-Agent Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=CgBDmmVt8y},
}
Figure