Backward Responsibility in Transition Systems Using General Power Indices

Christel Baier, Roxane van den Bossche, Sascha Klüppelholz, Johannes Lehmann, Jakob PiribauerAAAI 2024 · DOI

TL;DR

This paper introduces a novel game-theoretic approach to pinpoint which states in an AI system are "responsible" for a safety violation, going beyond simply identifying that a violation occurred. They propose two types of responsibility—optimistic and pessimistic—and develop algorithms to compute them, offering valuable insights for debugging complex AI systems.

What Problem Does This Paper Address?

Modern AI systems, especially those operating in complex environments, are often modeled as transition systems. When such a system violates a safety property (e.g., never reaching an undesirable state), model checkers can provide a "counterexample"—an execution trace that demonstrates the violation. However, simply having this trace doesn't tell developers why the violation happened or which parts of the system are most to blame. Understanding this "backward responsibility" is crucial for effective debugging and improving AI reliability. Existing methods often rely on distance metrics or mutation-based techniques, but this paper proposes a more principled, game-theoretic approach.

Methods

The core of the paper's contribution lies in framing the problem of backward responsibility as a cooperative game. They define two types of games based on a given counterexample:

  • Optimistic Responsibility: Assumes that states not on the counterexample actively help satisfy the safety property.
  • Pessimistic Responsibility: Assumes that states not on the counterexample actively try to violate the safety property.

These games are then analyzed using "general power indices," a concept from cooperative game theory that assigns a value to each player (state) based on their contribution to a coalition's success. The most well-known example of a power index is the Shapley value. The authors develop algorithms for computing both optimistic and pessimistic responsibility, with a focus on efficiency for the optimistic case and analyzing the complexity for the pessimistic case. They also propose a stochastic algorithm for approximating responsibility in larger, more complex models.

Datasets

Not discussed in the paper. The paper focuses on formal methods and theoretical analysis, using abstract transition systems and game arenas as its "datasets."

Key Insights and Ideas

  • Framing Responsibility as a Game: The most significant insight is the elegant application of cooperative game theory to attribute responsibility. By treating states as players in a game where "winning" means satisfying the safety property, they can leverage established concepts like Shapley values.
  • Optimistic vs. Pessimistic Responsibility: The distinction between optimistic and pessimistic views provides a nuanced understanding. Optimistic responsibility is simpler to compute and focuses on states that can guarantee safety on their own, while pessimistic responsibility is more complex but captures situations where states might be responsible even if they aren't directly on the counterexample path, by assuming others might not cooperate.
  • Computational Trade-offs: The paper highlights a clear trade-off: optimistic responsibility is computationally tractable (polynomial time), while pessimistic responsibility is significantly harder (NP-complete for positivity, NP-hard/PSPACE for threshold). This guides practitioners on which approach to use based on their computational resources and desired level of detail.
  • Stochastic Approximation for Scale: The development of a stochastic algorithm is crucial for making these techniques practical for real-world, large-scale AI systems where exact computation is infeasible.

Key Results

  • Efficient Algorithm for Optimistic Responsibility: They provide a characterization that allows optimistic responsibility to be computed efficiently, essentially by checking if a state can win "on its own."
  • Complexity Analysis for Pessimistic Responsibility: They establish that computing pessimistic responsibility is computationally hard, providing bounds (NP-complete, NP-hard, PSPACE) for different decision problems related to it.
  • Implementation and Evaluation: The authors developed a tool that implements these techniques. Experiments show that their stochastic algorithm can provide good approximations for large models, and state grouping can further improve performance and simplify results. For instance, in the "Misrouted Train" example, they found that state 35 had a responsibility of 3/4, while other states had 1/12, demonstrating how the method can pinpoint critical components.

Limitations and Future Work

  • Safety Games Focus: The current work is primarily focused on safety games (properties of the form "never reach bad state"). The authors suggest extending their framework to other types of games, such as Büchi games (liveness properties), to see if their results hold.
  • User Presentation: While the tool computes responsibility values, mapping these back to human-readable source code or specifications remains a challenge. Future work could explore better ways to present this information to users for more intuitive debugging.
  • Pessimistic Complexity: The precise complexity of the pessimistic threshold problem remains open, lying between NP and PSPACE.
  • Moral Responsibility: The paper explicitly states that their notion of responsibility does not include moral considerations, which is a distinct area of research.

Summary updated

BibTeX
@inproceedings{baier2024backward,
  author = {Christel Baier and Roxane van den Bossche and Sascha Klüppelholz and Johannes Lehmann and Jakob Piribauer},
  title = {{Backward Responsibility in Transition Systems Using General Power Indices}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.30013},
}
Figure