zbMATH — the first resource for mathematics

An experimental study of the misdirection algorithm for combinatorial auctions. (English) Zbl 1129.91320
Erlebach, Thomas (ed.) et al., Approximation and online algorithms. 4th international workshop, WAOA 2006, Zurich, Switzerland, September 14–15, 2006. Revised papers. Berlin: Springer (ISBN 978-3-540-69513-4/pbk). Lecture Notes in Computer Science 4368, 265-278 (2007).
Summary: Single-minded combinatorial auctions (CA) are auctions in which a seller wants to sell diverse kinds of goods and each of the potential buyers, also called bidders, places a bid on a combination, i.e., a subset of the goods. There is a severe computational limitation in CA, as the problem of computing the optimal allocation is NP-hard and even hard to approximate. There is thus interest in polynomial time approximation algorithms for this problem. Recently, many such approximation algorithms were designed, among them greedy and local search based algorithms. One of these is a so-called misdirection algorithm combining both approaches and using a non-standard, misdirected, local search approach with neighborhood of size 2. This algorithm has the best known provable approximation ratio for the problem in terms of the sizes of bids. Its analysis, however, is quite complicated. We study this algorithm and its variants on typical instances designed for CAs. One question is if larger neighborhood helps – a question that seems quite difficult to address theoretically at the moment, taking into account already complex analysis for size 2 neighborhood. We also study experimentally other aspects of the misdirection algorithm, and finally present a comparison to other approximation algorithms.
For the entire collection see [Zbl 1128.68001].
91B26 Auctions, bargaining, bidding and selling, and other market models
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI