Method And System For Conducting Combinatorial Auctions

University of California System: University of California, Berkeley
posted on 01/28/2010

• request more info 
•   
•  LICENSE ONLINE

Advancements in game theory and auction analysis have led to the development of various mechanisms to facilitate exchanging goods, services, and other things of value. For example, the well-known Vickrey-Clarke-Groves (VCG) auctions have beenproposed for various exchange-type applications. Unfortunately, implementations of VCG auctions are often undesirably computationally complex and may require periodic infusions of capital for sustained operability. Such auctions are considered not budget balanced if additional infusions of capital are required. Furthermore, certain applications may require that certain desirable auction properties, such as efficiency, be compromised. An efficient auction may be an auction that maximizes the aggregate benefit to participants, i.e., the social welfare,when participants act to benefit themselves, i.e., they bid selfishly. In addition, conventional auction systems and methods often lack capabilities required for various real-world applications, especially applications involving exchange of combinations of items or things, such as portions of sub-links comprising a communication link. To solve this problem, researchers at UC Berkeley have developed a double-sided exchange wherein both buyers and sellers provide bids for matching via the exchange. A first interface receives buy bids from buyers and a second interface receives sell bids from sellers. A controller matches the sell bids with the buy bids, yielding matched buy bids and matched sell bids in response thereto so that allocations of the matched buy bids and the matched sell bids maximize a surplus of the exchange. An allocation that substantially maximizes an auctioneer’s profit and/or announces payments based on sell bids is provided. The announced allocations and prices can be shown to be a substantially competitive equilibrium in some applications.