Click here for full text:
Generating k Best Solutions to Winner Determination Problems: Algorithms & Application to Procurement
Kelly, Terence; Byde, Andrew
HPL-2006-40
Keyword(s): auctions; procurement; knapsack problems; k-shortest paths; decision support; preference elicitation
Abstract: Auction participants often cannot easily articulate their requirements and preferences. The buyer in a procurement auction, for instance, may hesitate to quantify the value of non-price solution attributes, and she may have difficulty delineating between hard and soft constraints. Consequently it can be difficult to formulate the winner determination problem (WDP) as a straightforward optimization problem. Existing decision-support aids for such situations, including scenario navigation and preference elicitation, address this difficulty through extensions to an optimization framework. This paper presents a complementary approach that frames the procurement decision problem as one of exploration rather than optimization. The foundation of our approach is an algorithm that generates k best solutions to auction WDPs. Our algorithm can scale to practical problem sizes for an interesting class of procurement auctions, and furthermore can incorporate hard constraints into the generation process. We describe ways of extracting useful guidance for the decision- maker from k-cheapest WDP solutions. We evaluate our method using real bids submitted by real suppliers in an HP material parts procurement auction.
10 Pages
Back to Index
| 
Printable version
