  We consider a robust model proposed by Scarf, 1958, for stochastic
optimization when only the marginal probabilities of (binary) random variables
are given, and the correlation between the random variables is unknown. In the
robust model, the objective is to minimize expected cost against worst possible
joint distribution with those marginals. We introduce the concept of
correlation gap to compare this model to the stochastic optimization model that
ignores correlations and minimizes expected cost under independent Bernoulli
distribution. We identify a class of functions, using concepts of summable cost
sharing schemes from game theory, for which the correlation gap is well-bounded
and the robust model can be approximated closely by the independent
distribution model. As a result, we derive efficient approximation factors for
many popular cost functions, like submodular functions, facility location, and
Steiner tree. As a byproduct, our analysis also yields some new results in the
areas of social welfare maximization and existence of Walrasian equilibria,
which may be of independent interest.
