Solutions to decentralized stochastic optimization problems lead to recursions in which the state space enlarges with the time-horizon, thus leading to non-tractability of classical dynamic programming. A common joint information state supplied to each of the agents leads to a tractable recursion, as is evident in the one-step-delayed information sharing structure case or when deterministic nestedness in information holds when there is a causality relationship as in the case of partially nested information structure. However, communication requirements for such 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, which is characterized by a sequence of Markov chain conditions. It is shown that if the information structure is stochastically nested, then an optimization problem is tractable, and in particular for LQG problems, the team optimal solution is linear, despite the lack of deterministic nestedness or partial nestedness. One other contribution of this paper is that, by regarding the multiple decision makers as a single decision maker and using Witsenhausen's equivalent model for discrete-stochastic control, it is shown that the common state required need not consist of observations and it suffices to share beliefs on the state and control actions; a pattern we refer to as k-stage belief sharing pattern. We discuss the minimum amount of information exchange required to achieve such an information pattern for k = 1. The information exchange needed is generally strictly less than what is needed for deterministic nestedness and is zero whenever stochastic nestedness applies. In view of nestedness, we present a discussion on the monotone values of information channels.