In a single-round, sealed-bid auction, every bidder, independently, submits a single bid without seeing the bids of others. One talks about unlimited supply, unit-demand auctions when an infinite number of items is for sale, and every consumer desires at most one unit. An auction is truthful when each bidder has his own strategy to bid, and bid his utility value, regardless of the actions of the other bidders. The aim in general is to design an auction such that it yields a revenue within a constant factor of optimal fixed pricing.

Given a set of bids, the outcome of an auction is the subset of bids that are satisfied and a corresponding set of sale prices such that for each winning bid b_i, the associated sale price is at most b_i. A deterministic auction mechanism maps sets of bids to an outcome, while a randomized auction mechanism maps sets of bids to probability distributions on auction outcomes.

A result from Goldberg et al. [1] shows that the simplest truthful auction that is approximately optimal in the worst case is a randomized auction. In this paper, the authors show the existence of deterministic auctions that are approximately optimal in the worst case. They also show that such an auction is necessarily asymmetric, that is, the outcome can depend on the order of the input bids. This result answers a question that was left open in Goldberg et al. [1].