Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andersson, A., Carlsson, P., & Ygge, F. (2002). Resource allocation with wobbly functions. Computational Optimization and Applications, 23(2), 171–200.
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/~ygge).
Andersson, A., & Ygge, F., (2001). Efficient resource allocation with non-concave objective functions. Computational Optimization and Applications, 20, 281–298.
Borenstein, S., Jaske, M., & Rosenfeld, A. (2002). Dynamic pricing, advanced metering and demand response in electricity markets. (Available from http://www.ef.org).
Carlsson, P., Ygge, F., & Andersson, A. (2001). Extending equilibrium markets. IEEE Intelligent Systems, 16(4), 18–26.
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/).
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.
Ibaraki, T., & Katoh, N. (1998). Resource Allocation Problems – Algorithmic Approaches. The MIT Press, Cambridge, Massachusetts.
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.
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.
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/~rpatrick/hp.html).
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.
Rasmusson, L., & Paues, G. (2002). Network components for market-based network admission and routing. Technical report, Swedish Institute of Computer Science, SICS, Kista, Sweden.
Rothkopf, M.H., Pekec, A., & Harstad, R.M. (1998). Computationally manageable combinatorial auctions. Management Science, 44(8), 1131–1147.
Tennenholtz, M. (2000). Some tractable combinatorial auctions. In AAAI/IAAI 2000 Proceedings.
Author information
Authors and Affiliations
Corresponding author
Additional information
Per Carlsson has a broad background and he is currently a full time researcher at Uppsala University. Previously he held a corresponding position at EnerSearch, an energy business oriented research company.
Since the end of the -90s Dr. Per Carlsson has focused on resource allocation in general and electronic markets in particular. The main goal of his is to develop electricity markets to increase the efficiency of our electricity usage.
Currently he is involved in how to increase end user participation to even out fluctuations in electricity demand over the day.
Arne Andersson is chaired professor in Computing Science at Uppsala University and one of the founders of Trade Extensions.
Prof. Andersson is an internationally leading expert on algorithms and optimization with an extensive track record of scientific publications, program committees, editorial boards, etc. He is also key designer of Trade Extensions’ scenario analysis tool, and has deep experience with a number of complex electronic negotiations both in public and private sector.
Rights and permissions
About this article
Cite this article
Carlsson, P., Andersson, A. A flexible model for tree-structured multi-commodity markets. Electron Commerce Res 7, 69–88 (2007). https://doi.org/10.1007/s10660-006-0063-Y
Issue Date:
DOI: https://doi.org/10.1007/s10660-006-0063-Y