Backward Responsibility in Transition Systems Using General Power Indices

Research output: Contribution to journalConference articleContributedpeer-review

Abstract

To improve reliability and the understanding of AI systems, there is increasing interest in the use of formal methods, e.g. model checking. Model checking tools produce a counterexample when a model does not satisfy a property. Understanding these counterexamples is critical for efficient debugging, as it allows the developer to focus on the parts of the program that caused the issue. To this end, we present a new technique that ascribes a responsibility value to each state in a transition system that does not satisfy a given safety property. The value is higher if the non-deterministic choices in a state have more power to change the outcome, given the behaviour observed in the counterexample. For this, we employ a concept from cooperative game theory – namely general power indices, such as the Shapley value – to compute the responsibility of the states. We present an optimistic and pessimistic version of responsibility that differ in how they treat the states that do not lie on the counterexample. We give a characterisation of optimistic responsibility that leads to an efficient algorithm for it and show computational hardness of the pessimistic version. We also present a tool to compute responsibility and show how a stochastic algorithm can be used to approximate responsibility in larger models. These methods can be deployed in the design phase, at runtime and at inspection time to gain insights on causal relations within the behavior of AI systems.

Details

Original languageEnglish
Pages (from-to)20320-20327
Number of pages8
JournalProceedings of the AAAI Conference on Artificial Intelligence
Volume38
Issue number18
Publication statusPublished - 25 Mar 2024
Peer-reviewedYes

Conference

Title38th AAAI Conference on Artificial Intelligence
Abbreviated titleAAAI-24
Conference number38
Duration20 - 27 February 2024
Website
Degree of recognitionInternational event
LocationVancouver Convention Centre
CityVancouver
CountryCanada

External IDs

ORCID /0000-0002-5321-9343/work/160951234
ORCID /0000-0001-7047-3813/work/161890923
ORCID /0000-0003-1724-2586/work/165453615
ORCID /0000-0003-4829-0476/work/165453943

Keywords

ASJC Scopus subject areas

Keywords

  • causality, Cooperative Game Theory