A Fundamental Limit in Decentralized Decision-Making
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.
Related
- Decentralized Decision-Making among Heterogeneous Autonomous Vehicles: An α-Potential Game Framework
- A Decentralized Partially Observable Team Decision Methodology with Delayed Information Sharing
- Stochastic consensus dynamics for decentralized decision systems
- Classes of Aggregation Rules for Ethical Decision Making in Automated Systems
- Risk-Averse Decision Making with Multi-Level Reliability Guarantees
BibTeX
@misc{carpentiero2026fundamental,
title = {{A Fundamental Limit in Decentralized Decision-Making}},
author = {Marco Carpentiero and Felice Scala and Vincenzo Matta and Ali H. Sayed},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07479},
eprint = {2609.07479},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07479},
}
RIS
TY - UNPB
TI - A Fundamental Limit in Decentralized Decision-Making
AU - Marco Carpentiero
AU - Felice Scala
AU - Vincenzo Matta
AU - Ali H. Sayed
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07479
UR - https://arxiv.org/abs/2609.07479
AB - 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.
ER -