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 @math 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.
The Pandora's box solution can be written as a special case of the Gittins index theorem @cite_19 . @cite_22 consider a minimization variant of the Gittins index theorem when there is no discounting. Another very relevant paper is that of @cite_13 , while their results are to design auctions. Their proof of the Pandora's box problem inspired this work.
@cite_19 @cite_13 @cite_22
2304126241 1987077169
When exploring acquisition targets, firms typically begin with the possibilities offering greatest option value and work their way down, as prescribed by optimal search theory. Yet the market designs economists have often prescribed, involving simultaneous or ascending prices, stymie this process. As a result they may be arbitrarily inefficient when one accounts for the costs bidders must invest to learn their value for acquiring different items. We present a model that incorporates such costs, and a simple descending price procedure that we prove robustly approximates the fully optimal sequential search process quite generally. Our results exploit a novel characterization of Weitzman's "Pandora's Box" problem in terms of option pricing theory that connects seamlessly with recent techniques from algorithmic mechanism design. We analyze and solve a game in which a player chooses which of several Markov chains to advance, with the object of minimizing the expected time (or cost) for one of the chains to reach a target state. The solution entails computing (in polynomial time) a function @math ---a variety of "Gittins index"---on the states of the individual chains, the minimization of which produces an optimal strategy. It turns out that @math is a useful cousin of the expected hitting time of a Markov chain but is defined, for example, even for random walks on infinite graphs. We derive the basic properties of @math and consider its values in some natural situations.