TL;DR
This paper introduces a novel method for analyzing the robustness of normative systems by incorporating the concept of "violation severity." By ranking possible system states based on how severely norms are violated, the authors enable more nuanced robustness analysis and the verification of system properties under different compliance assumptions, particularly for systems with "contrary to duty" obligations.
What Problem Does This Paper Address?
In multi-agent systems (MAS), normative systems define ideal agent behavior through norms. However, agents are autonomous and can fail to comply. While "contrary to duty" (CTD) obligations can specify how to mitigate violations, simply penalizing violations doesn't fully capture robustness. The severity of a norm violation can vary significantly, and this variation is crucial for understanding how robust a system truly is. For instance, revealing restricted information is less severe than revealing secret information. Existing approaches to robustness analysis often treat all violations equally or rely on penalty-based severity, which can lead to reasoning fallacies. This paper addresses the need for a method that can reason about system robustness considering varying levels of norm violation severity and CTD obligations.
Methods
The authors propose a method that combines model checking with a preference-based approach to define obligations. They leverage a partial order over norms to represent their relative severity. This severity partial order, along with the normative specifications, is used to compute a preference relation between possible worlds. This relation ranks worlds based on their compliance, prioritizing worlds that violate less severe obligations or fewer obligations of the same severity. This ranking partitions the state space into different "ideality levels." The authors then encode these levels into a model suitable for off-the-shelf model checkers like PRISM, allowing for the specification and verification of robustness properties using temporal logic. They introduce algorithms for computing the preference relation and the world ranking.
Datasets
Not discussed in the paper. The paper uses a simulated "ISR Scenario" as a running example.
Key Insights and Ideas
- Violation Severity as a Partial Order: The core idea is that norm violations aren't binary (violated/not violated) but exist on a spectrum of severity. Representing this as a partial order allows for incomparable severity levels, reflecting real-world complexity.
- Ideality Levels for Robustness: By ranking worlds based on compliance and severity, the system is partitioned into "ideality levels." This allows for robustness analysis under specific assumptions about how severely the system might fail.
- CTD Obligations and Severity: The framework explicitly handles "contrary to duty" obligations, which are crucial for repairing violations. The severity of violating these repair obligations can also be specified.
- Model Checking for Severity-Aware Queries: The method enables model checkers to answer questions like "Is it possible to achieve goal X without violating any norm of severity Y or higher?" This moves beyond simple reachability to more nuanced robustness checks.
Key Results
The paper presents a formalization and algorithms for computing world rankings based on normative specifications and violation severity. They demonstrate this with an ISR scenario, showing how different severity specifications lead to different rankings and how these rankings can be used to query a model checker. For instance, they show how to check properties within specific severity ranges, such as ensuring an unauthorized boat is neither intercepted nor reported, while staying within a certain severity threshold.
Limitations and Future Work
- Static Scenarios: The current model analyzes static scenarios with a fixed configuration. Future work aims to represent complex workflows where goals or environmental constraints can change at runtime.
- Severity of Norm Subsets: The current model defines severity for individual norms. Future work plans to generalize this to specify severity for subsets of norms, acknowledging that combined violations might have more severe consequences.
- Agent-Specific Compliance: The authors suggest exploring different compliance assumptions for individual agents within a system, similar to existing work in normative system verification.
- Probabilistic Violations: While the PRISM model checker can handle probabilities, the current work assumes uniform transition probabilities. Future work could incorporate probabilistic violation likelihoods to compute the probability of undesired situations.
Summary updated