Abstract
As autonomous AI agents increasingly collaborate across organizational boundaries, semantic interoperability becomes a prerequisite for trustworthy automation. Existing interoperability solutions assume either shared vocabularies or predefined schema mappings, leaving first-time interactions between previously unknown agents unresolved. We define this challenge as the Stranger Problem: the absence of a protocol that enables autonomous systems to establish verifiable semantic agreement before exchanging operational data.
This paper argues that runtime semantic negotiation represents a distinct and unsolved interoperability regime, separate from both shared-schema validation and pre-engineered semantic mapping. We identify four fundamental capabilities required for practical deployment: machine-readable semantic publication, explicit expression of data requirements, runtime validation of exchanged information, and mechanisms for maintaining semantic agreements as participating systems evolve.
Building upon established Semantic Web technologies—including RDF, SHACL, and ShEx—we outline how existing standards provide the technical foundations for this capability while highlighting the absence of standardized negotiation protocols between previously unknown agents.
Finally, we propose a seven-problem research agenda addressing trust establishment, negotiation efficiency, benchmark development, governance, security, lifecycle management, and economic evaluation. We argue that solving the Stranger Problem is essential for enabling scalable, trustworthy multi-agent ecosystems and represents a foundational challenge for the next generation of semantic interoperability infrastructure.
