Technical Report 2004-045

A Flexible Model for Tree-Structured Multi-Commodity Markets

Per Carlsson and Arne Andersson

October 2004


In this article we study tree-structured multi-commodity markets. The concept is a way to handle dependencies between commodities on the market in a tractable way. The winner determination problem of a general combinatorial market is well known to be NP-hard. It has been shown that on single-unit single-sided auctions with tree-structured bundles the problem can be computed in polynomial time.

We show that it is possible to extend this to multi-unit double-sided markets. Further it is possible to handle the commodities of a bundle not only as complements but as perfect substitutes too. Under certain conditions the computation time is still polynomial.

Available as Postscript (2.37 MB, no cover), PDF (238 kB, no cover), and compressed Postscript (1.26 MB, no cover)

Download BibTeX entry.