Variations on the theme of the Witsenhausen counterexample

This is a semi-tutorial paper that places Witsenhausen’s celebrated 1968 counterexample within a broad class of dynamic decision problems with nonclassical information, which includes stochastic linear-quadratic Gaussian (LQG) teams as well as LQG zero-sum stochastic games. For a fixed (nonclassical) information structure, there are instances (depending on the structure of the objective function) when linear policies are optimal and other instances (including Witsenhausen’s counterexample) when the optimal policies are nonlinear. The paper discusses these instances, optimality as well as saddle-point property (in the case of zero-sum games) of linear policies, and implications of these results for general multi-stage decision problems with specific information structures. It also discusses possible extensions to nonzero-sum stochastic dynamic games where the solution concept is Nash equilibrium.