The Price of Information in Combinatorial Optimization

Sahil Singla

TL;DR

This paper generalizes the classic "Pandora’s Box" problem to complex combinatorial structures like spanning trees, matchings, and set covers. It introduces a powerful reduction technique showing that if you have a "FRUGAL" algorithm (one that makes irrevocable choices) for a standard optimization problem, you can adapt it to handle uncertain data where revealing the truth requires paying a probing price.

What Problem Does This Paper Address?

In traditional combinatorial optimization, we assume we know the costs or rewards of every element (like edges in a graph or items in a knapsack). In reality, information is rarely free.

Imagine you are designing a network. You have a rough estimate of the cost to lay a cable between two cities, but to get the exact quote, you have to pay a contractor to conduct a site survey. Your goal isn't just to find the cheapest tree; it's to minimize the disutility—the sum of the final construction costs plus all the money you spent on surveys.

This is a generalization of Weitzman’s "Pandora’s Box" problem. In the original version, you just want to pick the single best item from a set of boxes, each with a hidden value and a cost to open. This paper asks: What if you need to pick a whole set of items that satisfy a specific constraint (like forming a matching or a spanning tree) while balancing the "Price of Information" (PoI)?

Methods

The author, Sahil Singla, tackles this by bridging two different "worlds":

  1. The PoI World: Information is hidden, and probing costs money ($\pi_i$).
  2. The Free-Info World: Information is free, but the values of the items are modified into "surrogate" variables ($Y_i$).

The "Grade" System

The core mathematical tool is the Grade ($\tau$). For any random variable, the grade is a single number that captures the "worth" of probing that variable. It’s essentially the threshold where the expected gain from seeing the actual value equals the cost of the probe.

FRUGAL Algorithms

The paper’s most significant contribution is the definition of a FRUGAL algorithm. An algorithm is frugal if it picks elements one-by-one and irrevocably (it never changes its mind or deletes an element once selected).

The author proves a "Transfer Theorem" (Theorem 1.6): If an $\alpha$-approximation FRUGAL algorithm exists for a problem in the Free-Info world, then an $\alpha$-approximation algorithm also exists for that problem in the PoI world. This is a massive win because many classic greedy and primal-dual algorithms are naturally frugal.

Datasets

As a theoretical computer science paper, this work does not use empirical datasets. Instead, it provides rigorous mathematical proofs and algorithmic analysis for various combinatorial structures defined over independent probability distributions.

Key Insights and Ideas

  • The Power of Irrevocability: The "FRUGAL" property is the secret sauce. Because the algorithm can't "take back" a choice, it naturally aligns with the reality of paying for information—once you've paid to see a value and committed to it, you've spent that budget.
  • Semiadditive Functions: The paper identifies a specific class of objective functions (semiadditive) where the value is a sum of random variables plus a "non-additive" part that doesn't depend on the random outcomes (like connection costs in facility location). This structure allows the "Grade" reduction to work.
  • Mixed-Sign Objectives: Optimization with mixed signs (Reward - Price) is notoriously difficult because standard approximation techniques (like linear programming) often fail to capture the trade-off. The reduction to the Free-Info world bypasses this by turning the price into a modification of the distribution itself.

Key Results

The paper provides a suite of new approximation algorithms for the Price of Information setting:

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

The paper also establishes hardness results, showing that for general submodular functions, finding a good solution is $\Omega(\sqrt{n})$ hard even in a deterministic setting.

Limitations and Future Work

  • The Shortest Path Problem: One notable absence is the $s-t$ shortest path problem. The author notes that there are currently no known "FRUGAL" algorithms with good guarantees for shortest paths, making it an open challenge.
  • Computational Hardness: While many problems were solved, the author points out that finding the optimal policy for max-weight matching in the PoI world remains an open question regarding its computational complexity.
  • Independence Assumption: The current model assumes that the random variables (costs/rewards) are independent. Extending this to correlated variables would be a significant (and difficult) next step.

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},
}

Loading related content...

Figure