In presence of high dimensional stochastic data, handling joint distribution of correlated random variables can present a formidable task, with respect to sampling and estimation as well as algorithmic complexity. A common heuristic is to estimate only marginal distributions and substitute joint distribution by independent (product) distribution. We study the possible suboptimality of decisions resulting from ignoring correlations. We utilize a distributionally-robust stochastic programming (DRSP) model to quantify this loss as Price of Correlations (POC). Using techniques of cost-sharing from game theory, we identify a wide class of problems for which POC has a small upper bound. This class includes many stochastic convex programs, uncapacitated facility location, Steiner tree, and submodular functions, suggesting that the intuitive and efficient approach of assuming independent distribution closely approximates the robust model for these stochastic optimization problems. In addition to providing an approximation scheme for solving the DRSP model, POC provides a conceptual understanding of value of correlations in a decision problem involving uncertainties. Since its introduction, our bounds on POC have found further applications in fields like welfare maximization, k-dimensional matching, transportation problems, and incentive compatible mechanism design.
Copyright. All Rights Reserved.