Tech Reports

ULCS-10-010

Combinatorial Auctions with Externalities: Basic Properties and Bidding Languages

Piotr Krysta, Tomasz Michalak, Tuomas Sandholm and Michael Wooldridge

Abstract

Although combinatorial auctions have received a great deal of attention from the computer science community over the past decade, research in this domain has focused on settings in which a bidder only has preferences over the bundles of goods they themselves receive, and is indifferent about how other goods are allocated to other bidders. In general, however, bidders in combinatorial auctions will be subject to externalities: they care about how the goods they are not themselves allocated are allocated to others. Our aim in the present paper is to study such combinatorial auctions with externalities from a computational perspective. We first present our formal model, and then develop a classification scheme for the types of externalities that may be exhibited in a bidder's valuation function. We then develop a bidding language for combinatorial auctions with externalities. The language uses weighted logical formulae to represent bidder valuation functions. We then investigate the properties of this representation: we study the complexity of the winner determination problem, and characterise the complexity of classifying the properties of valuation functions. We then present two approaches to winner determination for our bidding language: an exact approach based on integer linear programming, and approximation methods.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.