Can We Trust Autonomous Agents? A Formal Framework for Verifiable Agent Economies

Brief Summary

In one sentence: Transactions between AI agents are hard to verify, and paying the geometric mean of the verified value range minimizes the worst-case loss for both buyer and seller.

The problem: delegating money before trust is verifiable

AI agents are moving from doing work for people to spending money on their behalf: booking flights, negotiating services, and initiating payments. A principal who delegates such tasks struggles to confirm three things. Did the agent deliver at the agreed quality? Did it overpay? And what stops a penalized agent from adopting a new identity and starting over?

The paper illustrates the problem with a concrete case. A user asks a personal assistant agent to book a flight. The assistant selects a travel-service agent, negotiates a price, completes the payment, and the user receives a confirmation. The transaction looks successful, but the confirmation hides three possible failures:

• Misdelivery: The travel-service agent books a worse cabin or flight than it promised. The confirmation proves that a ticket exists, not that it is the ticket the user requested.
• Overpayment: The assistant pays a premium for an unverifiable promise, such as a claimed best-price guarantee with no evidence behind it.
• Strategic shirking: A historically reliable service agent finds that the extra profit from cutting corners on one order exceeds the long-run loss from a damaged reputation, and defects on that order.

None of these failures comes from weak agent reasoning. They arise because payment authority is handed over before identity, behavior, and delivery are reliably verifiable. The paper calls this class of problems trust-asymmetric coordination: the principal does not fully observe the agent's true capability, effort, or execution, so trust in the transaction is not something to assume.

Four requirements

The paper models the problem as a repeated Bayesian game and states four requirements that hold jointly:

1. Delivery incentive compatibility: The long-run payoff from honest delivery exceeds the one-shot gain from cutting corners. Detection probability, stake slashing, and the continuation value of reputation jointly support this condition. In the flight case, the extra profit from issuing a worse ticket must be smaller than the slashed stake plus the lost future reputation.
2. Verifiable settlement: Payment depends on whether delivery matches the agreed quality, not only on whether delivery occurred. Verification is costly: stronger verification narrows the residual uncertainty about value but costs more. A booking confirmation shows that a ticket was issued; checking the cabin class and price requires additional verification.
3. Budget and authority safety: Actions taken through constrained wallets and permission gates stay within the budget and scope the principal sets. The assistant spends money, but not beyond the user's limit and not on items outside the user's authorization.
4. Sybil resistance: Creating a new identity to reset reputation and escape penalties costs more than it gains. Without this condition, a poorly rated service agent simply re-registers and reputation loses its force.

The mechanism and geometric-mean settlement

The mechanism M* addresses the four requirements together. Credential-based admission binds identity, stake- and reputation-weighted matching selects service agents, constrained escrow controls the budget, and verification-conditioned settlement determines payment. The central element is the payment rule. When verification bounds the delivered value only to an interval [v_min, v_max], the mechanism pays the geometric mean:

P* = √(v_min · v_max)

After verification, the buyer knows only that the delivery is worth at least v_min and at most v_max. Paying v_min shortchanges the seller, paying v_max overcharges the buyer, and the arithmetic mean (v_min + v_max)/2 still leaves one side with a large worst-case deviation. The geometric mean equalizes the factor by which the buyer overpays and the factor by which the seller is underpaid, and this common factor is the smallest one any payment rule achieves.

The paper proves that, among all receipt-conditioned payment rules, geometric-mean pricing attains the minimal worst-case exposure bound √s, where s = v_max/v_min, and that this bound is tight. In the flight case, if verification only establishes that the ticket is worth between 100 and 400, the geometric-mean price is 200. The buyer overpays by at most a factor of 2 and the seller is underpaid by at most a factor of 2. Paying the arithmetic mean of 250 instead exposes the buyer to an overpayment of up to 2.5 times and the seller to an underpayment of up to 1.6 times, so the largest deviation grows.

The analysis also states when each guarantee holds. Honest delivery is sequentially optimal when detection probability, stake, and reputation continuation value satisfy an explicit inequality. Identity renewal is unprofitable when identity-creation cost and stake are high enough. Budget safety covers only actions routed through the constrained wallet and permission gates.

Results

The numerical analysis finds an interior optimum for the verification budget. Too little verification leaves high residual risk, while too much lets verification cost consume welfare. Near the optimum, the mechanism achieves 46% higher welfare than Verification-Only and raises honest delivery from 77% to 99%. The interior optimum persists across five detection laws, a measured sampling-audit verifier, learning agents, and thin markets, although its location shifts with the verification technology.

Scope

The paper is explicit about what lies outside its guarantees: misrepresentation at the quoting stage, the assistant agent's own incentives, collusion among agents, and the physical evidence chain of embodied agents. For example, a misinterpreted instruction or a prompt-injection attack is enough to steer a faithful assistant toward the wrong transaction. Budget safety caps how much the assistant spends, but it does not guarantee that the spending matches the principal's intent.

Highlights

1. Trust decomposed into four checkable constraints: Rather than treating trustworthiness in general terms, the framework requires honest delivery, verifiable settlement, budget safety, and resistance to identity resets, and it states concrete conditions for each. The three failures in the flight case (misdelivery, overpayment, and strategic shirking) map to three distinct design targets: delivery incentives, verifiable settlement, and reputation continuation value. Deployers therefore see which guarantees the mechanism provides by construction and which ones depend on parameter calibration.
2. Exposure optimality of geometric-mean pricing: When verification yields only a value interval, geometric-mean pricing simultaneously minimizes the buyer's worst-case overpayment and the seller's worst-case underpayment, with the tight bound √s. The result is concise, provable, and tied directly to verification cost: stronger verification narrows the interval and shrinks exposure. Without knowing where the true value lies inside the interval, the rule picks the point that equalizes both sides' worst-case deviations, and that point is the geometric mean.
3. An interior verification budget: Welfare first rises and then falls as the verification budget grows. Deployment therefore calls for calibrating verification to the verifier technology, market thickness, and false-positive rate rather than adding verification blindly. The measured sampling-audit verifier moves the optimum without removing it.
4. Explicit boundaries: The paper does not claim to solve every problem. Quote-stage fraud, assistant-side bias, agent collusion, and physical-world evidence chains are listed as future work, including prompt injection against the personal assistant and coordinated price inflation among travel-service agents. Readers know which conclusions hold under which conditions and which questions remain open.