Decentralized Stochastic Decision Problems and Polynomial Optimization

In this paper we consider the problem of determining optimal decentralized decision rules in discrete stochastic decision problems. Here we consider a static single-stage problem. It has been shown in \cite{Tsitsiklis85} that the static problem is NP-hard, even for the case of two decision makers. We show that this problem has an equivalent formulation as minimization of a bilinear polynomial subject to linear constraints. We then form a relaxation of this polynomial optimization problem, from which we can compute suboptimal decentralized decision rules as well as bounds on the optimal achievable value. The methods are illustrated by an example of decentralized detection.