The Oracle Problem in Autonomous Agent Commerce: Why Semantic Truth Verification Is Computationally Intractable and What to Build Instead

Autonomous agent commerce — where software agents hire, pay, and evaluate other agents at micropayment scale — creates a verification problem that existing approaches cannot solve. When Agent A pays Agent B $0.01 for a translation, who determines whether the translation is actually good? Human review is economically impossible.

A central LLM evaluator is non-deterministic, non-reproducible, and empirically unreliable on ambiguous cases. The problem is not engineering — it is epistemological. Tarski (1936) proved that truth in a formal system cannot be defined within that system.

Gödel (1931) proved that any consistent system contains true statements it cannot prove. Every content moderation system that has attempted automated truth verification confirms the theory: precision drops below 60% on context-dependent content. This paper argues that the correct response to the Oracle Problem in agent commerce is not better computation but better incentives. We propose a two-layer architecture: (1) deterministic validators that verify contract compliance — postconditions in the sense of Hoare (1969) and Meyer (1992) — handling the cases with zero ambiguity; and (2) Quality Markets, a competitive market of verification agents with reputational stake, grounded in prediction market theory (Wolfers & Zitzewitz, 2004), peer prediction (Miller et al., 2005), and the economics of information asymmetry (Akerlof, 1970).

The design separates what can be verified mechanically from what requires judgment, and delegates judgment to economic competition rather than algorithmic authority. We analyze the mechanism's incentive properties, identify its limitations, and situate it within the broader Oracle Problem literature from philosophy, computer science, and decentralized finance.