Efficient privacy-preserving protocols for multi-unit auctions

Felix Brandt, Tuomas Sandholm

Research output: Contribution to journalConference articlepeer-review

30 Scopus citations

Abstract

The purpose of multi-unit auctions is to allocate identical units of a single type of good to multiple agents. Besides well-known applications like the selling of treasury bills, electrical power, or spectrum licenses, multi-unit auctions are also well-suited for allocating CPU time slots or network bandwidth in computational multiagent systems. A crucial problem in sealed-bid auctions is the lack of trust bidders might have in the auctioneer. For one, bidders might doubt the correctness of the auction outcome. Secondly, they are reluctant to reveal their private valuations to the auctioneer since these valuations are often based on sensitive information. We propose privacy-preserving protocols that allow bidders to jointly compute the auction outcome without the help of third parties. All three common types of multi-unit auctions (uniform-price, discriminatory, and generalized Vickrey auctions) are considered for the case of marginal decreasing valuation functions. Our protocols are based on distributed homomorphic encryption and can be executed in a small constant number of rounds in the random oracle model. Security merely relies on computational intractability (the decisional Diffie-Hellman assumption). In particular, no subset of (computationally bounded) colluding participants is capable of uncovering private information.

Original languageEnglish
Pages (from-to)298-312
Number of pages15
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3570
DOIs
StatePublished - 2005
Externally publishedYes
Event9th International Conference on Financial Cryptography and Data Security, FC 2005 - Roseau, Dominican Republic
Duration: 28 Feb 20053 Mar 2005

Fingerprint

Dive into the research topics of 'Efficient privacy-preserving protocols for multi-unit auctions'. Together they form a unique fingerprint.

Cite this