TY - GEN
T1 - Secure combinatorial auctions by dynamic programming with polynomial secret sharing
AU - Suzuki, Koutarou
AU - Yokoo, Makoto
N1 - Publisher Copyright:
© IFCA/Springer-Verlag Berlin Heidelberg 2003.
PY - 2003
Y1 - 2003
N2 - 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 tackhng vaxious 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 singleitem auctions, linear-goods auctions, and general combinatorial auctions.
AB - 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 tackhng vaxious 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 singleitem auctions, linear-goods auctions, and general combinatorial auctions.
UR - http://www.scopus.com/inward/record.url?scp=84957038963&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84957038963&partnerID=8YFLogxK
U2 - 10.1007/3-540-36504-4_4
DO - 10.1007/3-540-36504-4_4
M3 - Conference contribution
AN - SCOPUS:84957038963
SN - 354000646X
SN - 9783540006466
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 44
EP - 56
BT - Financial Cryptography - 6th International Conference, FC 2002, Revised Papers
A2 - Blaze, Matt
PB - Springer Verlag
T2 - 6th International Financial Cryptography Conference, FC 2002
Y2 - 11 March 2002 through 14 March 2002
ER -