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

Autonomous AI agents discover services, negotiate, and settle payments. However, open agent markets lack reliable means to verify delivery, constrain delegated authority, and make identity renewal economically consequential. To address these failures, we formalize the verifiable agent economy, where evidence and programmable constraints govern identity, behavior, and payment. We introduce the agentic economy stack and formulate trust-asymmetric coordination through four requirements: delivery incentive compatibility, verifiable settlement, budget and authority safety, and Sybil resistance. To operationalize these requirements, we construct a blockchain-based mechanism combining verifiable credentials, stake, reputation, constrained wallets, and receipt-conditioned settlement. Within the class of receipt-conditioned payment rules, its geometric-mean payment rule minimizes worst-case multiplicative exposure to residual value uncertainty. The mechanism satisfies delivery incentive compatibility and Sybil resistance under explicit deterrence and identity-cost conditions, while its budget and authority guarantee is limited to actions routed through the enforcement path. Across five detection laws, numerical analysis identifies an interior verification-budget optimum. At their respective optima, our mechanism achieves 46% higher welfare than Verification-Only and raises honest delivery from 77% to 99%. A measured sampling-audit verifier shifts but preserves the optimum, while false positives and thin markets tighten participation and staking requirements.