Responsibility Anticipation and Attribution in LTLf

Giuseppe De Giacomo, Emiliano Lorini, Timothy Parker, Gianmarco ParrettiIJCAI 2025 · DOI

TL;DR

This paper introduces a formal framework for reasoning about agent responsibility in autonomous systems using Linear Temporal Logic over finite traces (LTLf). It connects strategic reasoning in game theory with notions of responsibility, providing algorithms and complexity analyses for anticipating and attributing both active and passive responsibility. This work offers a computational grounding for responsibility, crucial for designing more accountable AI.

What Problem Does This Paper Address?

The paper tackles the challenge of formally defining and computationally assessing responsibility in autonomous systems. Responsibility is a complex, multi-faceted concept in machine ethics and AI, with various interpretations (e.g., causal, moral, active, passive, anticipated, attributed). Existing formalizations are fragmented, lacking a unified computational approach. This paper aims to bridge this gap by providing a rigorous framework for reasoning about strategic responsibility, specifically focusing on how an agent's chosen strategy leads to certain outcomes, and whether it could have acted differently. This is essential for building AI systems that can be held accountable for their actions.

Methods

The authors leverage Linear Temporal Logic on finite traces (LTLf) as their formal language, a common choice for specifying properties of reactive systems. They connect LTLf specifications to concepts from game theory and reactive synthesis, particularly focusing on strategy synthesis (winning, dominant, and best-effort strategies).

Key methodological contributions include:

  • Formalization of Responsibility Notions: Defining and formalizing "active responsibility" (agent forces an outcome) and "passive responsibility" (agent lets an outcome occur) within the LTLf framework. They further distinguish between "anticipation" (ex ante, before actions) and "attribution" (ex post, after actions).
  • Connection to Strategy Synthesis: Establishing a direct link between responsibility notions and existing concepts in strategy synthesis, such as winning, dominant, and best-effort strategies. This allows leveraging established algorithms and complexity results from this field.
  • Algorithmic Development: Proposing algorithms for checking various forms of responsibility, including active responsibility, weak passive responsibility anticipation, and strong passive responsibility anticipation. These algorithms are based on automata-theoretic techniques and game solving.
  • Complexity Analysis: Deriving tight computational complexity bounds (PSPACE-complete, 2EXPTIME-complete) for checking these responsibility notions, providing insights into the feasibility of their practical implementation.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Responsibility as a Strategic Property: The core insight is that responsibility is not just about individual actions but is deeply intertwined with the agent's chosen strategy and its interaction with the environment. This allows for a more nuanced and computationally tractable analysis.
  • Bridging Logic and Game Theory: The paper successfully bridges formal logic (LTLf) with game-theoretic concepts (strategies, dominance, best-effort), providing a robust foundation for reasoning about responsibility.
  • Novel "Strong Passive Responsibility": The introduction of "strong passive responsibility" is a significant contribution. It goes beyond simply "letting happen" to consider whether the agent could have achieved a better outcome (in terms of avoiding the undesirable one) by choosing a different strategy. This is particularly relevant for agents that aim to optimize their performance and avoid blame.
  • Unavoidability of Weak Passive Responsibility: The paper suggests that weak passive responsibility is often unavoidable in LTLf settings because dominant strategies (which would prevent it) rarely exist. This highlights the practical challenges in ensuring agents are never passively responsible.
  • Best-Effort Strategies as a Unifying Concept: Best-effort strategies emerge as a unifying concept for both weak and strong passive responsibility anticipation, suggesting they are a crucial consideration for designing responsible agents.

Key Results

The paper provides theoretical results and algorithms for checking various responsibility notions:

  • Active Responsibility: Checking active responsibility for an LTLf formula $\phi$ under a strategy $\sigma_{ag}$ and environment specification $\mathcal{E}$ is PSPACE-complete with respect to $\phi$, 2EXPTIME-complete with respect to $\mathcal{E}$, and polynomial with respect to $\sigma_{ag}$.
  • Weak Passive Responsibility Anticipation: Checking weak passive responsibility anticipation for $\phi$ under $\sigma_{ag}$ and $\mathcal{E}$ is PSPACE-complete with respect to $\phi$, 2EXPTIME-complete with respect to $\mathcal{E}$, and polynomial with respect to $\sigma_{ag}$.
  • Strong Passive Responsibility Anticipation: Checking strong passive responsibility anticipation for $\phi$ under $\sigma_{ag}$ and $\mathcal{E}$ is 2EXPTIME-complete with respect to both $\phi$ and $\mathcal{E}$, and polynomial with respect to $\sigma_{ag}$.
  • Passive Responsibility Attribution (Weak and Strong): Checking weak passive responsibility attribution for $\phi$ under $\sigma_{ag}$, $\mathcal{E}$, and history $h$ is PSPACE-complete with respect to $\phi$, 2EXPTIME-complete with respect to $\mathcal{E}$, and polynomial with respect to both $\sigma_{ag}$ and $h$. Strong passive responsibility attribution has similar complexity, with 2EXPTIME-completeness for both $\phi$ and $\mathcal{E}$.

Limitations and Future Work

  • Single Agent Focus: The current work focuses on a single agent's perspective. The authors suggest extending the framework to multi-agent settings, where agents operate in an environment shaped by other agents and the environment itself.
  • Responsibility-Aware Strategy Synthesis: The authors note that the characterized responsibility notions can be used not only for assessment but also during strategy synthesis. This opens a research avenue into generating strategies that actively avoid unintended responsibility.
  • Third-Person Perspective: The current work examines responsibility from the agent's viewpoint (first-person perspective). Future work could explore a third-person perspective, where an external observer assesses an agent's responsibility.

Summary updated

BibTeX
@inproceedings{giacomo2025responsibility,
  author = {Giuseppe De Giacomo and Emiliano Lorini and Timothy Parker and Gianmarco Parretti},
  title = {{Responsibility Anticipation and Attribution in LTLf}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/6},
}
Figure