Double auctions for dynamic spectrum allocation

Wireless spectrum is a precious resource and must be allocated and used efficiently. The conventional spectrum allocation lets a government (e.g., FCC) sell a given portion of spectrum to one provider. This is not only restrictive, but also limits spectrum reuse and may lead to significant under-utilization of spectrum. In this paper, we develop a novel truthful double auction scheme to let any resource owner (e.g., a cellular provider), who has spare spectrum at a given time, sell to one or more providers that need additional spectrum at that time. Spectrum auction is fundamentally different from conventional auction problems since spectrum can be re-used and competition pattern is complex due to wireless interference. We propose the first double auction design for spectrum allocation that explicitly decouples the buyer side and seller side auction design while achieving (i) truthfulness, (ii) individual rationality, and (iii) budget balance. To accurately capture wireless interference and support spectrum reuse, we partition the conflict graph so that buyers with strong direct and indirect interference are put into the same subgraph and buyers with no or weak interference are put into separate subgraphs and then compute pricing independently within each subgraph. We develop a merge scheme to combine spectrum allocation results from different subgraphs and resolve potential conflicts. Using conflict graphs generated from real cell tower locations, we extensively evaluate our approach and demonstrate that it achieves high efficiency, revenue, and utilization.