Responsibility Attribution in Parameterized Markovian Models

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragen

Beitragende

Abstract

We consider the problem of responsibility attribution in the setting of parametric Markov chains. Given a family of Markov chains over a set of parameters, and a property, responsibility attribution asks how the difference in the value of the property should be attributed to the parameters when they change from one point in the parameter space to another. We formalize responsibility as path-based attribution schemes studied in cooperative game theory. An attribution scheme in a game determines how a value (a surplus or a cost) is distributed among a set of participants. Path-based attribution schemes include the well-studied Aumann-Shapley and the Shapley-Shubik schemes. In our context, an attribution scheme measures the responsibility of each parameter on the value function of the parametric Markov chain. We study the decision problem for path-based attribution schemes. Our main technical result is an algorithm for deciding if a path-based attribution scheme for a rational (ratios of polynomials) cost function is over a rational threshold. In particular, it is decidable if the Aumann-Shapley value for a player is at least a given rational number. As a consequence, we show that responsibility attribution is decidable for parametric Markov chains and for a general class of properties that include expectation and variance of discounted sum and long-run average rewards, as well as specifications in temporal logic.

Details

OriginalspracheEnglisch
TitelProceedings of the AAAI Conference on Artificial Intelligence
Herausgeber (Verlag)AAAI Press
Seiten11734-11743
Seitenumfang10
Band35
Auflage13
ISBN (elektronisch)2374-3468
ISBN (Print)978-1-57735-866-4
PublikationsstatusVeröffentlicht - 18 Mai 2021
Peer-Review-StatusNein

Konferenz

TitelThirty-Fifth AAAI Conference on Artificial Intelligence
KurztitelAAAI-21
Dauer2 - 9 Februar 2021
BekanntheitsgradInternationale Veranstaltung
StadtVirtual

Externe IDs

Scopus 85108135862
ORCID /0000-0002-5321-9343/work/142236689

Schlagworte

DFG-Fachsystematik nach Fachkollegium

Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis

Schlagwörter

  • Planning with Markov Models (MDPs, POMDPs), Action, Change, Causality, Cooperative Game Theory