Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: cebly@cs.toronto.edu
Abstract
Combinatorial auctions provide a valuable mechanism for the
allocation of goods in settings where buyer valuations exhibit
complex structure with respect to substitutability and
complementarity. Most algorithms are designed to work with
explicit "flat" bids for concrete bundles of goods. However, logical
bidding languages allow the expression of complex utility
functions in a natural and concise way, and have recently attracted
considerable attention.
Despite the power of logical languages, no current winner determination
algorithms exploit the specific structure of logically specified
bids to solve problems more effectively. In this paper, we describe
techniques to do just this. Specifically, we propose a direct
integer program (IP) formulation of the winner determination
problem for bids in the LGB logical language. This formulation
is linear in the size of the problem and can be solved effectively
using standard optimization packages. We compare this formulation
and its solution time to those of the corresponding set of flat bids,
demonstrating the immense utility of exploiting the structure of
logically expressed bids. We also consider an extension of
LGB and show that these can also be solved using linear constraints.
To appear, AAAI-02
Return to List of Papers