Combinatorial auction design
- aInterdisciplinary Center for Economic Science, George Mason University, Fairfax, VA 22030; and cCybernomics Inc., 2212 E. Camino El Ganado, Tucson, AZ 85718
-
Contributed by Vernon Smith, June 17, 2003
Abstract
Combinatorial auctions allow for more expressive bidding in which participants can submit package bids with logical constraints that limit allowable outcomes. This type of auction can be useful when participants' values are complementary or when participants have production and financial constraints. However, combinatorial auctions are currently rare in practice. The main problems confronted in implementing these auctions are that they have computational uncertainty (i.e., there is no guarantee that the winning bids for such an auction can be found in a “reasonable” amount of time when the number of bidders and items becomes larger) and that the auction is cognitively complex and can lead participants to pursue perverse bidding strategies. This article describes a type of combinatorial auction that, during laboratory testing, eliminated these problems and produced extremely efficient outcomes.
Footnotes
-
↵ b To whom correspondence should be addressed. E-mail: dporter4{at}gmu.edu.
-
Abbreviations: FCC, Federal Communications Commission; SMR, simultaneous multiround auction; IP, integer program; CRA, Charles River and Associates; CC, combinatorial clock.
-
See commentary on page 10590.
-
↵ d In some instances, such risk may reduce the aggressiveness with which bidders bid and, in so doing, may lead to a misassignment of items. In other instances, bidders may bid too aggressively and, in so doing, obtain items at prices that exceed the value the bidder places on those items.
-
↵ e A buyers' auction becomes two-sided when sellers may participate as buyers of their own offerings.
-
↵ f For example, conservation of flow in network distribution systems or storage- and channel-capacity limits can be applied as allocation constraints in the auction proposed.
-
↵ g This is the supermarket problem also referred to at various FCC discussions as the 2N boogie man because there are that many combinations of items that a bidder must consider. Suppose you have $100 in your pocket and you are standing at the entrance to the supermarket. You despondently realize that you may never come out because you must first consider every possible way you might fill your shopping cart.
-
↵ h By transparency, we mean that bidders can easily determine what bid amount would be the current winner of a set of items.
-
↵ i For example, if a winning bid is for a package containing one unit of item C and one of item D, then the bidder isn't concerned with whether the winning prices are 40 and 60 or 60 and 40, respectively, as long as they eliminate his competition and have a total cost less than he is willing to pay.
-
↵ j For example a bid on a package containing items C and D at current clock prices in round t can be resubmitted as a package in round t + 1 by bidding on one item at the previous (pre) price as long as at least one item is bid at the current new price: for example, {C, D}t can become {preC, D}t+1.
-
↵ k V * is the value of the maximization problem max Σv j·x j subject to x jε{0,1} and Σx j·y j ≤ Y, where v j is the value for package j, y j is the vector of elements of package j, and Y is the vector of total supply.
-
↵ l V̂ is the value of the max {v 1Y,..., v nY}, where v iY is the value of participant i for the entire supply Y.
- Copyright © 2003, The National Academy of Sciences
