The Stranger Problem: Why AI Agents Need Runtime Semantic Negotiation Before They Can Trust Each Other

The Stranger Problem

Artificial intelligence is rapidly evolving from isolated assistants into autonomous agents capable of collaborating with one another. These agents can place orders, exchange records, coordinate logistics, process claims, and complete business transactions across organizational boundaries. The technical infrastructure required to move data between systems is improving quickly. APIs, messaging platforms, and interoperability protocols make data exchange increasingly straightforward. However, moving data is not the same as sharing meaning. When two AI agents that have never interacted before attempt to cooperate, they lack a reliable way to verify that they interpret exchanged information in the same way. This missing layer of semantic agreement creates what we call the Stranger Problem.

The Trust Gap Between AI Agents

Human collaboration depends on establishing shared understanding before acting. Even when people speak different languages, they clarify expectations, define terminology, negotiate meaning, and verify understanding. AI systems currently lack an equivalent mechanism. Without semantic negotiation, agents may:

• interpret identical data differently

• assume incompatible schemas

• make incorrect decisions while appearing confident

• silently propagate errors throughout automated workflows

As AI systems become increasingly autonomous, these semantic failures become more costly than simple transport failures.

Why This Matters

Failures in multi-agent systems are often caused not by poor reasoning, but by miscommunication. Consequences include:

• failed business transactions

• incorrect automation

• inconsistent data interpretation

• unnecessary human intervention

• increasing integration costs as ecosystems grow

Even organizations using advanced AI models continue to rely heavily on manual integration work because semantic understanding cannot yet be established dynamically.

The "Stranger Tax"

Every first interaction between unfamiliar AI systems introduces additional cost. This hidden "Stranger Tax" appears as:

• custom integrations

• manual schema mapping

• validation logic

• human review

• maintenance of one-off connectors

The problem becomes exponentially more expensive as more organizations and agents participate in the ecosystem. Unlike communication between systems owned by the same organization, agents from different companies share neither governance nor assumptions. The cost of these first-time interactions has never been systematically measured.

What Runtime Semantic Negotiation Requires

A practical solution requires more than data exchange. Agents must establish semantic agreement before taking action. Four core capabilities are required.

1. Publish Meaning Each participant must expose machine-readable descriptions of what its data represents.

2. Express Requirements Consumers must declare the structure and semantics they require for a particular task.

3. Verify Before Acting Incoming data must be validated against published semantic commitments before decisions are made. Validation should produce explicit success or failure—not assumptions.

4. Evolve Safely As schemas change over time, semantic agreements must remain synchronized without silently breaking existing integrations.

Three Types of Interoperability

Not all interoperability challenges are equally difficult.

Shared Vocabulary

Both parties already use the same semantic model. Validation is straightforward because meaning is already shared.

Predefined Mapping

Different schemas exist, but engineers create translation rules ahead of time. This represents most enterprise integration work today.

Runtime Negotiation

Two previously unknown systems interact without any preexisting mapping or human preparation. They must:

• discover semantic compatibility

• negotiate shared understanding

• validate exchanged information

• establish sufficient trust before acting

This third scenario remains largely unsolved and represents the central challenge of the emerging agent economy.

An Open Research Agenda

Addressing the Stranger Problem requires coordinated research across multiple disciplines. Several important questions remain open.

How little negotiation is enough?

Determine the minimum information exchange required to establish safe semantic agreement.

How can semantic claims be trusted?

Develop mechanisms that allow systems to verify that published semantic descriptions are accurate and trustworthy.

When should negotiation occur?

Agents need principled ways to determine when negotiation is worthwhile and when refusing cooperation is the safer option.

How should different environments be handled?

Open internet environments, regulated industries, and trusted consortiums each require different negotiation strategies.

How can agreements evolve?

Semantic contracts must remain valid as participating systems change over time.

How can progress be measured?

The industry needs shared benchmarks to quantify semantic failures and compare proposed solutions.

How can systems remain secure?

Negotiation protocols must provide sufficient transparency for verification while protecting proprietary information and resisting malicious behavior.

A Community Effort

The technologies needed to build runtime semantic negotiation already exist in the Semantic Web ecosystem. Standards such as RDF, SHACL, and ShEx provide many of the necessary building blocks. The challenge is establishing common protocols that allow previously unknown agents to use these standards during first contact. Achieving this requires collaboration across researchers, standards organizations, platform providers, and practitioners. Three immediate priorities include:

1. Shared benchmark datasets for evaluating semantic negotiation.

2. Standardized metrics for measuring the cost of semantic failures.

3. An open working group dedicated to developing interoperable runtime negotiation standards

Looking Ahead

The future of autonomous AI systems depends not only on more capable models but also on trustworthy communication. One future allows AI agents to exchange information with explicit, verifiable meaning, validating every interaction before action is taken and producing auditable records of semantic agreement. The alternative relies on increasingly powerful language models to infer meaning implicitly—producing confident responses that cannot be independently verified where correctness matters most. The technical foundations for the first future already exist. The remaining challenge is agreeing on how strangers establish trust before they act.

This article introduces the key ideas behind the Stranger Problem.

For the complete academic discussion Read the paper →