Toward a VCG-Like Approximate Mechanism for Large-Scale Multi-unit Combinatorial Auctions

Multi-unit combinatorial auction is a combinatorial auction that has some items that can bee seen as indistinguishable. Although the mechanism can be applied for dynamic electricity auctions and various purposes, it is difficult to be applied for large-scale auction problems due to its computational intractability. In this paper, I introduce a mechanism that employs an approximate allocation and pricing algorithm that is capable to handle multi-unit auctions. The algorithm effectively produce approximation allocations that are necessary in pricing and it behaves as an approximation of VCG(Vickrey-Clarke-Groves) mechanism satisfying budget balance condition and bidders´ individual rationality without having single-minded bidders assumption. I show that the proposed allocation algorithm successfully produced good allocations for the problems that cannot be easily solved by ordinary LP solvers due to hard time constraints.