Iterative Combinatorial Auctions: Theory and Practice

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 17

Agents

Combinatorial auctions, which allow agents to bid directly for bundles of resources, are necessary for optimal auction-based solutions to resource allocation problems with agents that have non-additive values for resources, such as distributed scheduling and task assignment problems. We introduce iBundle, the first iterative combinatorial auction that is optimal for a reasonable agent bidding strategy, in this case myopic best-response bidding. Its optimality is proved with a novel connection to primal-dual optimization theory. We demonstrate orders of magnitude performance improvements over the only other known optimal combinatorial auction, the Generalized Vickrey Auction.