Caching in Multi-unit combinatorial auctions
2002 (English)In: International Joint Conference on Autonomous Agents & Multiagent systems, 2002Conference paper (Refereed)
Combinatorial Auctions are preferable to traditional (sequential) auctions since they allow bidders to express complementarity and substitutability relationships between items, and hence may enhance economic efficiency. However, in such auctions, the problem of determining the optimal winning bids is \textitNP-hard in the general case. In a recent paper, Leyton-Brown et al. have proposed an algorithm for computing the winners in a multi-unit combinatorial auction. It is a branch and bound algorithm that makes use of a caching technique. In this note, we present a counterexample to show that caching, as described by the authors, may fail and the algorithm may eventually give a suboptimal solution. We discuss why it fails and propose how it could be fixed and properly used in a General (multi-unit) combinatorial auction.
Place, publisher, year, edition, pages
IdentifiersURN: urn:nbn:se:uu:diva-10663OAI: oai:DiVA.org:uu-10663DiVA: diva2:38431