×

A flexible model for tree-structured multi-commodity markets. (English) Zbl 1117.90046

Summary: 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 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.

MSC:

90B60 Marketing, advertising
90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersson, A., Carlsson, P., & Ygge, F. (2002). Resource allocation with wobbly functions. Computational Optimization and Applications, 23(2), 171–200. · Zbl 1028.90038 · doi:10.1023/A:1020524817896
[2] Andersson, A., & Ygge, F. (1998). Managing large scale computational markets. In: El-Rewini, H. (ed.), Proceedings of the Software Technology Track of the 31th Hawaiian International Conference on System Sciences (HICSS31), (vol. VII, pp. 4–14) IEEE Computer Society, Los Alamos, ISBN 0-8186-8251-5, ISSN 1060-3425, IEEE Catalog Number 98TB100216. (Available from http://www.enersearch.se/\(\sim\)ygge ).
[3] Andersson, A., & Ygge, F., (2001). Efficient resource allocation with non-concave objective functions. Computational Optimization and Applications, 20, 281–298. · Zbl 0990.90076 · doi:10.1023/A:1011263102622
[4] http://www.apx.nl .
[5] Borenstein, S., Jaske, M., & Rosenfeld, A. (2002). Dynamic pricing, advanced metering and demand response in electricity markets. (Available from http://www.ef.org ).
[6] Carlsson, P., Ygge, F., & Andersson, A. (2001). Extending equilibrium markets. IEEE Intelligent Systems, 16(4), 18–26.
[7] Carlsson, P., Ygge, F., & Andersson, A. (2003). A tractable mechanism for time dependent markets. Technical Report 2003-027, Department of Information Technology, Uppsala University, (Available from http://www.it.uu.se/research/reports/ ).
[8] Carlsson, P., Ygge, F., & Andersson, A. (2003). A tractable mechanism for time dependent markets. In: Jen Yao Chung and Liang-Jie Zhang (ed.), CEC 2003, IEEE International Conference on E-Commerce (pp. 31–34). IEEE Computer Society, Los Alamos.
[9] Ibaraki, T., & Katoh, N. (1998). Resource Allocation Problems – Algorithmic Approaches. The MIT Press, Cambridge, Massachusetts. · Zbl 0946.90066
[10] Katoh, N., & Ibaraki, T. Resource allocation problems. In: Du, D.-Z. & Pardalos, P.M. (eds.), Handbook of Combinatorial Optimization. (vol. 2, pp. 159–260). chapter Resource Allocation Problems, Kluwer Academic Publisher. · Zbl 0946.90066
[11] Nisan, N. (2000). Bidding and allocation in combinatorial auctions. In EC’00, Proceedings of the 2nd ACM Conference on Electronic Commerce (pp. 1–12). The Association for Computing Machinery, New York, USA.
[12] http://www.nordpool.no .
[13] Patrick, R.H., & Wolak, F.A. (2001). Using customer demands under spot market prices for service design and analysis. Technical Report WO 2801-11, EPRI. (Available from http://www.rci.rutgers.edu/\(\sim\)rpatrick/hp.html ).
[14] Rasmusson L. Evaluating resource bundle derivatives for multi-agent negotiation of resource allocation. In Liu, J. & Ye, Y., (eds.), E-Commerce Agents, number 2033 in LNAI (pp. 154–165), Berlin Heidelberg, Springer Verlag. · Zbl 0978.68749
[15] Rasmusson, L., & Paues, G. (2002). Network components for market-based network admission and routing. Technical report, Swedish Institute of Computer Science, SICS, Kista, Sweden.
[16] Rothkopf, M.H., Pekec, A., & Harstad, R.M. (1998). Computationally manageable combinatorial auctions. Management Science, 44(8), 1131–1147. · Zbl 0989.90094 · doi:10.1287/mnsc.44.8.1131
[17] Tennenholtz, M. (2000). Some tractable combinatorial auctions. In AAAI/IAAI 2000 Proceedings. · Zbl 0999.68003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.