Caching in Multi-Unit Combinatorial Auctions paper tracking number(ID) = 55

摘要

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 NP-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 subopti-mal solution. We discuss why it fails and propose how it could be fixed and properly used in a General (multi-unit) combinatorial auction.