Certifying information flow in multi-agent behaviours
Abstract
We study which input-output behaviours of several agents can be produced by a declared communication schedule, that is, a fixed sequence of senders, recipients, message alphabets, and output times, together with shared randomness. Since a schedule admits only finitely many deterministic protocols, membership is a linear program, and an infeasible target is excluded by a separating inequality. Under explicit operational assumptions, we prove that the affine hull of the achievable behaviours is described exactly by the equalities stating that each joint output statistic depends only on the inputs that can reach the agents involved, so that a violated equality identifies both the statistic and the missing input. One binary message per event already attains this affine hull, so message capacity restricts which behaviours are achievable without being visible to any equality. We apply the result to one-bit broadcast and relay hierarchies for two and three agents, and to low-order projections of the local polytope.
Related
- Minimum Experimental Information for Certifying Bell Nonlocality of Gravity
- Multi-time advantage for certifying quantum coherence
- The coupled spread of information and potential-driven motion in evacuating agent populations
- Labtune: Treating Lab Organization and Information Sharing as Experimental Variables in LLM-Agent Discovery
- Role differentiation as ignition of a collective information engine: Structuration in Agent Populations
BibTeX
@misc{akbar2026certifying,
title = {{Certifying information flow in multi-agent behaviours}},
author = {M. Haider Akbar and Onur Pusuluk and Özgür E. Müstecaplıoğlu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23631},
eprint = {2610.23631},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23631},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Certifying information flow in multi-agent behaviours
AU - M. Haider Akbar
AU - Onur Pusuluk
AU - Özgür E. Müstecaplıoğlu
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23631
UR - https://arxiv.org/abs/2610.23631
AB - We study which input-output behaviours of several agents can be produced by a declared communication schedule, that is, a fixed sequence of senders, recipients, message alphabets, and output times, together with shared randomness. Since a schedule admits only finitely many deterministic protocols, membership is a linear program, and an infeasible target is excluded by a separating inequality. Under explicit operational assumptions, we prove that the affine hull of the achievable behaviours is described exactly by the equalities stating that each joint output statistic depends only on the inputs that can reach the agents involved, so that a violated equality identifies both the statistic and the missing input. One binary message per event already attains this affine hull, so message capacity restricts which behaviours are achievable without being visible to any equality. We apply the result to one-bit broadcast and relay hierarchies for two and three agents, and to low-order projections of the local polytope.
ER -