95-09 Computationally Manageable Combinatorial Auctions

DIMACS TR: 95-09

Computationally Manageable Combinatorial Auctions

Authors: Michael H. Rothkopf, Aleksandar Pekec, Ronald M. Harstad

ABSTRACT
There is interest in designing simultaneous auctions for situations in which the value of assets to a bidder depends upon which other assets he or she wins. In such cases, bidders may well wish to submit bids for combinations of assets. When this is allowed, the problem of determining the revenue maximizing set of nonconflicting bids can be a difficult one. We analyze this problem, identifying several different structures of combinatorial bids for which computational tractability is constructively demonstrated and some structures for which computational tractability cannot be guaranteed.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-09.ps.gz

DIMACS Home Page