Stepwise Randomized Combinatorial Auctions Achieve Revenue Monotonicity  

by Baharak Rastegari

In combinatorial auctions that use VCG, a seller can sometimes increase revenue by dropping bidders. In our previous work,  we showed that such failures of ``revenue monotonicity'' occur under an extremely broad range of deterministic strategyproof combinatorial auction mechanisms, even when bidders have ``known single-minded'' valuations. In this work we consider the question of whether revenue monotonic, strategyproof mechanisms for such bidders can be found in the broader class of randomized mechanisms. We demonstrate thatsurprisinglysuch mechanisms do exist. We represent such a randomized mechanism as a solution to a quadratically constrained linear program, prove that it is always feasible (i.e., for all bidder valuations) and give its solution analytically. Furthermore, we give an algorithm for running such a mechanism in time quadratic in the number of bidders.

Visit the LCI Forum page