Combinatorial Auctions with Externalities

Although combinatorial auctions have received a great deal of attention from the computer science community over the past decade, research in this domain has focussed on settings in which a bidderonly has preferences over the bundles of goods they themselvesreceive, and is indifferent about how other goods are allocated toother bidders. In general, however, bidders in combinatorial auctions will be subject to externalities: they care about how the goodsthey are not themselves allocated are allocated to others. Our aimin the present work is to study such combinatorial auctions withexternalities from a computational perspective. We first presentour formal model, and then develop a classification scheme for thetypes of externalities that may be exhibited in a bidder's valuationfunction. We develop a bidding language for combinatorial auctions with externalities, which uses weighted logical formulae torepresent bidder valuation functions. We then investigate the properties of this representation: we study the complexity of the winnerdetermination problem, and characterise the complexity of classifying the properties of valuation functions. Finally, we considerapproximation methods for winner determination.

Authors

• Piotr Krysta
• Tomasz Michalak University of Warsaw IDEAS NCBR
• Tuomas Sandholm Carnegie Mellon University, Computer Science Department, Pittsburgh, USA Strategy Robot, Inc. Strategic Machine, Inc. Optimized Markets, Inc.
• Michael Wooldridge University of Oxford

Keywords

• auctions
• externalities
• complexity
• winner determination