On the Coordination Efficiency of Strategic Multi-Agent Robotic Teams

We study the problem of achieving decentralized coordination by a group of strategic decision-makers choosing to engage or not in a task in a stochastic setting. First, we define a class of symmetric utility games that encompass a broad class of coordination games, including the popular framework known as global games. To study the extent to which agents engaging in a stochastic coordination game indeed coordinate, we propose a new probabilistic measure of coordination efficiency. Then, we provide a universal information-theoretic upper bound on the coordination efficiency as a function of the amount of noise in the observation channels. Finally, we revisit a large class of global games, and we illustrate that their Nash equilibrium policies may be less coordination efficient than certainty equivalent policies, despite them providing better expected utility. This counter-intuitive result, establishes the existence of a nontrivial trade-off between coordination efficiency and expected utility in coordination games.