Approximating Revenue-Maximizing Combinatorial Auctions

Anton Likhodedov, Tuomas Sandholm

Designing revenue-maximizing combinatorial auctions (CAs) is a recognized open problem in mechanism design. It is unsolved even for two bidders and two items for sale. Rather than attempting to characterize the optimal auction, we focus on designing approximations (suboptimal auction mechanisms which yield high revenue). Our approximations belong to the family of virtual valuations combinatorial auctions (VVCA). VVCA is a Vickrey-Clarke-Groves (VCG) mechanism run on virtual valuations that are linear transformations of the bidders’ real valuations. We pursue two approaches to constructing approximately optimal CAs. The first is to construct a VVCA with worst-case and average-case performance guarantees. We give a logarithmic approximation auction for basic important special cases of the problem: 1) limited supply of items on sale with additive valuations and 2) unlimited supply. The second approach is to search the parameter space of VVCAs in order to obtain high-revenue mechanisms for the general problem. We introduce a series of increasingly sophisticated algorithms that use economic insights to guide the search and thus reduce the computational complexity. Our experiments demonstrate that in many cases these algorithms perform almost as well as the optimal VVCA, yield a substantial increase in revenue over the VCG mechanism and drastically outperform the straightforward algorithms in run-time.

Content Area: 4. Auctions and Market-Based Systems

Subjects: 7.1 Multi-Agent Systems; 1. Applications

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.