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
Abstract
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