Open Problems

  There are a variety of natural questions left unanswered by the work described. Below, we list a few natural directions for further work in this area. Work is under way on variations on the protocol which will address tie-breaking issues, reduce communication costs, and

1. Tie-breaking
   The protocol described does not provide efficient tie-breaking without some loss of privacy.

2. Communication Costs
   While we believe the communication costs are sufficiently small to make this protocol practical in many situations, low-value auctions are likely to play an increasingly important role in electronic commerce. Efficiency improvements that enable auctions with private bids in these low-value situations could be very useful.

3. Hierarchical Auctions
   In some situations, it might be advantageous to hold sub-auctions which partially determine the outcome of the auction. For example, each country might hold a sub-auction, with the leading candidates from each country participating in a final auction. In order to preserve privacy, the winners of the sub-auctions and their bids must not be revealed.

4. Double Auctions and Auction Markets
   A double auction is a more general form of auction where there are multiple sellers and multiple buyers. All parties tender bids and a market clearing price is determined from those bids. A market clearing price is the equilibrium price at which the supply and demand (in units of the good) are equal. An auction market is a generalization of a double auction to continuous time. New bids are added and removed over time, causing the market clearing price to fluctuate. The stock market is a well known example of an auction market. Double auctions and auction markets are powerful market mechanisms, and privacy protecting protocols for these mechanism would be desirable. However, to be useful, such protocols must be highly efficient, particularly in the case of auction markets.

5. Privacy vs. Performance
   The protocol described protects information privacy at the cost of greater overhead. It is possible that performance could be improved by relaxing some of the privacy constraints. What is the nature of this tradeoff? Depending on the context of the auction, relaxing privacy constaints could be appropriate.