Competitive auctions

We study a class of single-round, sealed-bid auctions for an item in unlimited supply, such as a digital good. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e. encourages bidders to bid their true valuations) and on all inputs yields profit that is within a constant factor of the profit of the optimal single sale price. We justify the use of optimal single price profit as a benchmark for evaluating a competitive auctions profit. We exhibit several randomized competitive auctions and show that there is no symmetric deterministic competitive auction. Our results extend to bounded supply markets, for which we also give competitive auctions.