- Comparing winner determination algorithms for mixed multi-unit combinatorial auctions
- 7th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2008), Estoril, Portugal
- Book/source title
- AAMAS 2008: 7th International Conference on Autonomous Agents and Multi-Agent Systems: Proceedings: Volume 3
- Pages (from-to)
- Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
- Document type
- Conference contribution
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
Mixed multi-unit combinatorial auctions are combinatorial auctions in which the auctioneer and the bidders negotiate over transformations rather than over simple goods. By proposing a transformation a bidder is offering to produce a certain set of output goods after having received the specified input goods. Solving such a mixed auction means choosing a sequence of transformations such that the auctioneer ends up with all the goods desired at the lowest possible cost. This is a generalisation of the winner determination problem in combinatorial auctions and cannot be solved using standard winner determination algorithms. In this paper we analyse the computational complexity of the winner determination problem for mixed auctions and compare the performance of two new algorithms and of the original algorithm proposed for the problem. We also discuss suitable ways of generating test sets for this comparison.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.