The Price of Information in Combinatorial Optimization

Sahil Singla

Abstract

Consider a network design application where we wish to lay down a minimum-cost spanning tree in a given graph; however, we only have stochastic information about the edge costs. To learn the precise cost of any edge, we must conduct a study that incurs a price. Our goal is to find a spanning tree while minimizing the disutility, which is the sum of the tree cost and the total price spent on studies. Conversely, in reward-based applications, the goal is to maximize utility (tree reward minus probing prices). This work generalizes Weitzman’s classic "Pandora’s Box" problem to complex combinatorial structures like matchings, set covers, and Steiner trees. We introduce a reduction technique that transforms these "Price of Information" (PoI) problems into their non-price counterparts, enabling the design of exact and approximation algorithms for optimizing expected utility or disutility.

Introduction

In traditional combinatorial optimization, the parameters of a problem—such as the cost of an edge in a graph or the weight of an item in a knapsack—are typically assumed to be known constants. In practice, however, these values are often uncertain. While stochastic optimization addresses uncertainty by modeling parameters as random variables, it often assumes that the true values remain hidden until a decision is made.

This paper addresses a more nuanced reality: the Price of Information. In many scenarios, the true value of a parameter can be revealed, but only after paying a "probing price." For example, a civil engineering firm might have a rough estimate for the cost of a tunnel, but a precise quote requires an expensive geological survey. The challenge is to determine an optimal policy: which elements should be probed, in what order, and when should we stop probing and commit to a solution?

The Pandora’s Box Framework

The foundation of this research is Weitzman’s "Pandora’s Box" problem (1979). In the original model, an agent is presented with $n$ boxes, each containing a random reward. To see the reward in box $i$, the agent must pay a cost $\pi_i$. The goal is to maximize the value of the single best item found, minus the total probing costs.

This paper extends this logic to Combinatorial Pandora’s Box problems. Instead of selecting a single item, the agent must select a set of items that satisfy a specific combinatorial constraint (e.g., forming a spanning tree or a feasible matching). The objective is to optimize the total expected utility (Reward - Price) or disutility (Cost + Price).

Methodology: Grades and Frugality

The "Grade" System

The core of the proposed reduction is the concept of a Grade (denoted as $\tau$). For any random variable $X_i$ with a probing price $\pi_i$, the grade is a threshold value that captures the "worth" of probing. Mathematically, it is the value where the expected gain from revealing the actual outcome exactly balances the cost of the probe. By calculating these grades, the complex decision of whether to probe an element can be simplified into a comparison against a single surrogate value.

FRUGAL Algorithms

The paper’s primary theoretical contribution is the identification of FRUGAL algorithms. An algorithm is defined as frugal if it satisfies two conditions:

  1. Irrevocability: Once an element is selected for the solution, it cannot be removed.
  2. Independence of Future Information: The decision to include an element is based only on the information revealed so far.

The author proves a Transfer Theorem: If an $\alpha$-approximation frugal algorithm exists for a standard optimization problem in a "Free-Information" world (where values are known), then an $\alpha$-approximation algorithm exists for the same problem in the PoI world. This allows researchers to leverage decades of existing research in greedy and primal-dual algorithms to solve PoI problems.

Key Results and Approximations

By applying the Transfer Theorem, the paper provides a suite of approximation guarantees for various combinatorial structures. Notably, it shows that for Matroid Basis problems (like the Minimum Spanning Tree), an optimal adaptive policy can be found. For more complex constraints, the following approximations are established:

Problem Type Constraint Result
Utility Maximization $k$-system (e.g., matchings) $k$-approximation
Knapsack 2-approximation
Disutility Minimization Matroid Basis (e.g., MST) Optimal adaptive algorithm
Set Cover $\min\{O(\log |V|), f\}$-approx
Facility Location 1.861-approximation
Steiner Tree 3-approximation
Feedback Vertex Set $O(\log n)$-approximation

Discussion and Limitations

While the FRUGAL framework is powerful, it has limitations. The paper notes that the $s-t$ shortest path problem remains an open challenge because standard shortest-path algorithms are not naturally frugal in a way that translates to the PoI setting. Additionally, the current model assumes that the random variables are independent. If the cost of one edge provides information about the cost of another (correlation), the "Grade" system requires significant modification.

Finally, the paper establishes hardness results for general submodular functions, proving that finding a good solution is $\Omega(\sqrt{n})$ hard even in deterministic settings, suggesting that the success of the PoI reduction is closely tied to the specific combinatorial structure of the problem.

Summary updated

Abstract

Consider a network design application where we wish to lay down a minimum-cost spanning tree in a given graph; however, we only have stochastic information about the edge costs. To learn the precise cost of any edge, we have to conduct a study that incurs a price. Our goal is to find a spanning tree while minimizing the disutility, which is the sum of the tree cost and the total price that we spend on the studies. In a different application, each edge gives a stochastic reward value. Our goal is to find a spanning tree while maximizing the utility, which is the tree reward minus the prices that we pay. Situations such as the above two often arise in practice where we wish to find a good solution to an optimization problem, but we start with only some partial knowledge about the parameters of the problem. The missing information can be found only after paying a probing price, which we call the price of information. What strategy should we adopt to optimize our expected utility/disutility? A classical example of the above setting is Weitzman's "Pandora's box" problem where we are given probability distributions on values of $n$ independent random variables. The goal is to choose a single variable with a large value, but we can find the actual outcomes only after paying a price. Our work is a generalization of this model to other combinatorial optimization problems such as matching, set cover, facility location, and prize-collecting Steiner tree. We give a technique that reduces such problems to their non-price counterparts, and use it to design exact/approximation algorithms to optimize our utility/disutility. Our techniques extend to situations where there are additional constraints on what parameters can be probed or when we can simultaneously probe a subset of the parameters.
BibTeX
@inproceedings{singla2018price,
  author = {Sahil Singla},
  title = {{The Price of Information in Combinatorial Optimization}},
  booktitle = {SODA},
  year = {2018},
  doi = {10.1137/1.9781611975031.161},
}
Figure