Secure Combinatorial Auctions by Dynamic Programming with Polynomial Secret Sharing
Koutarou Suzuki, Makoto Yokoo,
Sixth International Financial Cryptography Conference
(FC-02), 2002.
Combinatorial auctions have recently attracted the interests of
many researchers due to their promising applications such as the spectrum
auctions recently held by the FCC.
In a combinatorial auction, multiple items with
interdependent values are sold simultaneously and bidders are allowed
to bid on any combination of items. This paper presents a method for
implementing several secure combinatorial auction protocols based on
our newly developed secure dynamic programming protocol. Dynamic
programming is a very effective, widely used technique for tackling various
combinatorial optimization problems, including several types of
combinatorial auctions. Our secure dynamic programming protocol
utilizes secret sharing techniques and can obtain the optimal solution
of a combinatorial optimization problem, i.e., result of a
combinatorial auction, without revealing the inputs of the problem, i.e.,
bidding prices. We discuss the application of the method to several
combinatorial auctions, i.e., multiple-unit single-item auctions,
linear-goods auctions, and general combinatorial auctions.