Agent Quality Graph (AQG): A Protocol for Evaluating AI Agent Trustworthiness via Delegation Graphs

1.1. Motivation

The design of AQG is inspired by the success of link-based ranking in web search (PageRank). In the web graph, a link from page A to page B is treated as a "vote" for page B's relevance. Similarly, in AQG, a delegation from agent A to agent B is treated as evidence of agent B's capability.¶

Key differences from web link analysis:¶

• Delegation edges carry outcome metadata (success, failure, quality score)¶

• Edges have recency weights (recent delegations matter more)¶

• The graph is partitioned by task category¶

• Anti-gaming mechanisms prevent Sybil attacks and score manipulation¶

1.2. Terminology

Agent

An autonomous software entity capable of receiving and completing tasks¶

Delegation

A transaction where one agent (delegator) assigns a task to another agent (delegatee)¶

Delegation Record

A signed, immutable record of a delegation transaction including outcome¶

Trust Score

A value between 0.0 and 1.0 representing an agent's accumulated reliability¶

AQG Node

A vertex in the quality graph representing an agent¶

AQG Edge

A directed, weighted edge representing accumulated delegation evidence between two agents¶

Trust Provider

An entity that computes and publishes trust scores from delegation data¶

2.1. Required Fields

• record_id: Unique identifier (UUID v4)¶

• delegator: Agent identifier of the task delegator¶

• delegatee: Agent identifier of the task executor¶

• timestamp: ISO 8601 datetime of delegation¶

• outcome: Result of the delegation (status required, others optional)¶

2.2. Outcome Status Values

success

Task completed satisfactorily¶

failure

Task could not be completed¶

partial

Task partially completed¶

timeout

Task did not complete within expected time¶

2.3. Signature

Delegation records SHOULD be signed by the delegator using Ed25519 or ECDSA-P256. The signature covers the canonical JSON of all fields except the signature object itself. This prevents tampering and enables verification of record authenticity.¶

3.1. Node Creation

Each unique agent identifier becomes a node in the quality graph. Nodes are created on first appearance in any delegation record.¶

3.2. Edge Aggregation

For each (delegator, delegatee) pair, a single directed edge is maintained. The edge weight is computed from all delegation records between the pair:¶

Edge weight = sum(outcome_weight * recency_weight) for each record¶

Where:¶

• outcome_weight: success=1.0, partial=0.5, timeout=-0.2, failure=-0.5¶

• recency_weight: exponential decay with half-life of 90 days¶

3.3. Category Partitioning

The graph is partitioned by task_category. An agent may have different trust scores in different categories. The global trust score is the weighted average across all categories.¶

4.1. Base Score Computation

The base trust score for each agent is computed using a modified PageRank algorithm applied to the AQG graph:¶

Score(agent_i) = (1 - d) / N + d * sum(Score(agent_j) * w(j->i) / out_degree(j)) for all agents j that delegate to agent_i¶

Where:¶

• d = damping factor (0.85)¶

• N = total number of agents¶

• w(j->i) = normalized edge weight from j to i¶

4.2. Score Normalization

Raw scores are normalized to the range [0.0, 1.0] using min-max normalization across all agents. A minimum of 10 delegation records are required before a score is published (cold-start threshold).¶

4.3. Anti-Gaming Mechanisms

• Sybil Resistance: Newly created agents have no score until they receive delegations from established agents (bootstrap problem).¶

• Collusion Detection: If a cluster of agents only delegate among themselves with uniformly positive outcomes, their mutual edge weights are discounted.¶

• Temporal Decay: Scores naturally decay without ongoing positive delegations, preventing legacy agents from maintaining high scores indefinitely.¶

• Verification Requirement: Outcomes signed by both delegator and delegatee carry higher weight than single-signed outcomes.¶

5.1. Submit Delegation Record

POST /aqg/v1/records¶

Accepts a signed delegation record. Validates signature, indexes the record, and triggers asynchronous score recomputation.¶

5.2. Query Trust Score

GET /aqg/v1/scores/{agent_id}¶

Returns the current trust score for an agent:¶

{
  "agent_id": "agent:hotel-booker@example.com",
  "global_score": 0.87,
  "categories": {
    "booking": { "score": 0.92, "records": 156 },
    "scheduling": { "score": 0.78, "records": 23 }
  },
  "computed_at": "2026-05-03T12:00:00Z",
  "provider": "aqg.example.com",
  "signature": { "algorithm": "Ed25519", "value": "..." }
}

5.3. Query Delegation Graph

GET /aqg/v1/graph/{agent_id}?depth=2¶

Returns the subgraph of delegation relationships for the specified agent, up to the requested depth.¶

6.1. A2A Integration

AQG trust scores can be included in A2A Agent Cards as an extension:¶

{
  "name": "Hotel Booker",
  "...": "...(standard A2A Agent Card fields)...",
  "extensions": {
    "aqg": {
      "trust_score": 0.87,
      "score_provider": "https://aqg.example.com",
      "score_url": "https://aqg.example.com/aqg/v1/scores/agent:hotel-booker@example.com"
    }
  }
}

6.2. MCP Integration

MCP servers can expose their AQG trust score via the agent.json well-known URI:¶

{
  "name": "hotel-booker",
  "description": "Books hotel rooms",
  "trust": {
    "verified": true,
    "score": 0.87,
    "source": "aqg.example.com"
  }
}

10.1. Normative References

[RFC8615]

Nottingham, M., "Well-Known Uniform Resource Identifiers (URIs)", May 2019.

[A2A]

LLC, G., "Agent-to-Agent Protocol", 2025.

[MCP]

Anthropic, "Model Context Protocol", November 2024.

10.2. Informative References

[PAGERANK]

Page, L., Brin, S., Motwani, R., and T. Winograd, "The PageRank Citation Ranking: Bringing Order to the Web", 1999.

[ARDP]

Pioli, R., "Agent Registration and Discovery Protocol (ARDP)", February 2026.