GA Based Winner Determination in Combinatorial Reverse Auction

Abstract

Combinatorial auction provides efficient resource allocations than traditional auction mechanisms in multi-item auctions, where the valuation of the items are not additive. However, solving winner determination problem so as to minimize procurement cost in combinatorial auction is NP-complete. In this paper, we consider a procurement scenario where the buyer wants to procure single unit of multiple items from a set of suppliers using single round sealed bid auction. The suppliers provide XOR bids for all the combinations of items. We propose Genetic Algorithm for solving winner determination problem for combinatorial allocation. A concept of repairing infeasible solution is used during the solution. We show that the algorithm is able to solve the problem within reasonable time.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 26 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.