Research map / Learning theory and algorithms / Prediction and decision losses
Backward Responsibility in Transition Systems Using General Power Indices
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces optimistic and pessimistic backward responsibility for states in transition systems with counterexamples, computed via general power indices (e.g. Shapley value), with complexity results, a tool, and a stochastic approximation.
Problem
Identifying which states of a transition system are responsible for a safety violation shown by a model-checking counterexample; existing forward responsibility ignores the specific counterexample.
Approach
Model states as players in a cooperative game where a coalition wins if it can avoid bad states on a counterexample-engraved safety game; responsibility is the general power index of each state, with optimistic (non-counterexample states cooperate) and pessimistic (they adversarially act) variants.
Key results
- Optimistic Shapley responsibility is characterised as 1/|WS_opt| for winning states, giving a polynomial-time algorithm for positivity, threshold and computation problems.
- Pessimistic positivity is NP-complete, threshold problem is NP-hard and in PSPACE, and pessimistic computation is #P-hard and in PSPACE.
- Stochastic sampling with 60s on benchmark models gives standard deviations as low as 0.0001-0.0038 for models with tens to hundreds of states (e.g. alternating_bit 0.0038).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use optimistic rather than pessimistic responsibility | Shapley responsibility for the railway network example · Railway network example | responsibility attribution across states: s1: 1/6 -> 1/2; s2: 2/3 -> 1/2; s3: 1/6 -> 0 | Mixed |
| Use pessimistic responsibility to assess the misrouting | Dresden Central Station · Misrouted train | Shapley responsibility: state 35: 3/4; states 36, 37, 42: 1/12 each | Mixed |
| Group t1 through t5 into one state group (ablation) | Responsibility analysis of the five-switch railway example · Five-switch railway example | Shapley responsibility: t_i: 0.0238 -> 1/6; s1: 0.3571 -> 1/6; s2: 0.5238 -> 2/3 | Mixed |
| Increase stochastic sampling time from 1s to 60s | Stochastic responsibility estimation · alternating_bit | standard deviation: 0.0304 -> 0.0038 | Helped |
| Increase stochastic sampling time from 1s to 60s | Stochastic responsibility estimation · brp, N = 4, MAX = 2 | standard deviation: 0.0015 -> 0.0002 | Helped |
| Increase stochastic sampling time from 1s to 60s | Stochastic responsibility estimation · crowds, TR = 3, CS = 5 | standard deviation: 0.0120 -> 0.0018 | Helped |
| Group states by the chunk being processed (ablation) | Stochastic responsibility estimation · BRP, N = 64, MAX = 5 | standard deviation: 0.0006 | Helped |
| Use optimistic responsibility to identify individually winnable states | Peg Solitaire analysis · Peg Solitaire | positive responsibility identification | Helped |
Surprising findings
- Pessimistic responsibility can assign positive responsibility to states not on the counterexample, e.g. s3 in the train example.
- Optimistic responsibility gives every responsible state the same value, so it does not rank states.
Limitations
- Pessimistic responsibility is computationally hard (NP-complete positivity, #P-hard computation), exact computation is exponential.
- Analysis restricted to safety games; extension to other game classes like Büchi is future work.
- Results are state-based and not mapped back to source-level specification language.
Experimental setup
Datasets: PRISM benchmark models (alternating_bit, brp, crowds, dining_philosophers, dresden_railways, generals) Peg Solitaire model Dresden Central Station model
Benchmarks: alternating_bit brp crowds dining_philosophers dresden_railways generals
Metrics: standard deviation of estimated responsibility number of samples runtime
Builds on: Shapley value general power indices (semivalues) forward responsibility (Chockler-Halpern style) PRISM
Closest papers by meaning
- Calibrating Conservatism for Scalable Oversight (ICML 2026 · similarity 0.83)
- Decomposing Interventional Causality into Synergistic, Redundant, and Unique Components (NeurIPS 2025 · similarity 0.82)
- Responsibility-aware Strategic Reasoning in Probabilistic Multi-Agent Systems (AAAI 2025 · similarity 0.82)
- Towards Computational Foreseeability (AAAI 2025 · similarity 0.82)
- Reasoning About Actual Causes in Nondeterministic Domains (AAAI 2025 · similarity 0.82)
- Prediction-Intervention Games and Invariant Sets (NeurIPS 2026 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.