Limits on accuracy for networks making decisions together
A Fundamental Limit in Decentralized Decision-Making
Information TheoryMultiagent Systems
Summary
When a group of connected agents try to decide something based on incoming data, they often can only talk to their immediate neighbors. While previous studies showed that estimating values in such networks can be just as good as doing it all in one place, this paper finds that actually making decisions (like classifying things) this way always comes with some unavoidable errors compared to a central system. The authors explain that this error limit depends on how the agents are connected and how easy or hard the decision problem is. They also show that different network shapes and which agents have useful information can greatly affect how well the group performs.
decentralized decision-makingclassification problemnetwork grapherror probabilitycentralized vs decentralizediterative algorithmlikelihood ratiomoment generating functionnetwork topologystreaming observations
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.