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

Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: cebly@cs.toronto.edu

Tuomas Sandholm
Computer Science Department
Carnegie Mellon University
Pittsburgh, PA, 15213
email: sandholm@cs.cmu.edu

Rob Shields
CombineNet Inc.
Fifteen 27th Street
Pittsburgh, PA 15222
email: Pittsburgh, PA 15222

Recent algorithms provide powerful solutions to the problem of determining cost-minimizing (or revenue-maximizing) allocations of items in combinatorial auctions. However, in many settings, criteria 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 preferences 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 computation and the efficacy of our elicitation techniques.

To appear, AAAI-04

Return to List of Papers