On the complexity of decentralized decision making and detection problems
- 1 May 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 30 (5), 440-446
- https://doi.org/10.1109/tac.1985.1103988
Abstract
We study the computational complexity of the discrete versions of some simple but basic decentralized decision problems. These problems are variations of the classical "team decision problem" and include the problem of decentralized detection whereby a central processor is to select one of two hypotheses, based on l-bit messages from two noncommunicating sensors. Our results point to the inherent difficulty of decentralized decision making and suggest that optimality may be an elusive goal.Keywords
This publication has 12 references indexed in Scilit:
- The decentralized wald problemInformation and Computation, 1987
- The decentralized quickest detection problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- On the complexity of designing distributed protocolsInformation and Control, 1982
- The complexity of the generalized Lloyd - Max problem (Corresp.)IEEE Transactions on Information Theory, 1982
- Detection with Distributed SensorsIEEE Transactions on Aerospace and Electronic Systems, 1981
- Team decision theory and information structuresProceedings of the IEEE, 1980
- Survey of decentralized control methods for large scale systemsIEEE Transactions on Automatic Control, 1978
- The zero-error side information problem and chromatic numbers (Corresp.)IEEE Transactions on Information Theory, 1976
- A Counterexample in Stochastic Optimum ControlSIAM Journal on Control, 1968
- Team Decision ProblemsThe Annals of Mathematical Statistics, 1962