Truthful spectrum auctions with approximate revenue

In cellular networks, a recent trend is to make spectrum access dynamic in the spatial and temporal dimensions, for the sake of efficient utilization of spectrum. In such a model, the spectrum is divided into channels and periodically allocated to competing base stations using an auction-based market mechanism. An “efficient” auction mechanism is essential to the success of such a dynamic spectrum access model. Two of the key objectives in designing an auction mechanism are “truthfulness” and revenue maximization. In this article, we design a polynomial-time spectrum auction mechanism that is truthful and yields an allocation with O(1)-approximate expected revenue, in the Bayesian setting. Our mechanism generalizes to general interference models. To the best of our knowledge, ours is the first work to design a polynomial-time truthful spectrum auction mechanism with a performance guarantee on the expected revenue. We demonstrate the performance of our designed mechanism through simulations.