TitleComputationally-efficient Winner Determination for Mixed Multi-Unit Combinatorial Auctions
Publication TypeConference Paper
Year of Publication2008
AuthorsGiovannucci A, Vinyals M, Rodríguez-Aguilar JA, Cerquides J
Conference Name7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 08)
PublisherTo appear
Conference LocationEstoril, Portugal
Pagination1071-1078
Abstract

Mixed Multi-Unit Combinatorial Auctions offer a high po- tential to be employed for the automated assembly of supply chains of agents offering goods and services. Their winner determination problem is an NP-hard problem that can be mapped into an integer program. Nonetheless, the compu- tational cost of the current solution hinders the application of mixed multi-unit combinatorial auctions to realistic sce- narios. In this paper we propose a new integer program for mixed multi-unit combinatorial auctions that severely sim- plifies the problem by taking advantage of the topological characteristics of the winner determination problem. Fur- thermore, we provide empirical evidence showing that the new IP allows to cope with much larger supply chain forma- tion scenarios.