Formalizing Group and Propagated Trust in Multi-Agent Systems

Nagat Drawel, Jamal Bentahar, Amine Laarej, Gaith RjoubIJCAI 2020 · DOI

TL;DR

This paper introduces a new formal logic, Branching Trust Logic (BT), designed to reason about group and propagated trust in multi-agent systems (MAS). By extending existing temporal logics, BT allows agents to express and reason about collective trust and how trust can spread through a system, offering a more nuanced understanding of trust dynamics beyond individual relationships.

What Problem Does This Paper Address?

In multi-agent systems (MAS), trust is a fundamental concept for enabling cooperation and effective interaction. While existing research has explored formalizing individual trust (how one agent trusts another), there's a significant gap in formally capturing more complex trust dynamics. Specifically, the authors identify the need to reason about:

  • Group Trust: How an entire group of agents collectively trusts another agent. This can manifest as "everyone trusts" (all members agree) or "distributed trust" (trust is spread across group members).
  • Propagated Trust: How trust can spread from one agent to another through a chain of relationships.

Current formalisms, like TCTL, are limited in their expressive power and cannot adequately handle nested trust formulas required for these more complex scenarios. This limitation hinders the development of MAS that can robustly manage and reason about collective trust.

Methods

The core contribution of this paper is the Branching Trust Logic (BT), a new temporal logic designed to address the limitations of existing approaches. BT extends the Computation Tree Logic (CTL) by introducing new modal operators:

  • Er(G, j, φ): "Everyone in group G trusts agent j to bring about φ."
  • Dr(G, j, φ): "Distributed trust: trust is distributed among members of group G concerning agent j and goal φ."
  • Pr(i, j, φ): "Agent i trusts agent j to bring about φ," specifically designed to handle propagation.

To enable automated reasoning (model checking and satisfiability), the authors propose a transformation procedure. This procedure converts BT models and formulas into equivalent CTL models and formulas. This allows leveraging existing, well-established CTL model checkers and satisfiability solvers. The transformation involves:

  1. Model Transformation: Augmenting the CTL model with new states and transitions to represent the trust accessibility relations (~i,j, ~E,j, ~G,j, ~j). Fresh propositional variables are used to mark these new states and transitions, distinguishing them from the original system dynamics.
  2. Formula Transformation: Recursively translating BT formulas into equivalent CTL formulas. This involves mapping the new trust operators to CTL path quantifiers and temporal operators, ensuring that the semantics are preserved. The transformation carefully uses the AX operator and the newly introduced propositional variables to correctly capture the semantics of trust, group trust, and propagated trust.

Datasets

Not discussed in the paper. The authors mention using a "well-known ordering protocol that regulates the interaction between seller and buyer agents" for testing their implementation, but this is a conceptual scenario rather than a formal dataset.

Key Insights and Ideas

  • Beyond Individual Trust: The paper highlights that formalizing trust in MAS requires moving beyond simple pairwise relationships to encompass group dynamics and propagation.
  • Expressive Power of BT: The introduction of Er, Dr, and Pr operators provides a formal language to express nuanced collective trust, which was previously lacking.
  • Leveraging Existing Tools: The transformation approach is a clever way to make complex trust reasoning accessible by building upon the mature field of CTL model checking. This avoids reinventing the wheel for verification algorithms.
  • Addressing TCTL's Paradox: The authors identify a specific paradox in TCTL (T(i, j, φ) ⇒ T(i, j, ¬T(i, j, φ))) that prevents nested trust formulas, making their BT logic a necessary refinement for handling propagation.
  • Bounded Transformations: The paper proves that both model and formula transformations are bounded in size, ensuring that the complexity of the original problem doesn't explode during the conversion to CTL.

Key Results

  • Formalization: A new logic, Branching Trust Logic (BT), is formally defined with syntax and semantics for individual, group, and propagated trust.
  • Reasoning Postulates: Key reasoning postulates for trust propagation and group trust are presented and shown to hold in BT.
  • Transformation Procedure: A sound and efficient transformation procedure from BT to CTL is presented, enabling model checking and satisfiability analysis.
  • Complexity Analysis:
    • Explicit BT model checking is P-complete.
  • BT model checking for concurrent programs is PSPACE-complete.
  • BT satisfiability is EXPTIME-complete.
  • Implementation: The authors implemented their transformation procedure and integrated it with the NuSMV model checker.
  • Experimental Validation: Tests on an ordering protocol with up to 66 agents demonstrated the scalability of their approach, confirming theoretical complexity results and showing polynomial increase in execution time and memory usage with the number of states.

Limitations and Future Work

  • Limitations:
    • The paper focuses on explicit models for complexity analysis. While the transformation is polynomial, the underlying CTL model checking can be computationally expensive for large explicit models.
  • The current work is based on a deterministic transformation.
  • Future Work:
    • Tackle run-time verification to investigate the dynamic changes of agents' behavior and their impact on group trust.
  • Explore more efficient symbolic model checking techniques for BT.
  • Investigate the application of BT in more complex MAS scenarios and real-world applications.

Summary updated

BibTeX
@inproceedings{drawel2020formalizing,
  author = {Nagat Drawel and Jamal Bentahar and Amine Laarej and Gaith Rjoub},
  title = {{Formalizing Group and Propagated Trust in Multi-Agent Systems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/9},
}
Figure