**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 that—surprisingly—such 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.