Introduction

Auctions are a fundamental technology for electronic commerce. They have been suggested as a technology for controlling allocation of bandwidth [5, 10] and are increasingly seen on the web.

If we could have an ideal auction, what properties might we desire? Here are some desiderata (not a complete list) for an ideal auction:

• Economic design -- we want the auction to be designed on solid economic principles and for participants to have incentives to bid as they truly value the item -- this is known as their valuation, and is also called their indfference price. If bidders bid less than their true valuations, it is possible that the final winning bid may be artificially low -- we illustrate this below in our discussion of sealed-bid auctions.

• Fast execution -- we want to have the auction run quickly.

• Privacy -- we want the auction to be private -- for others to not know our actual bids. We do not want even an auctioneer to know the bids. The only exception to this rule is that we will reveal the final price at which the item is sold. (At first this may seem like a paradoxical condition, but it is commonly achieved in Dutch auctions, discussed below.) Note that this is a quite useful requirement -- otherwise we give away detailed information on our preferences that may be used in the future to inform ``shills'' who work for the seller to attempt to artificially drive up the price an item is sold at (creating a disincentive to bid the true valuation.)

• Anonymity -- we don't want our identities to be revealed. One way to achieve this is to use an intermediary to anonymously forward our bids. Note that privacy is different from anonymity; privacy protects the values of the bids while anonymity protects the identities of the bidders. Even if our bids are anonymously forwarded, participants (such as the auctioneer) may learn the distribution of our bids.

In this paper, we discuss how to hold a true auction that combines the first three features. If we add anonymizing intermediaries to the mix, we can achieve an auction with all four properties.

• Auction Types
• Secret computation