Economic metaphors for solving intrafirm allocation problems: what does a market buy us?

The primary advantage of using simulated internal markets to solve complex resource allocation problems is that markets permit much of the computation of a solution to be distributed over a large number independent agents running on separate processors. The difficulty that arises in the context of NP-hard resource allocation problems is that the market for resources inevitably takes the form of a combinatorial auction, which induces a different type of NP-hard problem. We examine an important class of stochastic, intrafirm resource allocation problems and ask whether economic constructs, such as agents, markets, and prices, provide a useful foundation for structuring decentralized heuristic solution techniques. We show how complex exchange protocols can help market-based search techniques avoid the local maxima problems associated with other greedy search heuristics and converge on good equilibrium solutions.