DIMACS TR: 95-09
Computationally Manageable Combinatorial Auctions
Authors: Michael H. Rothkopf, Aleksandar Pekec, Ronald M. Harstad
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:
DIMACS Home Page