This preprint formalizes the Cross-Agent Governance Alignment (CAGA) problem: the challenge of verifying mutual governance compatibility between autonomous AI agents operating under distinct organizational policy regimes, without disclosing proprietary governance structures. As AI agents increasingly coordinate across institutional boundaries in regulated industries (healthcare, finance, cross-border data exchange, supply chains), existing governance models prove insufficient. Current frameworks assume either a single organizational authority or full policy transparency between participants. Neither assumption holds in multi-stakeholder settings where governance constraints encode confidential risk tolerances, regulatory interpretations, and competitive strategy. This paper: Defines governance domains and cross-domain interactions in formal terms, adopting the triadic verdict space (ALLOW, DENY, ABSTAIN) of the execution-time authorization framework Introduces the governance alignment predicate Φ(Dᵢ, Dⱼ, τ) Formalizes the CAGA problem under an honest-but-curious threat model Identifies required solution properties spanning correctness, privacy, determinism, evidentiary sufficiency, and composable security, including the requirement that alignment protocols produce tamper-evident authorization artifacts sufficient for independent third-party replay, consistent with the Replay requirement of the Five Tests Standard (5TS) Demonstrates that CAGA is irreducible to existing paradigms, including agent communication protocols, federated learning, secure multi-party computation, single-organization governance architectures, and blockchain-based transparency systems We argue that CAGA constitutes a zero-knowledge coordination problem at the intersection of AI governance, cryptographic protocol design, and multi-agent systems. The paper deliberately stops at problem formalization and does not disclose protocol constructions or implementation mechanisms. By precisely defining the problem space and evaluation criteria, this work establishes the foundation for rigorous solution development and provides a formal framework against which candidate governance-alignment protocols can be assessed. Version 1.1 (July 2026) retitles the paper to make explicit that CAGA is formalized as a zero-knowledge coordination problem for cross-organizational AI governance; aligns terminology with the Five Tests Standard (5TS) v1.2.0 and the FERZ authorization-artifact vocabulary; adopts the triadic verdict space in the governance domain formalization; and adds a companion reference to Execution-Time Authorization for AI Agents (v2.1), which develops the formal architecture of the single-domain authorization boundary. The problem formalization, threat model, and irreducibility argument are unchanged from the February 2026 release (v1.0). Keywords: AI governance, multi-agent systems, zero-knowledge proofs, cross-organizational coordination, governance alignment, deterministic governance, authorization boundaries, authorization artifacts, Five Tests Standard
Edward Meyman (Sun,) studied this question.