On Designing Distributed Auction Mechanisms for Wireless Spectrum Allocation
Auctions are believed to be effective methods to solve the problem of wireless spectrum allocation. Existing spectrum auction mechanisms are all centralized and suffer from several critical drawbacks of the centralized systems, which motivates the design of distributed spectrum auction mechanisms. However, extending a centralized spectrum auction to a distributed one broadens the strategy space of agents from one dimension (bid) to three dimensions (bid, communication, and computation), and thus cannot be solved by traditional approaches from mechanism design. In this paper, we propose two distributed spectrum auction mechanisms, namely distributed VCG and FAITH. Distributed VCG implements the celebrated Vickrey-Clarke-Groves mechanism in a distributed fashion to achieve optimal social welfare, at the cost of exponential communication overhead. In contrast, FAITH achieves sub-optimal social welfare with tractable computation and communication overhead. We prove that both of the two proposed mechanisms achieve faithfulness, i.e., the agents' individual utilities are maximized, if they follow the intended strategies. Besides, we extend FAITH to adapt to dynamic scenarios where agents can arrive or depart at any time, without violating the property of faithfulness. We implement distributed VCG and FAITH, and evaluate their performance in various setups. Evaluation results show that distributed VCG results in optimal allocation, while FAITH is more efficient in computation and communication.
S. Yang et al., "On Designing Distributed Auction Mechanisms for Wireless Spectrum Allocation," IEEE Transactions on Mobile Computing, vol. 18, no. 9, pp. 2129 - 2129, Institute of Electrical and Electronics Engineers (IEEE), Sep 2018.
The definitive version is available at https://doi.org/10.1109/TMC.2018.2869863
Keywords and Phrases
Communication system security; Cost accounting; Distributed Algorithmic Mechanism Design; Faithfulness; Game Theory; Interference; Mobile computing; Resource management; Spectrum Allocation; VCG Mechanism; Wireless Network; Wireless networks
International Standard Serial Number (ISSN)
Article - Journal
© 2018 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
01 Sep 2018