Secure combinatorial auctions by dynamic programming with polynomial secret sharing

Koutarou Suzuki, Makoto Yokoo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationFinancial Cryptography - 6th International Conference, FC 2002, Revised Papers
EditorsMatt Blaze
PublisherSpringer Verlag
Number of pages13
ISBN (Print)354000646X, 9783540006466
Publication statusPublished - 2003
Externally publishedYes
Event6th International Financial Cryptography Conference, FC 2002 - Southampton, Bermuda
Duration: Mar 11 2002Mar 14 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other6th International Financial Cryptography Conference, FC 2002

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Secure combinatorial auctions by dynamic programming with polynomial secret sharing'. Together they form a unique fingerprint.

Cite this