An Algorithm for Multi-Unit Combinatorial Auctions

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 17

Agents

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.