Complexity of Allocation Problems in Spectrum Markets with Interference Complementarities
Markets are often viewed as a key ingredient in facilitating more efficient dynamic spectrum access. In this paper the authors consider how such spectrum markets are influenced by a key property of the wireless medium: interference. Interference can result in "Complementarities" among the "Spectrum goods" being traded, which complicates the design of an efficient market mechanism. They consider several alternative models for defining such spectrum goods, and explore the impact of these choices on the complexity of the resulting market.