Approximation Algorithms for Secondary Spectrum Auctions

Abstract

We study combinatorial auctions for secondary spectrum markets, where short-term communication licenses are sold to wireless nodes. Channels can be assigned to multiple bidders according to interference constraints captured by a conflict graph. We suggest a novel approach to such combinatorial auctions using a graph parameter called inductive independence number. We achieve good approximation results by showing that interference constraints for wireless networks imply a bounded inductive independence number. For example, in the physical model the factor becomes O (√ k log 2 n ) for n bidders and k channels. Our algorithms can be turned into incentive-compatible mechanisms for bidders with arbitrary valuations.