Agentive Permissions in Multiagent Systems

Qi ShiIJCAI 2024

Introduction

In the study of multiagent systems, the intersection of agency and normativity presents a significant challenge for formal logic. Traditional deontic logic—the logic of obligation and permission—has historically focused on states of affairs (e.g., "it is permitted that $p$ occurs"). However, this approach often fails to capture the nuances of individual and collective action, particularly in environments where an agent's success depends on the actions of others.

This paper introduces a formal logical framework designed to distinguish between four distinct types of "agentive permissions." By decoupling the ability to ensure an outcome from the ability to merely admit its possibility, the research provides a more granular method for modeling how agents navigate complex, interactive, and nondeterministic environments.

The Problem of Agency in Deontic Logic

Standard deontic frameworks often treat agency in a vacuum. In the real world, an agent's action might not guarantee a specific result. Consider a factory dumping waste into a river: the factory might "ensure" the survival of the local fish population if it dumps a negligible amount, regardless of what other factories do. Conversely, it might merely "admit" the possibility of survival if that outcome depends on an upstream competitor also limiting its waste.

Existing systems lack the formal vocabulary to distinguish between these nuances of agency ("ensuring" vs. "admitting") and the strength of the permission itself ("strong" permission to take any such action vs. "weak" permission that at least one such action exists). This paper fills that gap by developing a logic based on multiagent transition systems.

The Formal Framework: Four Modalities of Permission

The core of the proposed method involves the definition of four new modal operators, which categorize permissions based on the relationship between an agent's choice and the resulting state of the world:

  1. Weak Admit (WA): There exists at least one permitted action that allows for the possibility of $\phi$.
  2. Weak Ensure (WE): There exists at least one permitted action that guarantees $\phi$ will occur.
  3. Strong Ensure (SE): Any action that guarantees $\phi$ is permitted.
  4. Strong Admit (SA): Any action that allows for the possibility of $\phi$ is permitted.

Theoretical Contributions

To validate this framework, the author employs several rigorous mathematical techniques:

  • Undefinability Proofs: Using truth set algebra, the paper proves that these four modalities are mutually undefinable. This confirms that each operator captures a unique normative "flavor" that cannot be expressed by a combination of the others.
  • Axiomatization: The author proposes a set of axioms and inference rules, proving them to be sound and complete. This ensures the logic perfectly aligns with the intended mathematical models.
  • Conflict Prevention: A specific inference rule (IR4) is introduced to prevent "normative conflicts," ensuring that multiple agents are not permitted to ensure outcomes that are mutually exclusive.

Computational and Structural Results

Beyond the theoretical definitions, the paper addresses the practical application of this logic through model checking and inter-logic mapping.

Model Checking Complexity

The research develops an algorithm to verify if these formulas hold within a given transition system. The global model-checking problem is shown to be computationally efficient, with a linear time complexity of $O(|\phi| \cdot (|S| + |M| + |\Delta|))$, where $|\phi|$ is the formula size, $|S|$ is the number of states, $|M|$ is the number of agents, and $|\Delta|$ is the number of transitions. This efficiency suggests the logic is suitable for real-time verification in complex systems.

Inter-logic Mapping

The paper provides a bridge between this new agentive permission logic and established frameworks such as STIT (Seeing To It That) logic and ATL (Alternating-time Temporal Logic). By showing how these modalities can be translated into existing systems, the author facilitates the adoption of these concepts by the broader formal methods community.

Conclusion and Future Directions

This research highlights the "agency gap" that exists in deterministic or single-agent models, where "ensuring" and "admitting" often collapse into the same concept. In multiagent worlds, however, these concepts diverge sharply.

While the current framework provides a robust foundation for one-step actions, the author identifies several avenues for future work. These include extending the logic to cover multi-step deontic constraints (e.g., permissions spanning a duration of time) and integrating concepts of causality and moral responsibility to better understand how being "permitted" to act relates to being "responsible" for the eventual outcome.

Summary updated

BibTeX
@inproceedings{shi2024agentive,
  author = {Qi Shi},
  title = {{Agentive Permissions in Multiagent Systems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure