STAMP: A Strategy-proof Approximation auction Mechanism for Spatially reusable Items in wireless networks

The advent of participatory sensing markets and spectrum markets based on the wireless networks have led to a new kind of auction dealing with spatially reusable items, which can be shared by multiple parties that are geographically far apart enough from each other. Simply applying traditional auctions to spatially reusable items is vulnerable to bid manipulation, and may lead to low allocation efficiency. In this paper, we study the problem of auctioning spatially reusable items. We propose STAMP, which is a STrategy-proof Approximation auction Mechanism for sPatially reusable items in wireless networks. STAMP can be implemented with any existing maximum independent set algorithm, and can guarantee the allocation efficiency as high as the algorithm based on. Evaluation results show that STAMP achieves much better performance than existing mechanisms, in terms of allocation efficiency.