Approximation Algorithms for k-Duplicates Combinatorial Auctions with Subadditive Bidders.

In this paper, we study the problem of maximizing welfare in combinatorial auctions with k duplicates of each item, where bidders are subadditive. We present two approximation algorithms for k-duplicates combinatorial auctions with subadditive bidders. First, we give a factor-$O(\sqrt{m})$ approximation algorithm for k-duplicates combinatorial auctions with subadditive valuations using value queries. This algorithm is also incentive compatible. Secondly, we give a factor-O(logm) approximation algorithm for k-duplicates combinatorial auctions with subadditive valuations using demand queries. [ABSTRACT FROM AUTHOR]