Second-Best Combinatorial Auctions - The Case of the Pricing-Per-Column Mechanism

One of the main contributions of classical mechanism design is the derivation of the Groves mechanisms. The class of Groves mechanisms are the only mechanisms that are strategy-proof and more importantly allocative efficient. The VCG mechanism retains its properties for combinatorial allocation problems. From a computational perspective the VCG has to solve two problems: (1) the winner-determination (2) the determination of the prices. However, both problems are complex (NP-hard), when complementarities are present. The pricing-per-column (PPC) auction is another approach to solve the combinatorial allocation problem. In essence, it applies the Vickrey principle to any possible combination of goods and determines the overall winning bids. PPC is computationally less demanding, however, it can be shown that PPC is not necessarily efficient. Apparently, solving the tension between computational and game-theoretic properties is a challenging task in mechanism design. Engineering auctions suggests to lower requirements upon the auction. In this paper the evaluation of the PPC concerning approximate efficiency is presented - in an analytical and simulative evaluation the PPC is compared to the VCG and it is shown that the efficiency losses incurred by the PPC mechanism are very small