DIMACS TR: 2000-27
Opportunity Cost Algorithms for Combinatorial Auctions
Authors: Karhan Akcoglu, James Aspnes, Bhaskar DasGupta and Ming-Yang
Kao
ABSTRACT
Two general algorithms based on opportunity costs are given for approximating
a revenue-maximizing set of bids an auctioneer should accept, in a
combinatorial auction in which each bidder offers a price for
some subset of the available goods and the auctioneer can only
accept non-intersecting bids. Since this problem is difficult
even to approximate in general, the algorithms are most useful when the bids
are restricted to be connected node subsets of an underlying object graph that
represents which objects are relevant to each other. The approximation
ratios of the algorithms depend on structural properties of this graph
and are small constants for many interesting families of object graphs.
The running times of the algorithms are linear in the size of the
bid graph, which describes the conflicts between bids. Extensions
of the algorithms allow for efficient processing of additional constraints,
such as budget constraints that associate bids with particular bidders
and limit how many bids from a particular bidder can be accepted.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-27.ps.gz
DIMACS Home Page