Decentralized decision-making shows unavoidable performance gap to centralized methods
A Fundamental Limit in Decentralized Decision-Making
Information TheoryMultiagent Systems
Summary
When several connected agents work together to classify data but can only share information with their immediate neighbors, their best collective decisions are less accurate than if a central authority made the decisions. The authors demonstrate that this loss in accuracy cannot be eliminated, even with perfect algorithms. They explain that the performance gap depends on how agents are connected and the nature of the decision problem, and they analyze how this gap grows with network size and arrangement.
What this means in practice
- •For network system designers: Design networked systems with knowledge that local-only information exchange fundamentally limits classification accuracy compared to centralized approaches.
- •For autonomous vehicle developers: Account for unavoidable performance loss when designing decentralized object recognition systems using vehicles that share information only with neighbors.
A theory result. No direct application yet.
Authors
Marco Carpentiero, Felice Scala, Vincenzo Matta, Ali H. Sayed
Abstract
In decentralized decision-making, several agents connected according to a network graph aim at solving a classification problem by collecting streaming observations. Due to decentralization, they run an iterative algorithm where, at each iteration, they can only exchange information locally with their neighbors. While decentralized estimation solutions have been shown to match the performance of optimal centralized systems, we show here that surprisingly this conclusion does not hold for decentralized decision-making. Specifically, we prove that the error probability for the best decentralized decision strategy exhibits an irreducible loss with respect to the optimal centralized classifier. This result establishes a fundamental limit for the performance of any decentralized decision strategy. We obtain an analytical relation showing that this limit is related to the interplay between decentralization and classification. The first aspect appears through the distances between the nodes in the graph, while the second aspect plays through the moment generating functions of the likelihood ratios that describe the decision problem. By applying the derived closed-form relation to different network topologies and inference problems, we observe some interesting and perhaps unexpected behavior emerging. In particular, we characterize the scaling law (with the network size) for the loss over popular network topologies, showing that the error probabilities might differ by orders of magnitude; and we examine how performance is affected by the relative distance between informative and uninformative agents over the graph.