Eliciting Bid Taker Non-Price Preferences in (Combinatorial) Auctions

Abstract

Recent algorithms provide powerful solutions to the problem of determining cost-minimizing (or revenue-maximizing) allocations of items in com-binatorial auctions. However, in many settings, cri-teria other than cost (e.g., the number of winners, the delivery date of items, etc.) are also relevant in judging the quality of an allocation. Furthermore, the bid taker is usually uncertain about her pref-erences regarding tradeoffs between cost and non-price features. We describe new methods that allow the bid taker to determine (approximately) optimal allocations despite this. These methods rely on the notion of minimax regret to guide the elicitation of preferences from the bid taker and to measure the quality of an allocation in the presence of utility function uncertainty. Computational experiments demonstrate the practicality of minimax computa-tion and the efficacy of our elicitation techniques. 1