In this paper we study tree-structured multi-commodity, multi-unit 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 combinatorial 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.
Note: Extended version of conference paper accepted for IEEE CEC2005, München, July 2005
Download BibTeX entry.