Affiliations: Faculty of Informatics, Shizuoka University, 3 5 1 Johoku Hamamatsu, Shizuoka, Japan | Center for Collective Intelligence, Sloan School of Management, Massachusetts Institute of Technology, 5 Cambridge Center, Cambridge MA 02142, USA
Note: [] Visiting from Nagoya Institute of Technology, Japan.
Abstract: Combinatorial auctions, one of the most popular market mechanisms, have a huge effect on electronic markets and political strategies. Combinatorial auctions provide suitable mechanisms for efficient allocation of resources to self-interested attendees. On the other hand, efficient resource allocation is also becoming crucial in many computer systems that should manage resources efficiently. Considering ubiquitous computing scenarios, the ability to complete an auction within a fine-grained time period without loss of allocation efficiency is in strong demand. Furthermore, to achieve such scenarios, it is very important to handle a large number of bids in an auction. In general, the optimal winner determination problem of a combinatorial auction is NP-hard. Thus, much work focuses on tackling the computational costs for winner determination. In this paper, we show that our approximation algorithms provide sufficient quality of winners for auctions that have a large number of bids on hard time constraints. Furthermore, we compare and discuss desirable properties of such approximation algorithms to be embedded in application systems.
