Loading
April 2005
Abstract: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
Available as PDF (245 kB, no cover), compressed Postscript (985 kB, no cover), and Postscript (1.86 MB, no cover)
Download BibTeX entry.