Pairwise independent correlation gap

In decision-making under uncertainty, understanding how elements in a system interact is critical. For example, in warehouse location optimization, a business may face decisions about where to place distribution centres to minimize costs like transportation and inventory. This decision involves understanding dependencies between warehouse locations (how one warehouse affects another). Submodular functions, which exhibit diminishing returns as more resources are added, are commonly used to model costs in such problems. The paper explores how different assumptions about dependencies among system elements impact submodular cost functions that depend on these interactions. A compelling analogy to study such multi-element interactions comes from neuroscience, where cortical neurons are known to exhibit pairwise independence in their random firing patterns, while exhibiting higher-order (triplets, quadruplets, and so on) dependencies. The key point is that by assuming that the neurons fire completely independently, unnecessary and unrealistic structure is forced on their joint random behavior, leading to poor approximations of the cost function on an average.

Drawing inspiration from this, the paper analyzes three models:

1. No Dependence Information Model: Assumes no specific knowledge about dependencies among elements. This serves as a baseline to evaluate other models.
2. Complete Independence Model: Assumes all elements are completely independent, which means every subset of the elements with two or more elements (pairs, triplets, quadruplets, and so on) are independent. While simple to formulate, this model can lead to significant inaccuracies. For submodular cost functions, it is known that the inaccuracy can be as large as e/(e−1) (approximately 1.58), when compared to the no-dependence-information model.
3. Pairwise Independence Model: Assumes elements are independent in pairs, while ignoring higher-order interactions. This is a weaker notion of complete independence. This model strikes a balance between realism and simplicity, with the inaccuracy shrinking from e/(e-1) to 4/3, as compared to the no-dependence-information model.

The findings demonstrate that with submodular cost functions:

• The pairwise independence model significantly improves upon the complete independence model in terms of model inaccuracy
• There is a fundamental difference in the joint random behavior of system elements when pairwise independence is assumed as opposed to complete independence

These results potentially indicate that significant cost benefits can be gleaned from assuming pairwise independence or other weaker forms of interaction between system elements.