Karhan Akcoglu, James Aspnes, Bhaskar DasGupta, and Ming-Yang Kao.
Opportunity-cost algorithms for combinatorial auctions.
In
E. J. Kontoghiorghes, B. Rustem, and S. Siokos, eds.,
*Applied Optimization 74: Computational Methods in Decision-Making,
Economics and Finance*,
Kluwer Academic Publishers, 2002, pp. 455–479.
An earlier version is available as
DIMACS technical report 2000-27
and as
arXiv:cs.CE/0010031.

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.

- Full version:
**PDF**. - ArXiv version: arXiv:cs.CE/0010031.

@incollection(AkcogluADK2002, title="Opportunity-cost algorithms for combinatorial auctions", author="Karhan Akcoglu and James Aspnes and Bhaskar DasGupta and Ming-Yang Kao", booktitle="Applied Optimization 74: Computational Methods in Decision-Making, Economics and Finance", editor="E. J. Kontoghiorghes and B. Rustem and S. Siokos", publisher="Kluwer Academic Publishers", year=2002, pages={455--479} )

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page