Revenue Monotonicity in Combinatorial Auctions

Baharak Rastegari, Anne Condon, Kevin Leyton-Brown

Intuitively, one might expect that a seller's revenue from an auction weakly increases as the number of bidders grows, as this increases competition. However, it is known that for combinatorial auctions that use the VCG mechanism, a seller can sometimes increase revenue by dropping bidders. In this paper we investigate the extent to which this problem can occur under other dominant-strategy combinatorial auction mechanisms. Our main result is that such failures of "revenue monotonicity" are not limited to mechanisms that achieve efficient allocations. Instead, they can occur under any dominant-strategy direct mechanism that sets prices using critical values, and that always chooses an allocation that cannot be augmented to make some bidder better off, while making none worse off.

Subjects: 7.1 Multi-Agent Systems; 15.9 Theorem Proving

Submitted: Apr 25, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.