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

Autonomous agent commerce where software agents hire, pay, and evaluate otheragents at micropayment scale creates a verication problem that existing approachescannot solve. When Agent A pays Agent B $0.01 for a translation, who determines whetherthe translation is actually good? Human review is economically impossible. A central LLMevaluator is non-deterministic, non-reproducible, and empirically unreliable on ambiguouscases. The problem is not engineering it is epistemological. Tarski (1936) proved thattruth in a formal system cannot be dened within that system. Gödel (1931) proved thatany consistent system contains true statements it cannot prove. Every content moderationsystem that has attempted automated truth verication conrms the theory: precision dropsbelow 60% on context-dependent content.This paper argues that the correct response to the Oracle Problem in agent commerce isnot better computation but better incentives. We propose a two-layer architecture: (1) de-terministic 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 verication agents with reputational stake, grounded in predictionmarket theory (Wolfers & Zitzewitz, 2004), peer prediction (Miller et al., 2005), and theeconomics of information asymmetry (Akerlof, 1970). The design separates what can beveried mechanically from what requires judgment, and delegates judgment to economiccompetition rather than algorithmic authority. We analyze the mechanism's incentive prop-erties, identify its limitations, and situate it within the broader Oracle Problem literaturefrom philosophy, computer science, and decentralized nance.