Approximation Algorithms for Secondary Spectrum Auctions

graph: There is a set of k communication channels that should be
allocated to n >> k bidders. Bidders have arbitrary valuations for
bundles of channels. A channel can be assigned to multiple bidders
unless there is a conflict between two bidders sharing the same channel. Conflicts are described in terms of a graph in which nodes represent bidders and edges represent conflicts. This problem generalizes combinatorial auctions and maximum weight independent set.

To motivate our study, we show that problem formulations for secondary
spectrum auctions in well established models for wireless communication can be reduced to the combinatorial auction problem with different variants of conflict graphs. We prove that for the conflict graphs obtained in our reductions the so-called inductive independence number \rho can be bounded by a constant or a logarithmic function for many prominent communication models. This allows us to construct efficient approximation algorithms with approximation factors based on \rho and k for the combinatorial auction problem with conflict graph -- thereby bypassing strong lower bounds for independent set problems. Our approximation ratios are close to best possible in both \rho and k. The algorithms can be used to derive incentive compatible mechanisms using the LP-based framework of Lavi and Swamy for general bidders with demand oracles. The obtained mechanisms are truthful in expectation.