Minimum cardinality non-anticipativity constraint sets for multistage stochastic programming (Q291043)

Stochastic programing provides an approach to decision-making that takes account of the probability distributions of uncertain parameters. Typically the values of these parameters are revealed over time, or with stage in a multistage decision setting, and decisions made at each stage hedge against possible realizations of parameters revealed in future stages. Endogenous uncertainty is defined to occur when the underlying stochastic process depends on the optimization decisions. The majority of the papers assumes that the sources of uncertainty are exogenous to the decision-making process; relatively little attention has, to date, been paid to stochastic programming in the presence of \textit{endogenous uncertainty}. Endogenous uncertainty is defined to occur when the underlying stochastic process depends on the optimization decisions. This paper contributes to the general field of multistage stochastic programming with endogenous uncertainty by characterizing necessary and sufficient sets of non-anticipativity constraints, without any restriction on the scenario space. The authors prove that sufficient sets of non-anticipativity constraints have matroid structure, and hence prove that such sets having minimum cardinality can be identified efficiently, in the general case.