Formal Semantics for Verifiable Multiagent Interaction

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 122 papers33 conceptsfrozen 2026-10-04

In a closed software system, we control every line of code. If Object A calls a method on Object B, we know exactly what will happen because we defined the internal logic of both. But as we move toward "open" systems—like decentralized marketplaces, autonomous web services, or collaborative AI swarms—this control vanishes. You might own Agent A, but Agent B is a "black box" developed by someone else.

In these environments, we cannot rely on knowing an agent's internal code. Instead, we must rely on social commitments: public, verifiable promises that agents make to one another. The research direction explored here focuses on turning these informal "promises" into rigorous mathematical structures that can be automatically verified, monitored, and enforced.

From Private Intentions to Public Commitments

Early AI research focused on the "mental states" of agents—their Beliefs, Desires, and Intentions (BDI). While useful for individual reasoning, Munindar P. Singh argued in Towards a Formal Theory of Communication for Multi-agent Systems that mental states are insufficient for communication. You cannot "verify" if an agent truly intends to pay you; you can only verify if they do pay you.

To solve this, researchers shifted the focus to social commitments. A commitment is a contract between a debtor and a creditor. If an agent says, "I will ship the book if you pay $20," they have created a conditional commitment. Singh later refined this in Semantical Considerations on Dialectical and Practical Commitments, distinguishing between claims about facts (dialectical) and promises to act (practical). By defining "satisfaction conditions" for these acts, we move communication from vague prose to a logic that a machine can check for compliance.

Grounding Logic in Execution Paths

The challenge with formal logic is that it often feels disconnected from actual code. How do you prove that a Python script "believes" something? Kaile Su, Abdul Sattar 0001, and their colleagues addressed this through computationally grounded models.

In papers like Computationally Grounded Model of BDI-Agents and Observation-based Model for BDI-Agents, they propose a bridge: treat an agent’s mental states as sets of possible execution paths (or "runs") of a computer program.

  • A Belief is not a feeling; it is the set of all states the program could possibly be in given its history.
  • An Intention is a subset of those paths that the agent is programmed to pursue.

By mapping abstract logic to concrete system transitions, researchers can use tools like Symbolic Model Checking and Ordered Binary Decision Diagrams (OBDDs) to mathematically prove that an agent will (or won't) violate a protocol before the code even runs.

The Rules of the Game: Electronic Institutions

If commitments are the "contracts" between agents, then Electronic Institutions are the "courtrooms" and "laws" that govern them. Marc Esteva and his team in Engineering Open Multi-Agent Systems as Electronic Institutions proposed shifting the engineering focus from the agents to the environment.

Instead of trying to make every agent "good," you build a framework that defines:

  1. Ontologies: A shared vocabulary so agents don't talk past each other.
  2. Protocols: The valid sequences of messages (e.g., you can't "award" a contract before a "bid" is placed).
  3. Norms: The consequences of actions, such as obligations and penalties.

This "macro-level" approach allows for framed autonomy. As described in the Agentic Business Process Management manifesto by Diego Calvanese and others, agents are free to reason and act independently as long as they stay within the "guardrails" of the organizational goals and normative constraints.

Real-Time Monitoring and Verification

Once a system is running, how do we know if agents are actually keeping their word? Federico Chesani and Marco Montali introduced the Reactive Event Calculus (REC) in Commitment Tracking via the Reactive Event Calculus.

REC provides a logic-based engine that listens to the "events" (messages) in a system and updates the state of social commitments in real-time. It can instantly detect if a deadline has been missed or if an obligation has been triggered. This moves verification from a static, one-time check to a dynamic, continuous process. Similarly, Nardine Osman 0001 and David Stuart Robertson 0001 developed frameworks for Dynamic Verification of Trust, allowing agents to use lightweight model checkers to verify the safety of a protocol at runtime before they agree to participate.

The Future: Semantic and System 2 Communication

As we move toward 6G and advanced AI, the nature of these interactions is evolving. Mehdi Bennis suggests in Semantic Communication meets System 2 ML that we are moving beyond the simple exchange of bits toward "System 2" communication. In this paradigm, agents don't just follow pre-defined scripts; they use abstraction and reasoning to evolve their own emergent languages.

The core challenge remains the same: how do we ensure these evolved, autonomous interactions remain safe and explainable? The answer lies in the continued development of the formal foundations laid by these researchers—ensuring that no matter how complex the agent, its "word" (its commitment) remains a mathematically verifiable fact.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_formal_semantics_for_verifiable_multiage_e6fe8122,
  title = {Formal Semantics for Verifiable Multiagent Interaction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/formal-semantics-for-verifiable-multiagent-interaction/rdr_e6fe8122235f4e3fae754235365f4acd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_formal_semantics_for_verifiable_multiage_e6fe8122_v1,
  title = {Formal Semantics for Verifiable Multiagent Interaction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/formal-semantics-for-verifiable-multiagent-interaction/rdr_e6fe8122235f4e3fae754235365f4acd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}