Robust Normative Systems

Thomas Ågotnes, Wiebe van der Hoek, Michael J. Wooldridge

TL;DR

This paper tackles the critical issue of non-compliance in multi-agent systems by formalizing and analyzing "robustness" in normative systems. They introduce novel ways to quantify and characterize how well a system's objectives hold even when some agents deviate from the rules, moving beyond simple compliance checks.

What Problem Does This Paper Address?

Multi-agent systems often rely on "normative systems" or "social laws" to coordinate agent behavior and achieve desirable outcomes. However, a major challenge is that agents might not always comply with these rules. This non-compliance can be accidental, rational (e.g., it's not in an agent's best interest), or even irrational. Existing approaches to handle this include making compliance "incentive compatible" (making it the rational choice) or using penalty mechanisms. This paper argues that these methods have limitations, especially in large, open systems. Therefore, it focuses on understanding and measuring the robustness of a normative system – its ability to remain effective despite some agents not following the rules.

Methods

The authors introduce three main ways to formalize and analyze robustness:

  1. Coalition-based Necessity and Sufficiency: They define when a specific set of agents (a coalition) is sufficient (their compliance guarantees the system's objective) or necessary (their compliance is required for the objective to hold). This involves analyzing Kripke structures (a standard model for multi-agent systems) and using temporal logic (CTL) to express system objectives.
  2. Quantitative Robustness (k-Robustness): This approach quantifies robustness by looking at the number of agents. They define k-sufficiency (at least k agents complying is enough) and k-necessity (at least k agents must comply). This leads to the concept of k-robustness, meaning the system is effective if and only if a specific number of agents comply. They also introduce "resilience," the maximum number of non-compliant agents a system can tolerate.
  3. Logical Characterization of Robustness: This is a more general approach using "coalition predicates." These are logical formulas that describe properties of coalitions. A coalition predicate can then be used to characterize the set of coalitions whose compliance is sufficient for the normative system's effectiveness. This allows for more complex conditions than just specifying a fixed set of agents or a number.

Datasets

Not discussed in the paper. The paper uses formal models (Kripke structures) and logical formulas to represent systems and objectives, rather than empirical datasets.

Key Insights and Ideas

  • Robustness is Crucial: The paper strongly emphasizes that simply designing a system where compliance is incentive compatible or relying on penalties isn't enough. Real-world systems need to be robust to inevitable non-compliance.
  • Beyond Simple Compliance: The work moves beyond asking "does everyone comply?" to asking "what happens if some don't comply?" and "how many must comply for the system to work?"
  • Formalizing "Lynchpin" Agents: The concept of necessary and sufficient coalitions helps identify critical agents whose compliance is essential or guarantees success.
  • Quantifying Tolerance: k-robustness provides a concrete way to measure how resilient a system is to a certain number of deviating agents.
  • Expressive Power of Coalition Predicates: The logical characterization using coalition predicates offers a highly flexible way to define complex robustness requirements, going beyond simple agent sets or counts.

Key Results

The paper presents several complexity results for checking these robustness properties:

  • C-sufficiency (checking if a specific coalition is sufficient) is co-NP-complete.
  • C-necessity (checking if a specific coalition is necessary) is co-NP-complete.
  • k-sufficiency (checking if any k agents complying is sufficient) is co-NP-complete.
  • k-necessity (checking if at least k agents must comply) is co-NP-complete.
  • k-robustness (being both k-sufficient and k-necessary) is also co-NP-complete.
  • C-sufficient feasibility (whether a normative system exists that is effective and robust for a given reliable coalition C) is Σ-complete.
  • P-characterization (checking if a coalition predicate characterizes robustness) is co-NP-complete.

Notably, for universal objectives (formulas in the L^u fragment of CTL), checking sufficiency is polynomial time decidable.

Limitations and Future Work

  • Complexity: Many of the decision problems related to robustness are computationally hard (co-NP-complete or Σ-complete). This suggests that checking these properties in large systems might be challenging.
  • Agency vs. System Deviation: The paper notes that some existing work on robustness (like French et al.) focuses on system deviations rather than agent deviations. The authors suggest incorporating "deontic-like" operators into the object language to handle this more directly.
  • Minimality vs. Robustness Trade-off: The paper briefly touches upon the trade-off between system simplicity (minimality) and robustness, suggesting that a minimal norm might require the grand coalition to be necessary. Future work could explore this trade-off more deeply.
  • Practical Implementation: While the formalisms are presented, the paper doesn't delve into the practical implementation of these robustness checks in real-world multi-agent systems.

Summary updated

Abstract

Although normative systems, or social laws, have proved to be a highly influential approach to coordination in multi-agent systems, the issue of emph{compliance} to such normative systems remains problematic. In all real systems, it is possible that some members of an agent population will not comply with the rules of a normative system, even if it is in their interests to do so. It is therefore important to consider the extent to which a normative system is emph{robust}, i.e., the extent to which it remains effective even if some agents do not comply with it. We formalise and investigate three different notions of robustness and related decision problems. We begin by considering sets of agents whose compliance is necessary and/or sufficient to guarantee the effectiveness of a normative system; we then consider quantitative approaches to robustness, where we try to identify the proportion of an agent population that must comply in order to ensure success, and finally, we consider a more general approach, where we characterise the compliance conditions required for success as a logical formula.
BibTeX
@inproceedings{agotnes2009robust,
  author = {Thomas Ågotnes and Wiebe van der Hoek and Michael J. Wooldridge},
  title = {{Robust Normative Systems}},
  booktitle = {Normative Multi-Agent Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=N8pClHDv06},
}

Loading related content...

Figure