Tackling Bidder Collusion in Dynamic Spectrum Auctions (Extended)

Report ID: 
2009-13
Authors: 
Xia Zhou, Alessandra Sala, and Haitao Zheng
Date: 
2009-08-01 05:00:00

Abstract

Dynamic spectrum auction is an effective solution to manage spectrum across many small networks. As the number of participants grows, collusion poses a serious threat to auction performance. Small groups of colluding bidders can make use of the interference constraints to manipulate auction outcomes, leading to unfair spectrum distribution and significant loss in auction revenue. Prior designs, however, are either forced to give up spatial reuse for collusion-resistance, become computationally prohibitive, or can only address very limited types of collusion. In this paper, we present DC2, a systematic auction design that can effectively discourage collusion and achieve spatial reuse, even when multiple collusion groups are present. DC2 achieves this using a novel 3-stage “Divide, Conquer, and Combine” procedure that integrates an efficient spectrum allocation algorithm with a powerful collusion-resistant mechanism design. More importantly, DC2 can configure the level of collusionresistance and maximize auction revenue for any given level. Auctioneers can now configure auctions based on their own preferences and deployment environments. We analytically prove DC2’s collusion-resistance and its revenue bound, and perform extensive network simulations to verify DC2’s effectiveness. We show that it is particularly effective against small-size collusion, the most commonly observed in practical auctions.

Document

PDF icon 2009-13.pdf