Reasoning about Cognitive Trust in Stochastic Multiagent Systems

Xiaowei Huang, Marta Kwiatkowska, Maciej Olejnik

TL;DR

This paper introduces a novel framework for automatically reasoning about cognitive trust in multi-agent systems. They achieve this by extending probabilistic temporal logic with operators for beliefs, goals, intentions, and trust, allowing for quantitative analysis of an agent's reliance on another. While the general problem is undecidable, they identify decidable fragments, paving the way for verifiable autonomous systems that can build and manage trust.

What Problem Does This Paper Address?

As autonomous systems, like self-driving cars and assistive robots, become more integrated into our lives, they need to collaborate with humans and other agents. This collaboration hinges on trust, a complex human concept that involves subjective evaluations of an agent's capabilities and intentions. The challenge is to formally model and automatically verify this "cognitive trust" in dynamic, uncertain, and multi-agent environments. Existing approaches often lack quantitative rigor or the ability to reason about the mental states that underpin trust. This paper aims to bridge that gap by providing a formal logic and verification framework for cognitive trust.

Methods

The core of the paper is the introduction of PRTL (Probabilistic Rational Temporal Logic), an extension of PCTL (Probabilistic Computation Tree Logic). PRTL incorporates operators for mental attitudes (beliefs, goals, intentions) and novel trust operators (competence, disposition, dependence). These operators are grounded in a formal model of autonomous stochastic multi-agent systems (ASMAS), which are based on concurrent stochastic multiplayer games. The framework models agents' cognitive states and their evolution through interleaving temporal and cognitive transitions. They also introduce preference functions to capture subjective beliefs and pro-attitude synthesis to derive agent strategies from beliefs and trust. The verification problem is then framed as model checking PRTL formulas against these ASMAS.

Datasets

Not discussed in the paper. The paper focuses on a formal framework and theoretical analysis, using a trust game as an illustrative example rather than real-world datasets.

Key Insights and Ideas

  • Quantifying Cognitive Trust: The paper moves beyond qualitative notions of trust to a quantitative, probabilistic approach, reflecting how humans express certainty ("I'm 99% sure..."). This allows for a more nuanced understanding of trust.
  • Beliefs as the Foundation: Trust is formally defined as being rooted in an agent's beliefs about another agent's capabilities and intentions, which are themselves derived from observations and preference functions.
  • Bridging Logic and AI: By extending temporal logic with cognitive operators, the paper provides a powerful tool for reasoning about the mental states that drive agent behavior and trust formation, bridging formal verification and AI reasoning.
  • Decidability Through Fragmentation: Recognizing the inherent undecidability of general trust reasoning, the authors identify specific, restricted fragments of their logic and system that are decidable, offering practical avenues for verification.

Key Results

The paper introduces the PRTL logic and the ASMAS framework. They demonstrate that while the general model checking problem for PRTL is undecidable, specific fragments (e.g., bounded fragments, fragments with certain restrictions on belief/trust operators) are decidable, with complexities ranging from PSPACE-complete to PTIME. They provide algorithms for pro-attitude synthesis and model checking, though the general synthesis step remains undecidable.

Limitations and Future Work

The authors acknowledge that the general problem of pro-attitude synthesis and model checking for PRTL* is undecidable. They suggest future work could explore:

  • Implementing a Model Checker: Building a practical tool based on their framework.
  • Memory Decay: Incorporating mechanisms for agents to prioritize recent experiences in their trust assessments, potentially improving decidability.
  • Axiomatisation and Satisfiability: Developing an axiomatisation for their logic and investigating the satisfiability problem.
  • Alternative Trust Notions: Exploring other formalizations of dependence and trust.
  • Nested Beliefs/Trust: Extending the logic to handle more complex nested belief and trust structures.

Summary updated

Abstract

We consider the setting of stochastic multiagent systems modelled as stochastic multiplayer games and formulate an automated verification framework for quantifying and reasoning about agents' trust. To capture human trust, we work with a cognitive notion of trust defined as a subjective evaluation that agent A makes about agent B's ability to complete a task, which in turn may lead to a decision by A to rely on B. We propose a probabilistic rational temporal logic PRTL*, which extends the probabilistic computation tree logic PCTL* with reasoning about mental attitudes (beliefs, goals and intentions), and includes novel operators that can express concepts of social trust such as competence, disposition and dependence. The logic can express, for example, that `agent A will eventually trust agent B with probability at least p that B will behave in a way that ensures the successful completion of a given task'. We study the complexity of the automated verification problem and, while the general problem is undecidable, we identify restrictions on the logic and the system that result in decidable, or even tractable, subproblems.
BibTeX
@article{huang2019reasoning,
  author = {Xiaowei Huang and Marta Kwiatkowska and Maciej Olejnik},
  title = {{Reasoning about Cognitive Trust in Stochastic Multiagent Systems}},
  journal = {ACM Trans. Comput. Log.},
  year = {2019},
  url = {https://openreview.net/forum?id=Sd3_oFMz5oa},
}
Figure