Optimal Winner Determination Algorithms for E-procurement Auction

In this paper, a winner determination problem in combinatorial auctions where there are more than two supplies of the same kind of asset is introduced. In combinatorial auction, the problem of finding the optimal allocation which maximizes revenue is NP-complete, but often seen in most combinatorial auction framework like the Generalized Vickrey Auction. Managing this computational difficulty, some restrictions to the combinations of assets allowed to be bid for has been proposed. We extend them to our case and give algorithms using dynamic programming. We consider such two cases : (1) each bid contains only one kind of assets, and (2) the combinations of assets allowed to be bid for have a hierarchical structure.