Multi-Round Anonymous Auction Protocols

Hiroaki KIKUCHI  Michael HAKAVY  Doug TYGAR  

IEICE TRANSACTIONS on Information and Systems   Vol.E82-D   No.4   pp.769-777
Publication Date: 1999/04/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Internet Technology and Its Applications)
auction,  multiparty computation,  anonymity,  communication cost,  

Full Text: PDF(226.3KB)>>
Buy this Article

Auctions are a critical element of the electronic commerce infrastructure. But for real-time applications, auctions are a potential problem - they can cause significant time delays. Thus, for most real-time applications, sealed-bid auctions are recommended. But how do we handle tie-breaking in sealed-bid auctions? This paper analyzes the use of multi-round auctions where the winners from an auction round participate in a subsequent tie-breaking second auction round. We perform this analysis over the classical first-price sealed-bid auction that has been modified to provide full anonymity. We analyze the expected number of rounds and optimal values to minimize communication costs.