Indirect Trust is Simple to Establish

Elham Parhizkar, Mohammad Hossein Nikravan, Sandra Zilles

Abstract

In decentralized Multi-Agent Systems (MAS), agents must often rely on "indirect trust"—recommendations from third-party advisers—to assess the reliability of unknown trustees. While existing state-of-the-art (SOTA) models employ complex Bayesian or evolutionary techniques to filter malicious advice, they often suffer from significant computational and memory overhead. This paper introduces ITEA (Indirect Trust with Expert Advice), a lightweight model based on online learning principles. Our results show that ITEA achieves performance comparable to or better than complex models while being orders of magnitude faster and more scalable.

Introduction

Trust is a fundamental mechanism for cooperation in MAS. When direct experience is unavailable, agents turn to advisers. However, these advisers may engage in deceptive behaviors such as badmouthing (unfairly disparaging good trustees) or ballot-stuffing (unfairly praising bad trustees). Existing solutions like TRAVOS (probabilistic) and MET (evolutionary) attempt to mitigate these attacks but are hindered by complexity: TRAVOS requires extensive memory to store interaction histories, while MET's evolutionary approach is computationally expensive. We propose that such complexity is unnecessary and that indirect trust can be effectively managed using simple online learning strategies.

Methodology: The ITEA Approach

ITEA treats the problem of indirect trust as a task of Predicting from Expert Advice (PEA). Each adviser is viewed as an "expert" whose advice is weighted based on past accuracy.

The Algorithm

ITEA utilizes an Exponential-Weighted Average strategy. It maintains a weight for each adviser, which is updated after every interaction. If an adviser's recommendation aligns with the actual outcome of an interaction, their weight is maintained; if they are incorrect, their weight is reduced exponentially.

Advantages

  • Efficiency: ITEA does not require storing the full history of interactions, resulting in a negligible memory footprint.
  • Scalability: The runtime complexity is $O(MK)$, where $M$ is the number of trustees and $K$ is the number of advisers. This is asymptotically optimal.

Experimental Evaluation

We evaluated ITEA against SOTA models (ACT, TRAVOS, MET) using a simulation framework with 1 truster, 10 trustees, and 100 advisers. We tested six distinct "Adviser Settings" (S1-S6) representing various attack patterns, including whitewashing and camouflage.

Performance Metrics

While many studies focus on Mean Absolute Error (MAE), we argue that the Relative Frequency of Unsuccessful Interactions (RFU) is a more practical measure of success in a marketplace. RFU measures how often a truster chooses a "bad" trustee based on the model's advice.

Table 1: RFU values across different scenarios and honesty levels. Bold values indicate the best performance.

Results and Discussion

As shown in the performance data in Table 1, ITEA consistently matches or outperforms more complex models across the majority of attack scenarios and honesty levels (90%, 70%, and 40% honest advisers).

Computational Efficiency

The most significant advantage of ITEA is its speed. In our tests, ITEA was approximately 50 times faster than TRAVOS and 238 times faster than MET, making it the only viable option for large-scale real-time systems.

Table 2: Runtime comparison (in seconds) for 50 interactions.

Key Insights

  1. Complexity vs. Performance: The "heavy machinery" of evolutionary algorithms does not necessarily provide a performance edge. Simple weighted averages are robust across diverse trustee behavior distributions.
  2. Robustness: By averaging results over 100 random distributions, we demonstrate that ITEA is less prone to the "blind spots" that affect more specialized, complex models.

Conclusion

This research demonstrates that indirect trust in MAS can be established using simple, efficient online learning techniques. ITEA provides a scalable, low-overhead alternative to current SOTA models without sacrificing accuracy. Future work will explore ITEA's performance in dynamic environments where trustee behavior evolves over time.

Reference: Parhizkar, E., Nikravan, M. H., & Zilles, S. (2019). Indirect Trust is Simple to Establish. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19).

Summary updated

Abstract

In systems with multiple potentially deceptive agents, any single agent may have to assess the trustworthiness of other agents in order to decide with which agents to interact. In this context, indirect trust refers to trust established through third-party advice. Since the advisers themselves may be deceptive or unreliable, agents need a mechanism to assess and properly incorporate advice. We evaluate existing state-of-the-art methods for computing indirect trust in numerous simulations, demonstrating that the best ones tend to be of prohibitively large complexity. We propose a new and easy to implement method for computing indirect trust, based on a simple prediction with expert advice strategy as is often used in online learning. This method either competes with or outperforms all tested systems in the vast majority of the settings we simulated, while scaling substantially better. Our results demonstrate that existing systems for computing indirect trust are overly complex; the problem can be solved much more efficiently than the literature suggests.
BibTeX
@inproceedings{parhizkar2019indirect,
  author = {Elham Parhizkar and Mohammad Hossein Nikravan and Sandra Zilles},
  title = {{Indirect Trust is Simple to Establish}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/446},
}
Figure