Approximately Truthful Mechanisms for Radio Spectrum Allocation

In wireless networks, a recent trend is to make spectrum access dynamic for efficient utilization of spectrum. In such a scenario, the spectrum is periodically allocated to wireless users using an auction-based market mechanism. A critical property required for designing such a mechanism is truthfulness, which could avoid market manipulation. Such mechanism design typically involves solving NP-hard problems; hence, approximation algorithms are always resorted to in real systems. However, recent results have suggested that it is impossible to implement reasonable approximations without losing robustness to manipulation. In this paper, we solve the problem in a novel perspective by relaxing the constraints of ensuring strong truthfulness. We discuss the concepts of approximate truthfulness and provide approximately truthful mechanisms to improve efficiency (in terms of social welfare and spectrum utilization). We first develop a computationally efficient mechanism that achieves truthful in expectation. This mechanism is based on the assumption that bidders are risk neutral. Following that, we break the assumption by proposing a hard-to-manipulate auction (HMA), which makes it hard to manipulate the auction for profit gains. Our extensive simulation results show that our mechanisms can achieve significant improvement over the state-of-the-art mechanisms.