An Algorithm for Multi-Unit Combinatorial Auctions

Abstract

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 specifies 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. Introduction Auctions are the most widely studied mechanism in the mechanism design literature in economics and game theory (Fudenberg & Tirole 1991). This is due to the fact that auctions are basic protocols, serving as the building blocks of more elaborated mechanisms. Given the wide popularity of auction...