The Stranger Problem: Runtime Semantic Negotiation for Trustworthy Multi-Agent Coordination

Introducing the Stranger Problem, a framework for runtime semantic negotiation that enables trustworthy interoperability between autonomous AI agents.

Canonical source
The Stranger Problem: Runtime Semantic Negotiation for Trustworthy Multi-Agent Coordination

Access this research paper

View this paper on the publisher site.

View DOI

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.

Citations (DOIs or URLs)

  1. https://doi.org/10.5281/zenodo.20754007
  2. https://creativecommons.org/licenses/by/4.0/

Authors

  • C

    Cruce Saunders

    Founder

Publication
Preprint (Zenodo)
Runtime Semantic NegotiationSemantic InteroperabilityMulti-Agent SystemsAgentic AIKnowledge GraphsSemantic WebSHACLShExRDFTrustworthy AISchema NegotiationSemantic ValidationAgent CommunicationAutonomous SystemsMachine-Readable SemanticsArtificial IntelligenceSemantic WebKnowledge GraphsSemantic InteroperabilityMulti-Agent SystemsRuntime ValidationOpen StandardsTrust Frameworks

Published

Share

Take the next step

Try CoreModels, talk with our team, or explore more resources.

Try CoreModelsTalk to usMore resources
The Stranger Problem: Runtime Semantic Negotiation for Trustworthy Multi-Agent Coordination | Aramai