Incentive Compatible Mulit-Unit Combinatorial Auctions: A Primal Dual Approach

We study multi-unit combinatorial auctions with multi-minded buyers. We provide two deterministic, efficient maximizing, incentive compatible mechanisms that improve upon the known algorithms for the problem (Bartal et al., Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge TARK IX, pp. 72–87, 2003). The first mechanism is an online mechanism for a setting in which buyers arrive one-by-one in an online fashion. We then design an offline mechanism with better performance guarantees based on the online mechanism. We complement the results by lower bounds that show that the performance of our mechanisms is close to optimal. The results are based on an online primal-dual approach that was used extensively recently and reveals the underlying structure of the problem.