Stochastic nestedness and information analysis of tractability in decentralized control

Communication requirements for nestedness conditions require exchange of very large data noiselessly, hence these assumptions are generally impractical. In this paper, we present a weaker notion of nestedness, which we term as stochastic nestedness. Stochastic nestedness is characterized with a sequence of Markov chain conditions. It is shown that if the information structure of two decision makers satisfy a stochastically nested structure, then the optimization admits a dynamic programming recursion and the optimization is tractable; and in particular for the LQG problems, the team optimal solution is linear, despite the lack of deterministic nestedness or partial nestedness. It is also shown that the common state required need not be consisting of observations and it suffices to share beliefs on the state and applied control actions; a pattern we refer to as k-step belief sharing pattern. In case stochastic nestedness is absent, we can evaluate a precise expression for the minimum amount of information required to achieve belief sharing. The information exchange needed is generally strictly less than the information exchange needed for deterministic nestedness (even under optimal coders) and is zero whenever stochastic nestedness applies. We provide explicit examples of stochastically nested information structures and exhibit the benefit of belief sharing on information exchange requirements and discuss the monotone value of information channels.