Counterfactual Reasoning for Causal Responsibility Attribution in Probabilistic Multi-Agent Systems

Technische Samenvatting: Contrfactueel Redeneren voor Toewijzing van Causale Verantwoordelijkheid in Probabilistische Multi-Agent Systemen

Probleemstelling
Het artikel behandelt de uitdaging van verantwoordelijkheidsallocatie in Multi-Agent Systemen (MAS), specifiek binnen probabilistische omgevingen waar meerdere agenten interageren en gezamenlijk uitkomsten beïnvloeden. Het kernprobleem is tweeledig:

1. Retrospectieve Toewijzing: Hoe kan op een eerlijke manier worden gekwantificeerd in welke mate individuele agenten verantwoordelijk zijn voor een specifieke uitkomst (bijvoorbeeld een botsing), gegeven een strategieprofiel en de capaciteiten van de agenten? Dit vereist onderscheid te maken tussen agenten die slechts deelnamen en diegenen wier handelingen causaal significant waren, met name wanneer agenten verschillende success- of faalkansen hebben (bijvoorbeeld: één agent kan met zekerheid stoppen terwijl een andere dat niet kan).
2. Strategisch Redeneren: Hoe moeten agenten hun strategieën kiezen wanneer ze "verantwoordelijkheidsbewust" zijn, wat betekent dat ze hun verwachte beloningen afwegen tegen de mogelijke straffen of mate van verantwoordelijkheid die ze kunnen oplopen voor ongewenste uitkomsten.

Methodologie
De auteurs modelleren het systeem als een Concurrent Stochastic Multi-Player Game (CSG). Agenten hanteren geheugenloze (gedrags)strategieën, die toestanden afbeelden op kansverdelingen over acties. De methodologie verloopt in drie hoofdfasen:

1. Formaliseren van Contrfactuele Verantwoordelijkheid (bCR):

   • Het artikel kiest een achterwaarts contrfactuele aanpak gebaseerd op de Necessary Element of a Sufficient Set (NESS)-test. Een agent $i$ draagt verantwoordelijkheid voor een uitkomst $\phi$ als er een coalitie $J$ (exclusief $i$) bestaat zodanig dat de strategieën van $J$ alleen $\phi$ niet garanderen, maar $J \cup \{i\}$ dit wel doet.
   • Om over te gaan van kwalitatieve naar kwantitatieve toewijzing, maken de auteurs gebruik van de Shapley-waarde. Zij definiëren een karakteristieke functie $v_{\vec{\sigma}, \phi}(A)$ die de minimale kans voorstelt dat $\phi$ optreedt wanneer coalitie $A$ een specifiek strategieprofiel $\vec{\sigma}_A$ volgt, terwijl agenten buiten $A$ optimaal handelen om de kans op $\phi$ te minimaliseren (onder de aanname dat $\phi$ ongewenst is).
   • De mate van verantwoordelijkheid $D_i(\vec{\sigma}, \phi)$ wordt berekend als de Shapley-waarde van de marginale bijdrage van agent $i$ aan de kans op $\phi$ over alle mogelijke coalities.

2. Logica voor Verificatie (PATL-SR):

   • De auteurs breiden PATL (Probabilistic Alternating-time Temporal Logic) uit met een nieuwe operator $\langle A \rangle D_{\bowtie d} [bCR_i(\vec{\sigma}, \psi)]$. Dit maakt redeneren mogelijk over de vraag of de mate van achterwaarts contrfactuele verantwoordelijkheid voor agent $i$ voldoet aan een specifieke grens $d$.
   • De logica integreert cumulatieve beloningen en temporele eigenschappen (begrensde bereikbaarheid/veiligheid).

3. Strategisch Besluitvorming (Nash-evenwicht):

   • Er wordt een verantwoordelijkheidsbewuste nutfunctie gedefinieerd: $u_i(\vec{\sigma}) = \text{Verwachte Beloning} - \lambda \cdot D_i(\vec{\sigma}, \phi)$, waarbij $\lambda$ een coëfficiënt is die beloning en verantwoordelijkheid in evenwicht brengt.
   • Het probleem van het vinden van stabiele strategieën wordt geformuleerd als het berekenen van een Nash-evenwicht (NE).
   • Om dit op te lossen, introduceren de auteurs een Parametric Stochastic Multi-Agent System (PSMAS), waarbij geheugenloze strategieën worden gecodeerd als variabelen. Zij tonen aan dat voor bereikbaarheids- en veiligheidsdoelstellingen de nutfunctie quasi-concaaf is (specifiek lineair in de strategieparameters), waardoor de berekening van het NE kan worden gereduceerd tot het oplossen van een stelsel vergelijkingen over de existentiële theorie van de reële getallen.

Belangrijkste Bijdragen

• Formeel Kader voor bCR: Het artikel introduceert een kwantitatieve definitie van achterwaarts contrfactuele verantwoordelijkheid in probabilistische CSG's met behulp van de Shapley-waarde. Dit kader waarborgt dat verantwoordelijkheid wordt toegewezen op basis van de marginale bijdrage aan de waarschijnlijkheid van een uitkomst.
• Theoretische Eigenschappen: De auteurs bewijzen formeel dat hun toewijzingsmethode voldoet aan belangrijke gewenste eigenschappen:
  • Efficiëntie: De som van de toegewezen verantwoordelijkheden is gelijk aan de totale toewijsbare waarde (het verschil tussen de werkelijke kans van de uitkomst en de minimaal haalbare kans).
  • Symmetrie: Agenten met identieke bijdragen ontvangen gelijke verantwoordelijkheid.
  • Null-speler: Agenten die geen invloed hebben op de uitkomst ontvangen nul verantwoordelijkheid.
  • Monotonie en Additiviteit: Verantwoordelijkheid gedraagt zich consistent wanneer uitkomsten worden uitgebreid of gecombineerd (onder specifieke disjuncte/vermijdbare voorwaarden).
• Logica en Complexiteit: De auteurs stellen PATL-SR voor, een logica die PATL uitbreidt met verantwoordelijkheidsopties. Zij bewijzen dat modelchecking voor PATL-SR binnen PSPACE blijft, wat overeenkomt met de complexiteit van standaard rPATL.
• Strategische Berekening: Het artikel biedt een methode om strategieprofielen voor Nash-evenwicht te berekenen waarbij agenten een nutfunctie optimaliseren die zowel beloningen als verantwoordelijkheid omvat. Zij tonen aan dat voor bereikbaarheids- en veiligheidsdoelstellingen deze berekening eveneens binnen PSPACE valt.

Resultaten

• Validatie via Casestudie: Het lopende voorbeeld van twee autonome voertuigen (A1 en A2) die een kruispunt naderen, demonstreert het kader. In een scenario waarin beide agenten kiezen om niet te remmen, berekent het model dat A1 een hogere mate van verantwoordelijkheid draagt (0,64) dan A2 (0,24). Dit sluit aan bij de intuïtie, omdat A1 een hogere kans heeft om te stoppen (0,8) vergeleken met A2 (0,4), waardoor A1's falen om te stoppen contrfactueel significant is.
• Complexiteitsgrenzen: Het artikel stelt vast dat het toevoegen van verantwoordelijkheidsredenering de computationele complexiteitsklasse van verificatie of evenwichtszoeking niet verhoogt boven PSPACE.
• Bestaan van Evenwicht: Door gebruik te maken van de quasi-concaafheid van de nutfunctie voor specifieke temporele doelstellingen, bevestigt het artikel dat stabiele strategieprofielen (Nash-evenwichten) kunnen worden berekend waarbij agenten reistijd (beloning) afwegen tegen het risico van een botsing (verantwoordelijkheid).

Betekenis en Claims
Het artikel claimt een fundamentele stap te zetten richting betrouwbare AI door "verantwoordelijkheidsbewuste agenten" mogelijk te maken. De betekenis hiervan ligt in:

• Interpreteerbaarheid: Het kader is gebaseerd op de Shapley-waarde, een concept dat breed wordt begrepen in verschillende disciplines, en biedt een interpreteerbare methode voor toewijzing in plaats van een "black box" moreel oordeel.
• Formele Strenge: Het overbrugt formele verificatie (logica, modelchecking) en speltheorie (Nash-evenwicht, nutmaximalisatie) om de dubbele vragen te adresseren van hoe verantwoordelijkheid moet worden toegewezen en hoe agenten moeten handelen gegeven die toewijzing.
• Praktische Toepasbaarheid: De auteurs merken op dat zij, hoewel zij niet claimen de totaliteit van morele verantwoordelijkheid te formaliseren (een complex filosofisch domein), hun aanpak een rigoureuze, kwantitatieve tool biedt voor het ontwerpen van systemen waarbij agenten rekening moeten houden met de gevolgen van hun handelingen in probabilistische, multi-agent omgevingen.

Het artikel concludeert door beperkingen te erkennen, zoals de huidige focus op geheugenloze strategieën, en suggereert toekomstig werk gericht op het uitbreiden van het kader naar agenten met eindig geheugen en het integreren van verantwoordelijkheid in normatieve systemen en multi-agent reinforcement learning.