Opportunity-cost algorithms for combinatorial auctions

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.


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",

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page