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:
- Irrevocability: Once an element is selected for the solution, it cannot be removed.
- 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