The complexity of multiagent systems

Abstract

In this work, we suggest representing multiagent systems using computational models, choosing, specifically, Multi-Prover Interactive Protocols to represent agent systems and the interactions occurring within them. This approach enables us to analyze complexity issues related to multiagent systems. We focus here on the complexity of coordination and study the possible sources of this complexity. We show that there are complexity bounds that cannot be lowered even when approximation techniques are applied.