An Algorithm for Multi-Unit Combinatorial Auctions

Kevin Leyton-Brown, Yoav Shoham, and Moshe Tennenholtz, Stanford University

We present a novel algorithm to compute the winners in a combinatorial auction (CA), that is, an auction in which bidders bid for bundles of goods. Recently published algorithms are limited to single-unit CAs, already a hard computational problem. In contrast, here we address the more general problem in which there are multiple units of each good, and each bid specifies the number of units desired from each good. We prove that our branch-and-bound algorithm, which incorporates a specialized dynamic programming procedure, is correct. We then provide very encouraging initial experimental results with an implemented version of the algorithm.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.