uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Caching in Multi-unit combinatorial auctions
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics.
Department of Information Technology. Datalogi.
2002 (English)In: International Joint Conference on Autonomous Agents & Multiagent systems, 2002Conference paper (Refereed)
Abstract [en]

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
URN: urn:nbn:se:uu:diva-10663OAI: oai:DiVA.org:uu-10663DiVA: diva2:38431
Available from: 2007-04-18 Created: 2007-04-18

Open Access in DiVA

No full text

Other links

By organisation
Department of MathematicsDepartment of Information Technology

Search outside of DiVA

GoogleGoogle Scholar

Total: 278 hits
ReferencesLink to record
Permanent link

Direct link