Planning problems are challenging and complex in that they usually involve multiple stakeholders with multi-attribute preferences. Thus few, if any, planning tools are useful in helping planners address such problems. Decision analysis is less useful than expected in dealing with planning problems because it focuses overwhelmingly on making a single decision for a particular decision-maker. In this paper, we describe the theoretical foundation of a planning tool called the ’decision network’, which aims to help planners make multiple and linked decisions when facing multiple stakeholders with multi-attribute preferences. The research provides a starting point for a fully fledged technology that is useful for dealing with complex planning problems. We first provide a general formulation of the planning problem that the decision network intends to address. We then introduce an efficient solution algorithm for this problem, with a numerical example to demonstrate how the algorithm works. The proposed solution algorithm is efficient, allowing computerization of the planning tool. We also demonstrate that the diagrammatic representation of the decision network is more efficient than that of a decision tree. Therefore, when dealing with challenging and complex planning problems, using the decision network to make multiple and linked decisions may yield more benefits than making such decisions independently.