An Algorithm for Multi-Unit Combinatorial Auctions

We present a novel algorithm for computing the optimal winning bids in a combinatorial auction (CA), that is, an auction in which bidders bid for bundles of goods. All previously published algorithms are limited to single-unit CAs, already a hard computational problem. In contrast, here we address the more general problem in which each good may have multiple units, and each bid speci€es an unrestricted number of units desired from each good. We prove the correctness of our branch-and-bound algorithm, which incorporates a specialized dynamic programming procedure. We then provide very encouraging initial experimental results from an implemented version of the algorithm.

Authors

• Kevin Leyton-Brown University of British Columbia
• and Moshe Tennenholtz Stanford University

Keywords

No keywords are indexed for this paper.