CS 789 THEORY SEMINAR [home]

Speaker:    Rica Gonen
Affiliation:  The Hebrew University of Jeruselem
Date:          February 7, 2004
Title:          Incentive Compatible Multi-unit Combinatorial Auctions

Abstract: 

This paper deals with multi-unit combinatorial auctions where there are n types of goods for sale, and for each good there is some fixed number of units. We focus on the case where each bidder desires a relatively small number of units of each good. In particular, this includes the case where each good has exactly k units, and each bidder desires no more than a single unit of each good. We provide incentive compatible mechanisms for combinatorial auctions for the general case where bidders are not limited to {\sl single minded} valuations. The mechanisms we give have approximation ratios close to the best possible for both on-line and off-line scenarios. This is the first result where non-VCG mechanisms are derived for non-single minded bidders for a natural model of combinatorial auctions